Quasi-Newton acceleration for constrained minimization problems

Sistemas de Otimalidade (ou Sistemas KKT) são sistemas formados pelas condições primais-duais estacionárias para a solução de problemas de otimização. Sob hipóteses adequadas (condições de qualificação), os minimizadores locais de um problema de minimização satisfarão as equações e inequações KKT; entretanto, infelizmente, muitos outros pontos estacionários (incluindo maximizadores) também são soluções desse sistema não linear. Por essa razão, os métodos destinados à resolução de problemas de programação não-linear fazem uso constante da estrutura de minimização, e o uso simples de métodos destinados à resolução de sistemas não-lineares podem gerar soluções espúrias. Todavia, caso o método destinado à resolução do sistema KKT tenha um ponto inicial situado na região de atração para um minimizador, esse método pode vir a ser muito eficiente. Neste trabalho, os métodos quase-Newton para a resolução de sistemas não-lineares são usados como aceleradores de algoritmos de programação não-linear (Lagrangiano Aumentado) com restrições de igualdade, desigualdade e caixa. Utilizamos como acelerador o método simétrico inverso de correção de posto um (ISR1), o qual realiza reínicios periódicos e faz uso das estruturas esparsas das matrizes para armazenamento. São demonstrados resultados de convergência e são realizados vários experimentos numéricos que comprovam a eficiência desta estratégia para problemas de minimização com restrições de igualdade, e indicam outros caminhos para problemas de minimização com restrições gerais (igualdade, desigualdade e caixa)Optimality (or KKT) systems arise as primal-dual stationarity conditions for constrained optimization problems. Under suitable constraint qualifications, local minimizers satisfy KKT equations but, unfortunately, many other stationary points (including, perhaps, maximizers) may solve these nonlinear systems too. For this reason, nonlinear-programming solvers make strong use of the minimization structure and the naive use of nonlinear-system solvers in optimization may lead to spurious solutions. Nevertheless, in the basin of attraction of a minimizer, nonlinear-system solvers may be quite efficient. In this work quasi-Newton methods for solving nonlinear systems are used as accelerators of nonlinear-programming (augmented Lagrangian) algorithms. A periodically-restarted memoryless symmetric rank-one (SRI) correction method is introduced for that purpose. Convergence results are given. For problems with only equality constraints, numerical experiments that confirm that the acceleration is effective are presented. A bunch of problems with equalities, inequalities and box constraints is tested and several comments and suggestions for further work are presente