Complexity analysis for a third-order algorithm to reach second-order stationarity

• Ano de defesa: 2024
• Autor(a) principal: Silva, David Ricardo Barreto Lima
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Complexidade; Complexity; Interior-point; Linearly-constraint; Não convexo; Nonconvex; Nonlinear optimization; Otimização não linear; Ponto estacionário; Ponto interior; Restrição linear; Second-order; Segunda ordem; Stationary point; Terceira ordem; Third-order
• Link de acesso: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-27092024-163832/

We develop a third-order interior-point-trust-region algorithm for nonconvex and non-negative constrained optimization with convergence to a second-order stationary point. Usually, a p-th order derivative p 3 is used only to improve the complexity bounds for finding a first-order stationary point or a p-th order stationary point to within a tolerance. Namely, when only the second-order derivative is considered, the version of our algorithm is known to achieve a second-order stationary point within tolerance > 0 in at most O(^(3)) iterations, while we show that using the third-order derivative, this complexity is improved to O(^(2)). The price to pay for achieving this result is that at each iteration of the algorithm, we solve a cubic ball constrained subproblem, which is considerably harder than its quadratic counterpart.