Um algoritmo de filtros em optimização não linear: a admissibilidade independente da optimização

Abstract

O objectivo deste trabalho é a implementação de um algoritmo para resolução de problemas de optimização não linear com restrições, utilizando o método dos filtros numa abordagem de restauração inexacta (IR, do inglês Inexact Restoration). Na abordagem IR, existem duas fases totalmente independentes em cada iteração - a admissibilidade e a optimalidade. A primeira tem como objectivo, conduzir o processo iterativo na direcção da região admissível, i.e., encontrar um ponto que viole menos as restrições. A partir deste ponto intermédio, efectua-se a fase da optimalidade, consistindo na optimização da função objectivo, no espaço das restrições satisfeitas. Na fase da admissibilidade, resolve-se um problema de optimização linear, cuja função objectivo é o somatório da linearização das restrições violadas, e cujas restrições são a linearização das restrições verificadas. A fase da optimalidade, consiste na resolução de um problema de optimização quadrático, cuja função objectivo é uma aproximação quadrática a partir do ponto obtido na fase anterior e as restrições são a linearização das restrições satisfeitas no mesmo ponto. Para avaliar as aproximações à solução calculadas em cada iteração, é utilizado um esquema baseado no método dos filtros, nas duas fases do algoritmo. Este método substitui as funções mérito, baseadas em esquemas de penalidade, evitando os inconvenientes associados, tais como a estimação do parâmetro de penalidade e a não diferenciabilidade de algumas delas. Implementou-se o método dos filtros no âmbito da técnica de globalização de procura unidimensional. Nas experiências computacionais, resolveram-se problemas teste codificados em AMPL. Para inferir a importância da fase de admissibilidade, foram realizados testes com duas versões do algoritmo desenvolvido - uma com as duas fases, a segunda apenas com a fase de optimalidade. Comparou-se o algoritmo com os pacotes de software LOQO e NPSOL.

The purpose of this work is to develop an algorithm to solve nonlinear constrained optimization problems, using the filter method with inexact restoration (IR) approach. In the IR approach two independent phases are performed in each iteration - the feasibility and the optimality phases. The first one directs the iterative process into the feasible region, i.e., finds one point with less constraints violation. The optimality phase starts from this point and its goal is to optimize the objective function into the satisfied constraints space. At the feasibility phase an optimization problem is solved, whose objective function is the sum of the violated constraints linearization and the constraints are the satisfied constraints linearization. The optimality phase optimizes a quadratic approximation from the point obtained in the previous phase subject to the set of satisfied constraints in the same point. To evaluate the solution approximations in each iteration a scheme based on filter method is used in both phases of the algorithm. This method replaces the merit functions that are based on penalty schemes, avoiding the related difficulties such as the penalty parameter estimation and the nondiferentiability of some of them. The filter method is implemented in a context of line search globalization technique. A set of AMPL test problems is solved. To evaluate the relevance of the feasibility phase, two versions of the algorithm are tested - the first one, with feasibility and optimality phases and the second with optimality phase only. The algorithm developed is compared with LOQO and NPSOL software packages.