Três contribuições em otimização não-linear e não-convexa

Abstract

Resumo: Esta tese apresenta três trabalhos sobre otimização não-linear e não-convexa. No primeiro trabalho, propõe-se uma versão subespacial do método de região de confiança Powell-Yuan para problemas de otimização suave com restrições de igualdade. A principal característica do método apresentado é que, a cada iteração, o subproblema Celis-Dennis-Tapia (CDT) é resolvido em um determinado subproblema, o que reduz o esforço computacional necessário para o cálculo do passo. Testes numéricos preliminares indicam que a versão subespacial do método é mais rápida que a sua versão original em problemas onde o número de restrições é muito menor que o número de variáveis. No segundo trabalho, investiga-se a convergência e a complexidade de pior-caso do método de controle não-linear do tamanho do passo, recentemente proposto por Toint (Optim. Methods Softw. 28: 82-95, 2013) para problemas de otimização suave sem restrições. A convergência global do método é provada sob a hipótese de que a norma das Hessianas dos modelos pode crescer por uma quantidade constante a cada iteração. Além disso, limitantes para a complexidade de pior-caso são estimados. Os resultados obtidos são então estendidos para alguns métodos destinados a problemas de otimização composta não-suave e problemas de otimização multiobjetivo sem restrições. Por fim, no terceiro trabalho, um método de região de confiança sem derivadas é proposto para problemas de otimização composta não-suave. A convergência global do método é estabelecida e um limitante para a complexidade de pior-caso é obtido. A análise de complexidade é então especializada para o caso em que a função composta é uma função de penalidade exata, fornecendo assim um limitante de complexidade para problemas de otimização com restrições de igualdade quando a solução é obtida por um método de penalidade exata sem derivadas. Resultados numéricos preliminares com problemas minimax e com problemas de otimização com restrições de igualdade sugerem que o algoritmo proposto _e promissor. Palavras-chave: Métodos de Região de Confiança, Métodos de Regularização, Métodos Subespaciais, Análise de Complexidade, Otimização sem Derivadas.

Abstract: This thesis presents three works on nonlinear and nonconvex optimization. In the _rst work, a subspace version of the Powell-Yuan trust-region algorithm is proposed for equalityconstrained optimization problems. The main feature of the method presented is that, at each iteration, the Celis-Dennis-Tapia (CDT) subproblem is solved in a certain subspace, which reduces the computational e_ort necessary to compute the step. Preliminary numerical tests indicate that the subspace version of the method is faster than its original version on problems where the number of constraints is much lower than the number of variables. In the second work, it is investigated the convergence and the worst-case complexity of the nonlinear stepsize control algorithm recently proposed by Toint (Optim. Methods Softw. 28: 82-95, 2013) for smooth unconstrained optimization problems. The global convergence of the method is proved under the assumption that the Hessians of the models can grow by a constant amount at each iteration. Moreover, worst-case complexity bounds are estimated. The results obtained are extended to some algorithms for composite nonsmooth optimization problems and unconstrained multiobjective problems as well. Finally, in the third work, a derivative-free trust-region algorithm is proposed for composite nonsmooth optimization problems. The global convergence of the method is established and a worst-case complexity bound is obtained. The complexity analysis is then especialized to the case where the composite function is an exact penalty function, providing a worst-case complexity bound for equality-constrained optimization problems when the solution is computed using a derivative-free exact penalty algorithm. Preliminary numerical results with _nite minimax problems and with equality-constrained problems suggest that the proposed algorithm is promising. Keywords: Trust-region Methods, Regularization Methods, Subspace Methods, Complexity Analysis, Derivative-Free Optimization. xi