Doctoral Thesis
DOI
https://doi.org/10.11606/T.45.2011.tde-04052011-114740
Document
Author
Full name
Ellen Hidemi Fukuda
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2011
Supervisor
Committee
Silva, Paulo José da Silva e (President)
Andreani, Roberto
Humes Junior, Carlos
Karas, Elizabeth Wegner
Perez, José Mario Martinez
Title in Portuguese
Tópicos em penalidades exatas diferenciáveis
Keywords in Portuguese
estimador de multiplicadores
método de Newton semi-suave
penalidades exatas
programação não linear
reformulação de sistemas KKT.
Abstract in Portuguese
Durante as décadas de 70 e 80, desenvolveram-se métodos baseados em penalidades exatas diferenciáveis para resolver problemas de otimização não linear com restrições. Uma desvantagem dessas penalidades é que seus gradientes contêm termos de segunda ordem em suas fórmulas, o que impede a utilização de métodos do tipo Newton para resolver o problema. Para contornar essa dificuldade, utilizamos uma ideia de construção de penalidade exata para desigualdades variacionais, introduzida recentemente por André e Silva. Essa construção consiste em incorporar um estimador de multiplicadores, proposto por Glad e Polak, no lagrangiano aumentado para desigualdades variacionais. Nesse trabalho, estendemos o estimador de multiplicadores para restrições gerais de igualdade e desigualdade, e enfraquecemos a hipótese de regularidade. Como resultado, obtemos uma função penalidade exata continuamente diferenciável e uma nova reformulação do sistema KKT associado a problemas não lineares. A estrutura dessa reformulação permite a utilização do método de Newton semi-suave, e a taxa de convergência local superlinear pode ser provada. Além disso, verificamos que a penalidade exata construída pode ser usada para globalizar o método, levando a uma abordagem do tipo Gauss-Newton. Por fim, realizamos experimentos numéricos baseando-se na coleção CUTE de problemas de teste.
Title in English
Topics in differentiable exact penalties
Keywords in English
exact penalties
multipliers estimate
nonlinear programming
reformulation of KKT systems
semismooth Newton method.
Abstract in English
During the 1970's and 1980's, methods based on differentiable exact penalty functions were developed to solve constrained optimization problems. One drawback of these functions is that they contain second-order terms in their gradient's formula, which do not allow the use of Newton-type methods. To overcome such difficulty, we use an idea for construction of exact penalties for variational inequalities, introduced recently by André and Silva. This construction consists on incorporating a multipliers estimate, proposed by Glad and Polak, in the augmented Lagrangian function for variational inequalities. In this work, we extend the multipliers estimate to deal with both equality and inequality constraints and we weaken the regularity assumption. As a result, we obtain a continuous differentiable exact penalty function and a new equation reformulation of the KKT system associated to nonlinear problems. The formula of such reformulation allows the use of semismooth Newton method, and the local superlinear convergence rate can be also proved. Besides, we note that the exact penalty function can be used to globalize the method, resulting in a Gauss-Newton-type approach. We conclude with some numerical experiments using the collection of test problems CUTE.
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2011-06-07