A global convergence theory for a general class of trust region algorithms for equality constrained optimization

[摘要] This work is concerned with global convergence results for a broad class of trust region sequential quadratic programming algorithms for the smooth nonlinear programming problem with equality constraints. The family of algorithms to which our results apply is characterized by very mild conditions on the normal and tangential components of the steps that its members generate. The normal component must predict a fraction of Cauchy decrease condition on the quadratic model of the linearized constraints. The tangential component must predict a fraction of Cauchy decrease condition on the quadratic model of the Lagrangian function associated with the problem in the tangent space of the constraints. The other main characteristic of this class of algorithms is that the trial step is evaluated for acceptance by using as merit function the Fletcher exact penalty function with a penalty parameter specified by El-Alem. The properties of the step together with the way that the penalty parameter is chosen allow us to establish that while the algorithm does not terminate, the sequence of trust region radii is bounded away from zero and the nondecreasing sequence of penalty parameters is eventually constant. These results lead us to conclude that the algorithms are well defined and that they are globally convergent. The class includes well-known algorithms based on the Celis-Dennis-Tapia subproblem and on the Vardi subproblem. As an example we present an algorithm which can be viewed as a generalization of the Steihaug-Toint dogleg method for the unconstrained case. It is based on a quadratic programming algorithm that uses as feasible point a step in the normal direction to the tangent space of the constraints and then does feasible conjugate reduced-gradient steps to solve the quadratic program. This algorithm should cope quite well with large problems.

[发布机构] Rice University