New Sharp Necessary Optimality Conditions for Mathematical Programs with Equilibrium Constraints

In this paper, we study the mathematical program with equilibrium constraints formulated as a mathematical program with a parametric generalized equation involving the regular normal cone. We derive a new necessary optimality condition which is sharper than the usual M-stationary condition and is applicable even when no constraint qualifications hold for the corresponding mathematical program with complementarity constraints reformulation.

     

Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions

We consider the generalized Nash equilibrium problem which, in contrast to the standard Nash equilibrium problem, allows joint constraints of all players involved in the game. Using a regularized Nikaido-Isoda-function, we then present three optimization problems related to the generalized Nash equilibrium problem. The first optimization problem is a complete reformulation of the generalized Nash game in the sense that the global minima are precisely the solutions of the game. However, this reformulation is nonsmooth. We then modify this approach and obtain a smooth constrained optimization problem whose global minima correspond to so-called normalized Nash equilibria. The third approach uses the difference of two regularized Nikaido-Isoda-functions in order to get a smooth unconstrained optimization problem whose global minima are, once again, precisely the normalized Nash equilibria. Conditions for stationary points to be global minima of the two smooth optimization problems are also given. Some numerical results illustrate the behaviour of our approaches.     

Constraint Qualifications for Nonsmooth Mathematical Programs with Equilibrium Constraints

We study nonsmooth mathematical programs with equilibrium constraints. First we consider a general disjunctive program which embeds a large class of problems with equilibrium constraints. Then, we establish several constraint qualifications for these optimization problems. In particular, we generalize the Abadie and Guignard-type constraint qualifications. Subsequently, we specialize these results to mathematical program with equilibrium constraints. In our investigation, we show that a local minimum results in a so-called M-stationary point under a very weak constraint qualification.      

Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized Nash equilibrium problems

Generalized Nash equilibrium problems (GNEPs) allow, in contrast to standard Nash equilibrium problems, a dependence of the strategy space of one player from the decisions of the other players. In this paper, we consider jointly convex GNEPs which form an important subclass of the general GNEPs. Based on a regularized Nikaido-Isoda function, we present two (nonsmooth) reformulations of this class of GNEPs, one reformulation being a constrained optimization problem and the other one being an unconstrained optimization problem. While most approaches in the literature compute only a so-called normalized Nash equilibrium, which is a subset of all solutions, our two approaches have the property that their minima characterize the set of all solutions of a GNEP. We also investigate the smoothness properties of our two optimization problems and show that both problems are continuous under a Slater-type condition and, in fact, piecewise continuously differentiable under the constant rank constraint qualification. Finally, we present some numerical results based on our unconstrained optimization reformulation.     

A single-level reformulation of mixed integer bilevel programming problems

This paper focuses on the single-level reformulation of mixed integer bilevel programming problems (MIBLPP). Due to the existence of lower-level integer variables, the popular approaches in the literature such as the first-order approach are not applicable to the MIBLPP. In this paper, we reformulate the MIBLPP as a mixed integer mathematical program with complementarity constraints (MIMPCC) by separating the lower-level continuous and integer variables. In particular, we show that global and local minimizers of the MIBLPP correspond to those of the MIMPCC respectively under suitable conditions.     

A simplified completely positive reformulation for binary quadratic programs

In this paper, we propose a simplified completely positive programming reformulation for binary quadratic programs. The linear equality constraints associated with the binary constraints in the original problem can be aggregated into a single linear equality constraint without changing the feasible set of the classic completely positive reformulation proposed in the literature. We also show that the dual of the proposed simplified formulation is strictly feasible under a mild assumption.     

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.     

Semismooth Newton method for the lifted reformulation of mathematical programs with?complementarity constraints

We consider a reformulation of mathematical programs with complementarity constraints, where by introducing an artificial variable the constraints are converted into equalities which are once but not twice differentiable. We show that the Lagrange optimality system of such a reformulation is semismooth and BD-regular at the solution under reasonable assumptions. Thus, fast local convergence can be obtained by applying the semismooth Newton method. Moreover, it turns out that the squared residual of the Lagrange system is continuously differentiable (even though the system itself is not), which opens the way for a natural globalization of the local algorithm. Preliminary numerical results are also reported.     

A reformulation for the stochastic lot sizing problem with service-level constraints

We study the stochastic lot-sizing problem with service level constraints and propose an efficient mixed integer reformulation thereof. We use the formulation of the problem present in the literature as a benchmark, and prove that the reformulation has a stronger linear relaxation. Also, we numerically illustrate that it yields a superior computational performance. The results of our numerical study reveals that the reformulation can optimally solve problem instances with planning horizons over 200 periods in less than a minute.     

A Smoothing Method for a Mathematical Program with P-Matrix Linear Complementarity Constraints

We consider a mathematical program whose constraints involve a parametric P-matrix linear complementarity problem with the design (upper level) variables as parameters. Solutions of this complementarity problem define a piecewise linear function of the parameters. We study a smoothing function of this function for solving the mathematical program. We investigate the limiting behaviour of optimal solutions, KKT points and B-stationary points of the smoothing problem. We show that a class of mathematical programs with P-matrix linear complementarity constraints can be reformulated as a piecewise convex program and solved through a sequence of continuously differentiable convex programs. Preliminary numerical results indicate that the method and convex reformulation are promising.     

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.      

Lagrangean relaxation based heuristics for lot sizing with setup times

We consider a lot sizing problem with setup times where the objective is to minimize the total inventory carrying cost only. The demand is dynamic over time and there is a single resource of limited capacity. We show that the approaches implemented in the literature for more general versions of the problem do not perform well in this case. We examine the Lagrangean relaxation (LR) of demand constraints in a strong reformulation of the problem. We then design a primal heuristic to generate upper bounds and combine it with the LR problem within a subgradient optimization procedure. We also develop a simple branch and bound heuristic to solve the problem. Computational results on test problems taken from the literature show that our relaxation procedure produces consistently better solutions than the previously developed heuristics in the literature.     

New Constrained Optimization Reformulation of Complementarity Problems

We suggest a reformulation of the complementarity problem CP(F) as a minimization problem with nonnegativity constraints. This reformulation is based on a particular unconstrained minimization reformulation of CP(F) introduced by Geiger and Kanzow as well as Facchinei and Soares. This allows us to use nonnegativity constraints for all the variables or only a subset of the variables on which the function F depends. Appropriate regularity conditions ensure that a stationary point of the new reformulation is a solution of the complementarity problem. In particular, stationary points with negative components can be avoided in contrast to the reformulation as unconstrained minimization problem. This advantage will be demonstrated for a class of complementarity problems which arise when the Karush–Kuhn–Tucker conditions of a convex inequality constrained optimization problem are considered.     

Constraint Qualifications for Mathematical Programs with Equilibrium Constraints and their Local Preservation Property

This paper studies the system of constraint qualifications tailored for mathematical programs with equilibrium constraints. The main focuses are on the relations among them and their local preservation property. After giving a relaxed version of the constant positive linear dependence constraint qualification for mathematical programs with equilibrium constraints, we establish some new relations among the tailored constraint qualifications. Then, we investigate their local preservation property. Finally, we present several results on the isolatedness of local minimizers. The paper contains some proof techniques that seem to be new in the literature of mathematical programs with equilibrium constraints. The obtained results complement and improve some recent ones in this direction.     

A variational inequality formulation of equilibrium models for end-of-life products with nonlinear constraints

Variational inequality theory facilitates the formulation of equilibrium problems in economic networks. Examples of successful applications include models of supply chains, financial networks, transportation networks, and electricity networks. Previous economic network equilibrium models that were formulated as variational inequalities only included linear constraints; in this case the equivalence between equilibrium problems and variational inequality problems is achieved with a standard procedure because of the linearity of the constraints. However, in reality, often nonlinear constraints can be observed in the context of economic networks. In this paper, we first highlight with an application from the context of reverse logistics why the introduction of nonlinear constraints is beneficial. We then show mathematical conditions, including a constraint qualification and convexity of the feasible set, which allow us to characterize the economic problem by using a variational inequality formulation. Then, we provide numerical examples that highlight the applicability of the model to real-world problems. The numerical examples provide specific insights related to the role of collection targets in achieving sustainability goals.     

Mathematical Programming with System of Equilibrium Constraints

In this paper, we study the mathematical program with system of equilibrium constraints. This problem contains bilevel program with system of equilibrium constraints, semi-infinite program with system of equilibrium constraints, mathematical program with Nash equilibrium constraints, mathematical program with system of mixed variational like inequalities constraints. We establish the existence theorems of mathematical program with system of equilibrium constraints under various assumptions.     

A Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints

This paper presents a sequential quadratic programming algorithm for computing a stationary point of a mathematical program with linear complementarity constraints. The algorithm is based on a reformulation of the complementarity condition as a system of semismooth equations by means of Fischer-Burmeister functional, combined with a classical penalty function method for solving constrained optimization problems. Global convergence of the algorithm is established under appropriate assumptions. Some preliminary computational results are reported.     

Gap Function Approach to the Generalized Nash Equilibrium Problem

We consider an optimization reformulation approach for the generalized Nash equilibrium problem (GNEP) that uses the regularized gap function of a quasi-variational inequality (QVI). The regularized gap function for QVI is in general not differentiable, but only directionally differentiable. Moreover, a simple condition has yet to be established, under which any stationary point of the regularized gap function solves the QVI. We tackle these issues for the GNEP in which the shared constraints are given by linear equalities, while the individual constraints are given by convex inequalities. First, we formulate the minimization problem involving the regularized gap function and show the equivalence to GNEP. Next, we establish the differentiability of the regularized gap function and show that any stationary point of the minimization problem solves the original GNEP under some suitable assumptions. Then, by using a barrier technique, we propose an algorithm that sequentially solves minimization problems obtained from GNEPs with the shared equality constraints only. Further, we discuss the case of shared inequality constraints and present an algorithm that utilizes the transformation of the inequality constraints to equality constraints by means of slack variables. We present some results of numerical experiments to illustrate the proposed approach.     

Equilibrium constrained optimization problems

We consider equilibrium constrained optimization problems, which have a general formulation that encompasses well-known models such as mathematical programs with equilibrium constraints, bilevel programs, and generalized semi-infinite programming problems. Based on the celebrated KKM lemma, we prove the existence of feasible points for the equilibrium constraints. Moreover, we analyze the topological and analytical structure of the feasible set. Alternative formulations of an equilibrium constrained optimization problem (ECOP) that are suitable for numerical purposes are also given. As an important first step for developing efficient algorithms, we provide a genericity analysis for the feasible set of a particular ECOP, for which all the functions are assumed to be linear.