Abadie-Type Constraint Qualification for Mathematical Programs with Equilibrium Constraints

Mathematical programs with equilibrium constraints (MPEC) are nonlinear programs which do not satisfy any of the common constraint qualifications (CQ). In order to obtain first-order optimality conditions, constraint qualifications tailored to the MPECs have been developed and researched in the past. In this paper, we introduce a new Abadie-type constraint qualification for MPECs. We investigate sufficient conditions for this new CQ, discuss its relationship to several existing MPEC constraint qualifications, and introduce a new Slater-type constraint qualifications. Finally, we prove a new stationarity concept to be a necessary optimality condition under our new Abadie-type CQ.Communicated by Z. Q. Luo     

Complementarity Constraint Qualifications and Simplified B-Stationarity Conditions for Mathematical Programs with Equilibrium Constraints

With the aid of some novel complementarity constraint qualifications, we derive some simplified primal-dual characterizations of a B-stationary point for a mathematical program with complementarity constraints (MPEC). The approach is based on a locally equivalent piecewise formulation of such a program near a feasible point. The simplified results, which rely heavily on a careful dissection and improved understanding of the tangent cone of the feasible region of the program, bypass the combinatorial characterization that is intrinsic to B-stationarity.     

Merit-Function Piecewise SQP Algorithm for Mathematical Programs with Equilibrium Constraints

We propose a merit-function piecewise SQP algorithm for mathematical programs with equilibrium constraints (MPEC) formulated as mathematical programs with complementarity constraints. Under mild conditions, the new algorithm is globally convergent to a piecewise stationary point. Moreover, if the partial MPEC linear independence constraint qualification (LICQ) is satisfied at the accumulation point, then the accumulation point is an S-stationary point. The research of the first author was supported by the National Natural Science Foundation of China under grants 10571177 and 70271014. The research of the second author was partially supported by NSERC.     

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.      

Convergence of an Inexact Smoothing Method for Mathematical Programs with Equilibrium Constraints

In this paper, we propose an inexact smoothing continuation method for mathematical problem with complementarity constraints. Under suitable conditions, we establish the convergence of the proposed method by showing that any accumulation point of the generated sequence is a B-stationary point of the problem.     

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 Class of Quadratic Programs with Linear Complementarity Constraints

We consider a class of quadratic programs with linear complementarity constraints (QPLCC) which belong to mathematical programs with equilibrium constraints (MPEC). We investigate various stationary conditions and present new and strong necessary and sufficient conditions for global and local optimality. Furthermore, we propose a Newton-like method to find an M-stationary point in finite steps without MEPC linear independence constraint qualification. The research of this author is partially supported by NSERC, and Research Grand Council of Hong Kong.     

New Relaxation Method for Mathematical Programs with Complementarity Constraints

In this paper, we present a new relaxation method for mathematical programs with complementarity constraints. Based on the fact that a variational inequality problem defined on a simplex can be represented by a finite number of inequalities, we use an expansive simplex instead of the nonnegative orthant involved in the complementarity constraints. We then remove some inequalities and obtain a standard nonlinear program. We show that the linear independence constraint qualification or the Mangasarian–Fromovitz constraint qualification holds for the relaxed problem under some mild conditions. We consider also a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is a weakly stationary point of the original problem and that, if the function involved in the complementarity constraints does not vanish at this point, it is C-stationary. We obtain also some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices of the Lagrangian functions of the relaxed problems are new and can be verified easily. Our limited numerical experience indicates that the proposed approach is promising.     

Existence Theorems of Quasivariational Inclusion Problems with Applications to Bilevel Problems and Mathematical Programs with Equilibrium Constraint

In this paper, we establish existence theorems of quasivariational inclusion problems; from them, we establish existence theorems of mathematical programs with quasivariational inclusion constraint, bilevel problems, mathematical programs with equilibrium constraint and semi-infinite problems. This research was supported by the National Science Council of the Republic of China. The authors express their gradtitude to the referees for valuable suggestions.     

On Efficiency Conditions for Nonsmooth Vector Equilibrium Problems with Equilibrium Constraints

In this article, necessary conditions of Fritz John type for weak efficient solutions of a nonsmooth vector equilibrium problem involving equilibrium constraints (VEPEC) in terms of the Clarke subdifferentials are established. Under constraint qualifications which are suitable for (VEPEC), necessary conditions of Kuhn-Tucker type for efficiency are derived. Under assumptions on generalized convexity of data, sufficient conditions for efficiency are developed. Some applications to vector variational inequalities and vector optimization problems with equilibrium constraints are also given.     

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.     

Some Exact Penalty Results for Nonlinear Programs and Mathematical Programs with Equilibrium Constraints

Recently, some exact penalty results for nonlinear programs and mathematical programs with equilibrium constraints were proved by Luo, Pang, and Ralph (Ref. 1). In this paper, we show that those results remain valid under some other mild conditions. One of these conditions, called strong convexity with order , is discussed in detail.     

Partial Augmented Lagrangian Method and Mathematical Programs with Complementarity Constraints

In this paper, we apply a partial augmented Lagrangian method to mathematical programs with complementarity constraints (MPCC). Specifically, only the complementarity constraints are incorporated into the objective function of the augmented Lagrangian problem while the other constraints of the original MPCC are retained as constraints in the augmented Lagrangian problem. We show that the limit point of a sequence of points that satisfy second-order necessary conditions of the partial augmented Lagrangian problems is a strongly stationary point (hence a B-stationary point) of the original MPCC if the limit point is feasible to MPCC, the linear independence constraint qualification for MPCC and the upper level strict complementarity condition hold at the limit point. Furthermore, this limit point also satisfies a second-order necessary optimality condition of MPCC. Numerical experiments are done to test the computational performances of several methods for MPCC proposed in the literature. This research was partially supported by the Research Grants Council (BQ654) of Hong Kong and the Postdoctoral Fellowship of The Hong Kong Polytechnic University. Dedicated to Alex Rubinov on the occassion of his 65th birthday.     

A New Extreme Point Algorithm and Its Application in PSQP Algorithms for Solving Mathematical Programs with Linear Complementarity Constraints

In this paper, we present a new extreme point algorithm to solve a mathematical program with linear complementarity constraints without requiring the upper level objective function of the problem to be concave. Furthermore, we introduce this extreme point algorithm into piecewise sequential quadratic programming (PSQP) algorithms. Numerical experiments show that the new algorithm is efficient in practice.     

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.     

Mathematical Programs with Vector Optimization Constraints

In this paper, we introduce mathematical programs with vector optimization constraints. For these problems, we establish two models in both the weak Pareto solution and Pareto solution setting. Some new existence results are obtained under rather weak conditions. We establish also equivalences between mathematical programs with vector optimization constraints and mathematical programs with vector variational inequality constraints.This research was partially supported by a grant from the National Science Council of the ROC. The authors thank the referees for helpful suggestions and comments.     

Necessary Conditions in Multiobjective Optimization with Equilibrium Constraints

We study multiobjective optimization problems with equilibrium constraints (MOPECs) described by parametric generalized equations in the form

Notes on Some Constraint Qualifications for Mathematical Programs with Equilibrium Constraints

We study the constraint qualifications for mathematical programs with equilibrium constraints (MPEC). Firstly, we investigate the weakest constraint qualifications for the Bouligand and Mordukhovich stationarities for MPEC. Then, we show that the MPEC relaxed constant positive linear dependence condition can ensure any locally optimal solution to be Mordukhovich stationary. Finally, we give the relations among the existing MPEC constraint qualifications.     

Complementarity Active-Set Algorithm for Mathematical Programming Problems with Equilibrium Constraints

In this paper, an algorithm for solving a mathematical programming problem with complementarity (or equilibrium) constraints (MPEC) is introduced, which uses the active-set methodology while maintaining the complementarity restrictions throughout the procedure. Finite convergence of the algorithm to a strongly stationary point of the MPEC is established under reasonable hypotheses. The algorithm can be easily implemented by adopting any active-set code for nonlinear programming. Computational experience is included to highlight the efficacy of the proposed method in practice.     

Necessary and sufficient conditions for nonsmooth 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. Then, we derive a necessary optimality result for nonsmooth MPEC on any Asplund space. Also, under generalized convexity assumptions, we establish sufficient optimality conditions for this program in Banach spaces.