On the sequential quadratically constrained quadratic programming methods

Mikhail Solodov

Keywords: Quadratically constrained quadratic programming | nonsmooth penalty function | Maratos effect.

An iteration of the sequential quadratically constrained quadratic programming method (SQCQP) consists of minimizing a quadratic approximation of the objective function subject to quadratic approximation of the constraints, followed by a linesearch in the obtained direction. Methods of this class are receiving attention due to the development of efficient interior point techniques for solving subproblems with this structure, via formulating them as second-order cone programs. Recently, Fukushima, Luo and Tseng \cite{flt:03} proposed a SQCQP method for convex minimization with twice continuously differentiable data. Their method possesses global and locally quadratic convergence, and it is free of the Maratos effect. The feasibility of subproblems in their method is enforced by switching between the linear and quadratic approximations of the constraints. This strategy requires computing a strictly feasible point, as well as choosing some further parameters. We propose a SQCQP method where feasibility of subproblems is ensured by introducing a slack variable and, hence, is automatic. In addition, we do not assume convexity of the objective function or twice differentiability of the problem data. While our method has all the desirable convergence properties, it is easier to implement. Among other things, it does not require computing a strictly feasible point, which is a nontrivial task. In addition, its global convergence requires weaker assumptions.

Anexos:

• r.ps