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. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-04052011-114740 |
| Date | 11 March 2011 |
| Creators | Ellen Hidemi Fukuda |
| Contributors | Paulo José da Silva e Silva, Roberto Andreani, Carlos Humes Junior, Elizabeth Wegner Karas, José Mario Martinez Perez |
| Publisher | Universidade de São Paulo, Matemática Aplicada, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds