On local convergence of sequential quadratically-constrained quadratic-programming type methods,with an extension to variational problems

We consider the class of quadratically-constrained quadratic-programming methods in the framework extended from optimization to more general variational problems. Previously, in the optimization case, Anitescu (SIAM J. Optim. 12, 949–978, 2002) showed superlinear convergence of the primal sequence under the Mangasarian-Fromovitz constraint qualification and the quadratic growth condition. Quadratic convergence of the primal-dual sequence was established by Fukushima, Luo and Tseng (SIAM J. Optim. 13, 1098–1119, 2003) under the assumption of convexity, the Slater constraint qualification, and a strong second-order sufficient condition. We obtain a new local convergence result, which complements the above (it is neither stronger nor weaker): we prove primal-dual quadratic convergence under the linear independence constraint qualification, strict complementarity, and a second-order sufficiency condition. Additionally, our results apply to variational problems beyond the optimization case. Finally, we provide a necessary and sufficient condition for superlinear convergence of the primal sequence under a Dennis-Moré type condition. Research of the second author is partially supported by CNPq Grants 300734/95-6 and 471780/2003-0, by PRONEX–Optimization, and by FAPERJ.     

New Sequential Quadratically-Constrained Quadratic Programming Method of Feasible Directions and Its Convergence Rate

This paper discusses optimization problems with nonlinear inequality constraints and presents a new sequential quadratically-constrained quadratic programming (NSQCQP) method of feasible directions for solving such problems. At each iteration. the NSQCQP method solves only one subproblem which consists of a convex quadratic objective function, convex quadratic equality constraints, as well as a perturbation variable and yields a feasible direction of descent (improved direction). The following results on the NSQCQP are obtained: the subproblem solved at each iteration is feasible and solvable: the NSQCQP is globally convergent under the Mangasarian-Fromovitz constraint qualification (MFCQ); the improved direction can avoid the Maratos effect without the assumption of strict complementarity; the NSQCQP is superlinearly and quasiquadratically convergent under some weak assumptions without thestrict complementarity assumption and the linear independence constraint qualification (LICQ). Research supported by the National Natural Science Foundation of China Project 10261001 and Guangxi Science Foundation Projects 0236001 and 0249003. The author thanks two anonymous referees for valuable comments and suggestions on the original version of this paper.     

Quadratic Convergence of a Primal-Dual Interior Point Method for Degenerate Nonlinear Optimization Problems

Recently studies of numerical methods for degenerate nonlinear optimization problems have been attracted much attention. Several authors have discussed convergence properties without the linear independence constraint qualification and/or the strict complementarity condition. In this paper, we are concerned with quadratic convergence property of a primal-dual interior point method, in which Newton’s method is applied to the barrier KKT conditions. We assume that the second order sufficient condition and the linear independence of gradients of equality constraints hold at the solution, and that there exists a solution that satisfies the strict complementarity condition, and that multiplier iterates generated by our method for inequality constraints are uniformly bounded, which relaxes the linear independence constraint qualification. Uniform boundedness of multiplier iterates is satisfied if the Mangasarian-Fromovitz constraint qualification is assumed, for example. By using the stability theorem by Hager and Gowda (1999), and Wright (2001), the distance from the current point to the solution set is related to the residual of the KKT conditions.By controlling a barrier parameter and adopting a suitable line search procedure, we prove the quadratic convergence of the proposed algorithm.     

A quadratically approximate framework for constrained optimization,global and local convergence

This paper presents a quadratically approximate algorithm framework （QAAF） for solving general constrained optimization problems, which solves, at each iteration, a subproblem with quadratic objective function and quadratic equality together with inequality constraints. The global convergence of the algorithm framework is presented under the Mangasarian-Fromovitz constraint qualification （MFCQ）, and the conditions for superlinear and quadratic convergence of the algorithm framework are given under the MFCQ, the constant rank constraint qualification （CRCQ） as well as the strong second-order sufficiency conditions （SSOSC）. As an incidental result, the definition of an approximate KKT point is brought forward, and the global convergence of a sequence of approximate KKT points is analysed.     

On the rate of convergence of sequential quadratic programming with nondifferentiable exact penalty function in the presence of constraint degeneracy

We analyze the convergence of a sequential quadratic programming (SQP) method for nonlinear programming for the case in which the Jacobian of the active constraints is rank deficient at the solution and/or strict complementarity does not hold for some or any feasible Lagrange multipliers. We use a nondifferentiable exact penalty function, and we prove that the sequence generated by an SQP using a line search is locally R-linearly convergent if the matrix of the quadratic program is positive definite and constant over iterations, provided that the Mangasarian-Fromovitz constraint qualification and some second-order sufficiency conditions hold. Received: April 28, 1998 / Accepted: June 28, 2001?Published online April 12, 2002     

A sequential quadratically constrained quadratic programming method for unconstrained minimax problems

In this paper, a sequential quadratically constrained quadratic programming (SQCQP) method for unconstrained minimax problems is presented. At each iteration the SQCQP method solves a subproblem that involves convex quadratic inequality constraints and a convex quadratic objective function. The global convergence of the method is obtained under much weaker conditions without any constraint qualification. Under reasonable assumptions, we prove the strong convergence, superlinearly and quadratic convergence rate.     

Implications of the constant rank constraint qualification

This paper investigates properties of a parametric set defined by finitely many equality and inequality constraints under the constant rank constraint qualification (CRCQ). We show, under the CRCQ, that the indicator function of this set is prox-regular with compatible parametrization, that the set-valued map that assigns each parameter to the set defined by that parameter satisfies a continuity property similar to the Aubin property, and that the Euclidean projector onto this set is a piecewise smooth function. We also show in the absence of parameters that the CRCQ implies the Mangasarian-Fromovitz constraint qualification to hold in some alternative expression of the set.     

A MULTIDIMENSIONAL FILTER SQP ALGORITHM FOR NONLINEAR PROGRAMMING

We propose a multidimensional filter SQP algorithm. The multidimensional filter technique proposed by Gould et al. [SIAM J. Optim., 2005] is extended to solve constrained optimization problems. In our proposed algorithm, the constraints are partitioned into several parts, and the entry of our filter consists of these different parts. Not only the criteria for accepting a trial step would be relaxed, but the individual behavior of each part of constraints is considered. One feature is that the undesirable link between the objective function and the constraint violation in the filter acceptance criteria disappears. The other is that feasibility restoration phases are unnecessary because a consistent quadratic programming subproblem is used. We prove that our algorithm is globally convergent to KKT points under the constant positive generators (CPG) condition which is weaker than the well-known Mangasarian-Fromovitz constraint qualification (MFCQ) and the constant positive linear dependence (CPLD). Numerical results are presented to show the efficiency of the algorithm.     

A Robust SQP Method for Mathematical Programs with Linear Complementarity Constraints

The relationship between the mathematical program with linear complementarity constraints (MPLCC) and its inequality relaxation is studied. Based on this relationship, a new sequential quadratic programming (SQP) method is presented for solving the MPLCC. A certain SQP technique is introduced to deal with the possible infeasibility of quadratic programming subproblems. Global convergence results are derived without assuming the linear independence constraint qualification for MPEC, the nondegeneracy condition, and any feasibility condition of the quadratic programming subproblems. Preliminary numerical results are reported. Research is partially supported by Singapore-MIT Alliance and School of Business, National University of Singapore.     

Global convergence of modified augmented Lagrangian methods for nonlinear semidefinite programming

We investigate in this paper global convergence properties of the augmented Lagrangian method for nonlinear semidefinite programming (NLSDP). Four modified augmented Lagrangian methods for solving NLSDP based on different algorithmic strategies are proposed. Possibly infeasible limit points of the proposed methods are characterized. It is proved that feasible limit points that satisfy the Mangasarian-Fromovitz constraint qualification are KKT points of NLSDP without requiring the boundedness condition of the multipliers. Preliminary numerical results are reported to compare the performance of the modified augmented Lagrangian methods.     

A nonsmooth variant of the Mangasarian-Fromovitz constraint qualification

A unified view on constraint qualifications for nonsmooth equality and inequality constrained programs is presented. A fairly general constraint qualification for programs involving B-differential functions is given. Further specification to piecewise differentiable equality constraints and locally Lipschitz continuous inequality constraints yields a nonsmooth version of the Mangasarian-Fromovitz constraint qualification.This work was supported by the Deutsche Forschungsgemeinschaft, DFG-Grant No. Pa 219/5-1.     

Combining the regularization strategy and the SQP to solve MPCC — A MATLAB implementation

Mathematical Program with Complementarity Constraints (MPCC) plays a very important role in many fields such as engineering design, economic equilibrium, multilevel games, and mathematical programming theory itself. In theory its constraints fail to satisfy a standard constraint qualification such as the linear independence constraint qualification (LICQ) or the Mangasarian-Fromovitz constraint qualification (MFCQ) at any feasible point. As a result, the developed nonlinear programming theory may not be applied to MPCC class directly. Nowadays, a natural and popular approach is trying to find some suitable approximations of an MPCC so that it can be solved by solving a sequence of nonlinear programs.This work aims to solve the MPCC using nonlinear programming techniques, namely the SQP and the regularization scheme. Some algorithms with two iterative processes, the inner and the external, were developed. A set of AMPL problems from MacMPEC database (Leyffer, 2000) [8] were tested. The comparative analysis regarding performance of algorithms was carried out.     

On Error Bounds for Quasinormal Programs

The Mangasarian-Fromovitz constraint qualification is a central concept within the theory of constraint qualifications in nonlinear optimization. Nevertheless there are problems where this condition does not hold though other constraint qualifications can be fulfilled. One of such constraint qualifications is the so-called quasinormality by Hestenes. The well known error bound property (R-regularity) can also play the role of a general constraint qualification providing the existence of Lagrange multipliers. In this note we investigate the relation between some constraint qualifications and prove that quasinormality implies the error bound property, while the reciprocal is not true.     

Interior-point ℓ 2-penalty methods for nonlinear programming with strong global convergence properties

We propose two line search primal-dual interior-point methods for nonlinear programming that approximately solve a sequence of equality constrained barrier subproblems. To solve each subproblem, our methods apply a modified Newton method and use an ℓ₂-exact penalty function to attain feasibility. Our methods have strong global convergence properties under standard assumptions. Specifically, if the penalty parameter remains bounded, any limit point of the iterate sequence is either a Karush-Kuhn-Tucker (KKT) point of the barrier subproblem, or a Fritz-John (FJ) point of the original problem that fails to satisfy the Mangasarian-Fromovitz constraint qualification (MFCQ); if the penalty parameter tends to infinity, there is a limit point that is either an infeasible FJ point of the inequality constrained feasibility problem (an infeasible stationary point of the infeasibility measure if slack variables are added) or a FJ point of the original problem at which the MFCQ fails to hold. Numerical results are given that illustrate these outcomes. Research supported by the Presidential Fellowship of Columbia University. Research supported in part by NSF Grant DMS 01-04282, DOE Grant DE-FG02-92EQ25126 and DNR Grant N00014-03-0514.     

On Constraint Qualifications in Nonsmooth Optimization

We introduce extensions of the Mangasarian-Fromovitz and Abadie constraint qualifications to nonsmooth optimization problems with feasibility given by means of lower-level sets. We do not assume directional differentiability, but only upper semicontinuity of the defining functions. By deriving and reviewing primal first-order optimality conditions for nonsmooth problems, we motivate the formulations of the constraint qualifications. Then, we study their interrelation, and we show how they are related to the Slater condition for nonsmooth convex problems, to nonsmooth reverse-convex problems, to the stability of parametric feasible set mappings, and to alternative theorems for the derivation of dual first-order optimality conditions.In the literature on general semi-infinite programming problems, a number of formally different extensions of the Mangasarian-Fromovitz constraint qualification have been introduced recently under different structural assumptions. We show that all these extensions are unified by the constraint qualification presented here.     

On constraint qualifications

The linear independence constraint qualification (LICQ) and the weaker Mangasarian-Fromovitz constraint qualification (MFCQ) are well-known concepts in nonlinear optimization. A theorem is proved suggesting that the set of feasible points for which MFCQ essentially differs from LICQ is small in a specified sense. As an auxiliary result, it is shown that, under MFCQ, the constraint set (even in semi-infinite optimization) is locally representable in epigraph form.The author wishes to thank Professor H. T. Jongen for valuable advice.     

存零约束优化问题的序列二次方法北大核心CSCD

存零约束优化(MPSC)问题是近年来提出的一类新的优化问题,因存零约束的存在,使得常用的约束规范不满足,以至于现有算法的收敛性结果大多不能直接应用于该问题.应用序列二次规划(SQP)方法求解该问题,并证明在存零约束的线性独立约束规范下,子问题解序列的聚点为原问题的Karush-Kuhn-Tucker点.同时为了完善各稳定点之间的关系,证明了强平稳点与KKT点的等价性.最后数值结果表明,序列二次规划方法处理这类问题是可行的.     

Metric regularity of the feasible set mapping in semi-infinite optimization

For parametric systems of (finitely many) equations and (infinitely many) inequalities the well-known concept of metric regularity is shown to be equivalent to the so-called extended Mangasarian-Fromovitz constraint qualification. By this, a corresponding result obtained by Robinson for finite optimization problems my be transferred to semi-infinite optimization. For the proof a local epigraph representation of the constraint set is mainly used.     

均衡约束数学规划问题的一种新的约束规格

本文研究了均衡约束数学规划(MPEC)问题.利用其弱稳定点,获得了一种新的约束规格–MPEC的伪正规约束规格.用一种简单的方式,证明了该约束规格是介于MPEC-MFCQ(即MPEC,Mangasarian-Fromowitz约束规格)与MPEC-ACQ(即MPEC,Abadie约束规格)之间的约束规格,因此该约束规格也可以导出MPEC问题的M-稳定点.最后通过两个例子,说明了该约束规格与MPEC-MFCQ以及与MPEC-ACQ之间是严格的强弱关系.     

Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints

In this paper, the nonlinear minimax problems with inequality constraints are discussed, and a sequential quadratic programming (SQP) algorithm with a generalized monotone line search is presented. At each iteration, a feasible direction of descent is obtained by solving a quadratic programming (QP). To avoid the Maratos effect, a high order correction direction is achieved by solving another QP. As a result, the proposed algorithm has global and superlinear convergence. Especially, the global convergence is obtained under a weak Mangasarian–Fromovitz constraint qualification (MFCQ) instead of the linearly independent constraint qualification (LICQ). At last, its numerical effectiveness is demonstrated with test examples.