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.     

On the Guignard constraint qualification for mathematical programs with equilibrium constraints

We recapitulate the well-known fact that most of the standard constraint qualifications are violated for mathematical programs with equilibrium constraints (MPECs). We go on to show that the Abadie constraint qualification is only satisfied in fairly restrictive circumstances. In order to avoid this problem, we fall back on the Guignard constraint qualification (GCQ). We examine its general properties and clarify the position it occupies in the context of MPECs. We show that strong stationarity is a necessary optimality condition under GCQ. Also, we present several sufficient conditions for GCQ, showing that it is usually satisfied for MPECs.     

On M-stationary points for mathematical programs with equilibrium constraints

Mathematical programs with equilibrium constraints are optimization problems which violate most of the standard constraint qualifications. Hence the usual Karush-Kuhn-Tucker conditions cannot be viewed as first order optimality conditions unless relatively strong assumptions are satisfied. This observation has lead to a number of weaker first order conditions, with M-stationarity being the strongest among these weaker conditions. Here we show that M-stationarity is a first order optimality condition under a very weak Abadie-type constraint qualification. Our approach is inspired by the methodology employed by Jane Ye, who proved the same result using results from optimization problems with variational inequality constraints. In the course of our investigation, several concepts are translated to an MPEC setting, yielding in particular a very strong exact penalization result.     

Second-Order Optimality Conditions for Mathematical Programs with Equilibrium Constraints

We study second-order optimality conditions for mathematical programs with equilibrium constraints (MPEC). Firstly, we improve some second-order optimality conditions for standard nonlinear programming problems using some newly discovered constraint qualifications in the literature, and apply them to MPEC. Then, we introduce some MPEC variants of these new constraint qualifications, which are all weaker than the MPEC linear independence constraint qualification, and derive several second-order optimality conditions for MPEC under the new MPEC constraint qualifications. Finally, we discuss the isolatedness of local minimizers for MPEC under very weak conditions.     

均衡约束数学规划的约束规格和最优性条件综述

约束规格在约束优化问题的最优性条件中起着重要的作用,介绍了近几年国际上关于均衡约束数学规划(简记为MPEC)的约束规格以及最优性条件的研究成果, 包括以下主要内容: (1) MPEC常用的约束规格(如线性无关约束规格 (MPEC-LICQ)、Mangasarian-Fromovitz约束规格 (MPEC-MFCQ)等)和新的约束规格(如恒秩约束规格、常数正线性相关约束规格等), 以及它们之间的关系; (2) MPEC常用的稳定点; (3) MPEC的最优性条件. 最后还对MPEC的约束规格和最优性条件的研究前景进行了探讨.     

Optimality conditions for nonsmooth mathematical programs with equilibrium constraints,using convexificators

In this paper, we deal with constraint qualifications, stationary concepts and optimality conditions for a nonsmooth mathematical program with equilibrium constraints (MPEC). The main tool in our study is the notion of convexificator. Using this notion, standard and MPEC Abadie and several other constraint qualifications are proposed and a comparison between them is presented. We also define nonsmooth stationary conditions based on the convexificators. In particular, we show that GS-stationary is the first-order optimality condition under generalized standard Abadie constraint qualification. Finally, sufficient conditions for global or local optimality are derived under some MPEC generalized convexity assumptions.     

隐互补约束优化问题的磨光SQP算法

本文提出了一类隐互补约束优化问题的磨光SQP算法.首先,我们给出了这类优化问题的最优性和约束规范性条件.然后,在适当假设条件下,我们证明了算法具有全局收敛性.     

A Fritz John Approach to First Order Optimality Conditions for Mathematical Programs with Equilibrium Constraints

Mathematical programs with equilibrium constraints (MPECs) are nonlinear programs which do not satisfy any of the common constraint qualifications. In order to obtain first order optimality conditions, constraint qualifications tailored to MPECs have been developed and researched in the past. This has been done by falling back on technical proofs or results from nonsmooth analysis. In this article, we use a completely different approach and show how the standard Fritz John conditions may be used in order to obtain short and elementary proofs for the most important optimality conditions for MPECs. As a by-product, we obtain a new stationarity concept.     

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.     

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

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

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.      

Stationary conditions for mathematical programs with vanishing constraints using weak constraint qualifications

We consider a class of optimization problems that is called a mathematical program with vanishing constraints (MPVC for short). This class has some similarities to mathematical programs with equilibrium constraints (MPECs for short), and typically violates standard constraint qualifications, hence the well-known Karush-Kuhn-Tucker conditions do not provide necessary optimality criteria. In order to obtain reasonable first order conditions under very weak assumptions, we introduce several MPVC-tailored constraint qualifications, discuss their relation, and prove an optimality condition which may be viewed as the counterpart of what is called M-stationarity in the MPEC-field.     

New Constraint Qualifications and Optimality Conditions for Second Order Cone Programs

We introduce three new constraint qualifications for nonlinear second order cone programming problems that we call constant rank constraint qualification, relaxed constant rank constraint qualification and constant rank of the subspace component condition. Our development is inspired by the corresponding constraint qualifications for nonlinear programming problems. We provide proofs and examples that show the relations of the three new constraint qualifications with other known constraint qualifications. In particular, the new constraint qualifications neither imply nor are implied by Robinson’s constraint qualification, but they are stronger than Abadie’s constraint qualification. First order necessary optimality conditions are shown to hold under the three new constraint qualifications, whereas the second order necessary conditions hold for two of them, the constant rank constraint qualification and the relaxed constant rank constraint qualification.

     

Nonsmooth multiobjective programming and constraint qualifications

We consider a nonsmooth multiobjective programming problem with inequality and set constraints. By using the notion of convexificator, we extend the Abadie constraint qualification, and derive the strong Kuhn-Tucker necessary optimality conditions. Some other constraint qualifications have been generalized and their interrelations are investigated.     

Enhanced Karush–Kuhn–Tucker Conditions for Mathematical Programs with Equilibrium Constraints

In this paper, we study necessary optimality conditions for nonsmooth mathematical programs with equilibrium constraints. We first show that, unlike the smooth case, the mathematical program with equilibrium constraints linear independent constraint qualification is not a constraint qualification for the strong stationary condition when the objective function is nonsmooth. We then focus on the study of the enhanced version of the Mordukhovich stationary condition, which is a weaker optimality condition than the strong stationary condition. We introduce the quasi-normality and several other new constraint qualifications and show that the enhanced Mordukhovich stationary condition holds under them. Finally, we prove that quasi-normality with regularity implies the existence of a local error bound.     

A Relaxed Constant Positive Linear Dependence Constraint Qualification for Mathematical Programs with Equilibrium Constraints

We introduce a relaxed version of the constant positive linear dependence constraint qualification for mathematical programs with equilibrium constraints (MPEC). This condition is weaker but easier to check than the MPEC constant positive linear dependence constraint qualification, and stronger than the MPEC Abadie constraint qualification (thus, it is an MPEC constraint qualification for M-stationarity). Neither the new constraint qualification implies the MPEC generalized quasinormality, nor the MPEC generalized quasinormality implies the new constraint qualification. The new one ensures the validity of the local MPEC error bound under certain additional assumptions. We also have improved some recent results on the existence of a local error bound in the standard nonlinear program.     

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.     

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

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

Some kind of Pareto stationarity for multiobjective problems with equilibrium constraints

ABSTRACT

In this paper, we derive some optimality and stationarity conditions for a multiobjective problem with equilibrium constraints (MOPEC). In particular, under a generalized Guignard constraint qualification, we show that any locally Pareto optimal solution of MOPEC must satisfy the strong Pareto Kuhn-Tucker optimality conditions. We also prove that the generalized Guignard constraint qualification is the weakest constraint qualification for the strong Pareto Kuhn-Tucker optimality. Furthermore, under certain convexity or generalized convexity assumptions, we show that the strong Pareto Kuhn-Tucker optimality conditions are also sufficient for several popular locally Pareto-type optimality conditions for MOPEC.     

Multiobjective Problems: Enhanced Necessary Conditions and New Constraint Qualifications through Convexificators

In this paper, we study necessary optimality conditions for local Pareto and weak Pareto solutions of multiobjective problems involving inequality and equality constraints in terms of convexificators. We develop the enhanced Karush–Kuhn–Tucker conditions and introduce the associated pseudonormality and quasinormality conditions. We also introduce several other new constraint qualifications which entirely depend on the feasible set. Then a connecting link between these constraint qualifications is presented. Moreover, we provide several examples that clarify the interrelations between the different results that we have established.