Preprint C70/2008
LOCAL CONVERGENCE OF STABILIZED SEQUENTIAL QUADRATIC PROGRAMMING AND SEQUENTIAL QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMMING METHODS, AND THEIR EXTENSIONS TO VARIATIONAL PROBLEMS
Damian R. Fernández Ferreyra
Keywords: Karush-Kuhn-Tucker system | variational inequalities | Newton methods.
This work is devoted to the analysis of local convergence of some recently proposed Newton--type methods for solving optimization problems. We also develop natural extensions of those techniques to the setting of variational problems. We emphasize that all results are new already in the optimization setting, while variational extensions can be considered as additional contributions. The first method considered is the stabilized Sequential Quadratic Programming (sSQP) algorithm, proposed by S.J. Wright and further studied by W.W. Hager, by A. Fischer, and by S.J. Wright. This method has been developed for preserving superlinear/quadratic convergence in the case of nonunique Lagrange multipliers (i.e., degenerate constraints), which is a challenging problem in contemporary optimization. Previously, convergence of sSQP was proven either under the Mangasarian--Fromovitz constraint qualification and the second-order sufficient condition for optimality, or under the strong second-order sufficient condition for optimality. We prove primal-dual quadratic convergence assuming only the second-order sufficient condition for optimality, without any constraint qualification assumptions, thus improving significantly over any of the previous results. In addition, we introduce a natural extension of sSQP techniques to the variational setting. We show also that in the variational setting, under a suitable second-order condition, the so-called natural residual provides a local error bound for the solution set of the associated Karush--Kuhn--Tucker (KKT) system. This is the first error bound for variational KKT systems that does not assume anything about the constraints of the underlying variational problem. The second method considered is the Sequential Quadratically Constrained Quadratic Programming (SQCQP) algorithm, studied by M. Anitescu, and by M. Fukushima, Z.-Q. Luo and P. Tseng. Previously, convergence of SQCQP was proven either under the Mangasarian--Fromovitz constraint qualification and the quadratic growth condition, or under the convexity assumptions, the Slater constraint qualification and the strong second-order sufficient condition for optimality. We prove a new primal-dual quadratic convergence result assuming the linear independence constraint qualification, strict complementarity, and the usual second-order sufficient condition for optimality. This result is complementary to the two previous ones, being neither weaker nor stronger. In addition, we obtain superlinear convergence of the primal sequence under a Dennis-Moré type condition, as well as extend the method to variational problems.