Augumented lagrangian methods with convergence under the constant positive linear dependence condition

Author(s)

Maria Laura Schuverdt

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica
• Defense date: 2006-08-03

Examining board members

José Mario Martínez Pérez; Alfredo Noel Iusem; Nelson Maculan Filho; Ernesto Julián Goldberg Birgin

• Advisor: Roberto Andreani; José Mario Martínez Pérez

Abstract

Contraint qualifications are useful tools in the convergence analysis of optimization methods. In this work we prove that the new constant positive linear dependence condition (CPLD) is a constraint qualification and we show that it is weaker than classic constraint qualifications, like the regularity, the Mangasarian-Fromovitz and the constant rank conditions. Moreover, we introduce an augmented Lagrangian algorithm for solving general nonlinear programming problems whose convergence result uses the CPLD condition. The proposed algorithm is developed for problems with two sets of constraints: a complex one, formed by the penalized constraints and a simple one, formed by the constraints that are verified for all the iterates generated along the process. The global convergence result establishes that if a limit point of the sequence generated by the algorithm satisfies the CPLD condition then this point is a stationary point of the original problem. Thus, the global convergence result is stronger than the previous results for more specific problems obtained using stronger constraint qualification, as the regularity. We also indicate suitable conditions under which we prove boundedness of the penalty parameter. The reliability of the approach was tested by means of an exhaustive comparison against LANCELOT, demonstrating that our method is more robust and efficient. Moreover, as an application of our algorithm when different constraints are incorporated, we introduce the resolution of Location Problems in which there exist many nonlinear constraints in the complex set. We show that, employing the Spectral Projected Gradient method for solving the subproblems, this class of problems with many variables and constraints is efficiently solved with moderate computational effort (AU)