Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications

We consider a difficult class of optimization problems that we call a mathematical program with vanishing constraints. Problems of this kind arise in various applications including optimal topology design problems of mechanical structures. We show that some standard constraint qualifications like LICQ and MFCQ usually do not hold at a local minimum of our program, whereas the Abadie constraint qualification is sometimes satisfied. We also introduce a suitable modification of the standard Abadie constraint qualification as well as a corresponding optimality condition, and show that this modified constraint qualification holds under fairly mild assumptions. We also discuss the relation between our class of optimization problems with vanishing constraints and a mathematical program with equilibrium constraints.     

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.     

约束优化问题中常用的约束规范及其相互关系

详细分析了约束优化问题中几种常见的约束规范,如L ICQ,SM FCQ,M FCQ,CRCQ,CPLD以及伪正规,拟正规和拟正则约束规范.针对等式和不等式约束问题讨论了它们与拉格朗日乘子的存在性及其性质之间的关系,给出了各种约束规范之间的关系图.特别通过反例,说明了WM FCQ在含等式约束的问题中不是一种约束规范.     

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.     

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.     

Global convergence of a robust filter SQP algorithm

We present a robust filter SQP algorithm for solving constrained optimization problems. This algorithm is based on the modified quadratic programming proposed by Burke to avoid the infeasibility of the quadratic programming subproblem at each iteration. Compared with other filter SQP algorithms, our algorithm does not require any restoration phase procedure which may spend a large amount of computation. The main advantage of our algorithm is that it is globally convergent without requiring strong constraint qualifications, such as Mangasarian–Fromovitz constraint qualification (MFCQ) and the constant rank constraint qualification (CRCQ). Furthermore, the feasible limit points of the sequence generated by our algorithm are proven to be the KKT points if some weaker conditions are satisfied. Numerical results are also presented to show the efficiency of the algorithm.     

紧约束函数梯度向量线性无关约束规范下Kuhn-Tucker条件的一个简洁证明

在紧约束函数的梯度向量线性无关这一约束规范下,运用隐函数定理和直交投影的性质,给出约束最优化问题Kuhn-Tucker一阶必要条件的一个简洁证明.     

Active set algorithm for mathematical programs with linear complementarity constraints

In the paper, an incomplete active set algorithm is given for mathematical programs with linear complementarity constraints (MPLCC). At each iteration, a finite number of inner-iterations are contained for approximately solving the relaxed nonlinear optimization problem. If the feasible region of the MPLCC is bounded, under the uniform linear independence constraint qualification (LICQ), any cluster point of the sequence generated from the algorithm is a B-stationary point of the MPLCC. Preliminary numerical tests show that the algorithm is promising.     

一类稀疏约束非线性规划的约束规格

研究一类带有闭凸集约束的稀疏约束非线性规划问题,这类问题在变量选择、模式识别、投资组合等领域具有广泛的应用.首先引进了限制性Slater约束规格的概念,证明了该约束规格强于限制性M-F约束规格,然后在此约束规格成立的条件下,分析了其局部最优解成立的充分和必要条件.最后,对约束集合的两种具体形式,指出限制性Slater约束规格必满足,并给出了一阶必要性条件的具体表达形式.     

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.     

Convexificators and boundedness of the Kuhn–Tucker multipliers set

In this paper we consider a nonsmooth optimization problem with equality, inequality and set constraints. We propose new constraint qualifications and Kuhn–Tucker type necessary optimality conditions for this problem involving locally Lipschitz functions. The main tool of our approach is the notion of convexificators. We introduce a nonsmooth version of the Mangasarian–Fromovitz constraint qualification and show that this constraint qualification is necessary and sufficient for the Kuhn–Tucker multipliers set to be nonempty and bounded.     

Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints

In this paper we consider a mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with complementarity constraints. Various stationary conditions for MPECs exist in literature due to different reformulations. We give a simple proof to the M-stationary condition and show that it is sufficient for global or local optimality under some MPEC generalized convexity assumptions. Moreover, we propose new constraint qualifications for M-stationary conditions to hold. These new constraint qualifications include piecewise MFCQ, piecewise Slater condition, MPEC weak reverse convex constraint qualification, MPEC Arrow-Hurwicz-Uzawa constraint qualification, MPEC Zangwill constraint qualification, MPEC Kuhn-Tucker constraint qualification, and MPEC Abadie constraint qualification.     

A linear programming proof of the second order conditions of non-linear programming

In this note we give a new, simple proof of the standard first and second order necessary conditions, under the Mangasarian–Fromovitz constraint qualification (MFCQ), for non-linear programming problems. We work under a mild constraint qualification, which is implied by MFCQ. This makes it possible to reduce the proof to the relatively easy case of inequality constraints only under MFCQ. This reduction makes use of relaxation of inequality constraints and it makes use of a penalty function. The new proof is based on the duality theorem for linear programming; the proofs in the literature are based on results of mathematical analysis. This paper completes the work in a recent note of Birbil et al. where a linear programming proof of the first order necessary conditions has been given, using relaxation of equality constraints.     

On Constraint Qualification in Multiobjective Optimization Problems: Semidifferentiable Case

Some versions of constraint qualifications in the semidifferentiable case are considered for a multiobjective optimization problem with inequality constraints. A Maeda-type constraint qualification is given and Kuhn–Tucker-type necessary conditions for efficiency are obtained. In addition, some conditions that ensure the Maeda-type constraint qualification are stated.     

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.     

Partial Exact Penalty for Mathematical Programs with Equilibrium Constraints

It is well known that mathematical programs with equilibrium constraints (MPEC) violate the standard constraint qualifications such as Mangasarian–Fromovitz constraint qualification (MFCQ) and hence the usual Karush–Kuhn–Tucker conditions cannot be used as stationary conditions unless relatively strong assumptions are satisfied. This observation has led to a number of weaker stationary conditions, with Mordukhovich stationary (M-stationary) condition being the strongest among the weaker conditions. In nonlinear programming, it is known that MFCQ leads to an exact penalization. In this paper we show that MPEC GMFCQ, an MPEC variant of MFCQ, leads to a partial exact penalty where all the constraints except a simple linear complementarity constraint are moved to the objective function. The partial exact penalty function, however, is nonsmooth. By smoothing the partial exact penalty function, we design an algorithm which is shown to be globally convergent to an M-stationary point under an extended version of the MPEC GMFCQ.     

Book Review of Introduction to the theory of toeplitz operators with infinite index,Vladimir Dybin and Sergei M. Grudsky (Translated from Russian by Andrei Jacob), operator theory: advances and applications,Birkhäuser Verlag,Basel-Boston-Berlin, 2002, volume 137, 299 pages. ISBN 3-7643-6728-8.

We consider a special class of optimization problems that we call a Mathematical Programme with Vanishing Constraints. It has a number of important applications in structural and topology optimization, but typically does not satisfy standard constraint qualifications like the linear independence and the Mangasarian–Fromovitz constraint qualification. We therefore investigate the Abadie and Guignard constraint qualifications in more detail. In particular, it follows from our results that also the Abadie constraint qualification is typically not satisfied, whereas the Guignard constraint qualification holds under fairly mild assumptions for our particular class of optimization problems.     

A method combining norm-relaxed QP subproblems with systems of linear equations for constrained optimization

Based on the ideas of norm-relaxed sequential quadratic programming (SQP) method and the strongly sub-feasible direction method, we propose a new SQP algorithm for the solution of nonlinear inequality constrained optimization. Unlike the previous work, at each iteration, the norm-relaxed quadratic programming subproblem (NRQPS) in our algorithm only consists of the constraints corresponding to an estimate of the active set, and the high-order correction direction (used to avoid the Maratos effect) is obtained by solving a system of linear equations (SLE) which also only consists of such a subset of constraints and gradients. Moreover, the line search technique can effectively combine the initialization process with the optimization process, and therefore (if the starting point is not feasible) the iteration points always get into the feasible set after a finite number of iterations. The global convergence is proved under the Mangasarian–Fromovitz constraint qualification (MFCQ), and the superlinear convergence is obtained without assuming the strict complementarity. Finally, the numerical experiments show that the proposed algorithm is effective and promising for the test problems.     

Necessary optimality conditions for a class of nonsmooth vector optimization

The Kuhn-Tucker type necessary conditions of weak efficiency are given for the problem of minimizing a vector function whose each component is the sum of a differentiable function and a convex function, subject to a set of differentiable nonlinear inequalities on a convex subset C of ℝ ⁿ , under the conditions similar to the Abadie constraint qualification, or the Kuhn-Tucker constraint qualification, or the Arrow-Hurwicz-Uzawa constraint qualification. Supported by the National Natural Science Foundation of China (No. 70671064, No. 60673177), the Province Natural Science Foundation of Zhejiang (No.Y7080184) and the Education Department Foundation of Zhejiang Province (No. 20070306).     

Optimality Conditions for Disjunctive Programs with Application to Mathematical Programs with Equilibrium Constraints

We consider optimization problems with a disjunctive structure of the feasible set. Using Guignard-type constraint qualifications for these optimization problems and exploiting some results for the limiting normal cone by Mordukhovich, we derive different optimality conditions. Furthermore, we specialize these results to mathematical programs with equilibrium constraints. In particular, we show that a new constraint qualification, weaker than any other constraint qualification used in the literature, is enough in order to show that a local minimum results in a so-called M-stationary point. Additional assumptions are also discussed which guarantee that such an M-stationary point is in fact a strongly stationary point.