Programação quadrática sequencial aplicada a problemas de optimização não linear com restrições de igualdade

Dissertação de mestrado em Matemática, área de especialização em Matemática e Aplicações à MecânicaO trabalho apresentado nesta tese considera várias implementações do método da programação quadrática sequencial (PQS) com procura unidimensional, para a resolução de problemas de optimização não linear com restrições de igualdade. As várias versões de implementação do método da PQS propostas estão relacionadas com as modificações que tem que ser introduzidas na estratégia PQS, para que esta seja capaz de convergir a partir de qualquer ponto inicial e para qualquer problema não convexo. Para se garantir que as direcções PQS sejam direcções de descida para uma dada função mérito, uma condição é que a Hessiana da Lagrangeana do modelo quadrático, k W , seja definida positiva. Para isso, consideram-se várias formulações do modelo quadrático que garantem a sua adequação no contexto da procura unidimensional. Assim, quando k W não é definida positiva, esta matriz é substituída por uma aproximação quasi-Newton k B definida positiva, ou é modificada directamente durante o processo de factorização. Outra possibilidade, é definir k W como a Hessiana de uma função Lagrangeana aumentada, que possui certas propriedades de convexidade. Para que o método da PQS convirja a partir de qualquer ponto inicial são propostas duas funções mérito importantes, a função de penalidade 2 l e a função Lagrangeana aumentada de Fletcher. Mostra-se que as direcções PQS são direcções de descida para estas funções. Os resultados computacionais mostram que a versão de implementação do método da PQS que dá melhores resultados é a que considera a aproximação quasi-Newton BFGS à inversa da Hessiana da Lagrangeana, usa para matriz inicial a matriz identidade, faz a resolução do sistema KKT pelo método dual e usa como função mérito a função Lagrangeana aumentada de Fletcher. O mesmo desempenho é obtido com a implementação que considera a aproximação quasi-Newton BFGS à inversa da Hessiana da Lagrangeana aumentada.This work considers several implementations of the sequential quadratic programming (SQP) method with line search, for solving nonlinear equality constrained problems. The several versions of implementation of the SQP method proposed, are related with modifications that must be introduced on the SQP strategy, so that it is able to converge from remote starting points and on nonconvex problems. To ensure that the SQP directions are descent directions for a given merit function, one condition is that the Hessian of the Lagrangian of the quadratic model, , k W is positive definite. For this, several formulations of the quadratic model that are adequate in the context of the line search are considered. Hence, when k W is not positive definite, this matrix is replaced by a positive definite quasi-Newton approximation, , k B or it is modified directly during the process of matrix factorization. Another possibility is to define k W as the Hessian of an augmented Lagrangian function having certain convexity properties. For the SQP method to be able to converge from remote starting points two merit function are proposed, the 2 l penalty function and the Fletcher’s augmented Lagrangian function. It is also proved that the SQP directions are descent directions for these merit functions. Computational experiments show that the implementation of the SQP method using quasi-Newton BFGS approximation to the inverse of the Hessian of the Lagrangian, choosing the initial matrix as the identity matrix, solve the KKT system by the dual method, and with the Fletcher’s augmented Lagrangian function as the merit function has better performance. The same performance is obtained with the implementation that uses the quasi-Newton BFGS approximation to the inverse of the Hessian of the augmented Lagrangian