Mathematical programming with equilibrium constraints

Authors: Andrew Amerman, Hannah Levy, Juan Henriquez, Matthew Baccaro, and Taha Shamshudin (SYSEN 5800 Fall 2021)

Introduction

A Mathematical Program with Equilibrium Constraint (MPEC) are special class of constrained optimization problems inside of nonlinear programming (NLP) [1]. These are constrained optimization problems where the constraints include equilibrium constraints like variational inequalities or complementary conditions. MPECs have applications in fields of engineering design, economic equilibrium, high level games, and modeling of transportation [2]. The feasible set of MPEC violates most of the standard constraint qualifications and are difficult to solve due to the feasible region not necessarily being convex or connected [1]. It is necessary to consider suitable optimality conditions for solving these optimization problems. Throughout this article, the theory and methodology behind MPEC will be discussed and an example will be given as well discussion on the applications pertaining to MPEC will occur.

Theory/Methodology/Algorithms

Definition

The MPEC problem is defined as a nonlinear programming optimization problem which includes variables of the sets $x\in R^{n}$ and  $y\in R^{m}$ where there are one or more parametric variational inequality constraints for primary variables y and parameter vector x [3].

The standard form for MPEC problems is:

$\min f(x,y)$

$s.t.(x,y)\in Z$

$y\in S(x)$

where $(v-y)^{T}$$F(x,y)\geq 0$ for all $v\in C(x)$

F refers to the equilibrium function of the inner problem.

Note that the above definition defines a nonlinear programming problem. The constraint:

$y\in S(x)$

represents the equilibrium constraints. The MPEC optimization problem becomes useful when these equilibrium constraints represent engineering or economic equilibrium states that can be modeled here as variational inequalities [3].

Targeted Approaches

Three different types of algorithmic approaches can be used to solve MPEC. These are the penalty interior point approach (PIPA), the implicit programming approach, and the piecewise sequential quadratic programming (SQP) approach [3].

PIPA

The PIPA approach considers an MPEC optimization problem with parametric complementary constraints as follows:

$\min f(x,y,w,z)$

$s.t.x\in X$

$F(x,y,w,z)=0$

[INSERT EQUATION HERE]

And defines the following optimality constraint:

Given:

[INSERT EQUATION HERE]

u^* is a stationary point if and only if:

[INSERT EQUATION HERE]

The following algorithm is employed:

Step 0: Initialize scalars and the initial iterate.

Step 1: Solve the quadratic programming subproblem at v such that [INSERT EQUATION HERE] is the unique solution. Set penalty parameter α_v using the selected penalty update rule.

Step 2: Calculate the step size.

Step 3: Compute the termination check to see if the optimal solution has been reached. If the optimal solution has not been reached, repeat steps 1-3 for v = v + 1 [3].

A basic termination condition is:

[INSERT EQUATION HERE]

Implicit Descent

The implicit descent approach solves MPEC problems of the form:

[INSERT FORMULA HERE]

The following subproblem can be defined:

[INSERT FORMULA HERE]

Where Q_v is a symmetric positive definite matrix.

The following method can be used to solve this formulation:

Step 0: Initialize scalars and the initial iterate.

Step 1: Solve the defined subproblem to obtain the solution dx^v if dx^v = 0, the optimal solution has been found and (x^v, y^v) is a stationary point. If not, determine the step size and repeat until the optimal solution has been found [3].

Piecewise SQP

The piecewise SQP approach solves MPEC problems of the form:

[INSERT FORMULA HERE]

The following Netwon-type method is employed:

Step 0: Initialize [INSERT FORMULA HERE]

Step 1: Let (dx^v, [INSERT FORMULA HERE]) be a KKT pair for:

[INSERT FORMULA HERE]

Step 2: Set x^v+1 $\equiv$ x^v + dx^v and check for termination. If check fails, repeat steps 1 and 2 with v = v + 1 [3].

General Approaches

Note that the above approaches do not cover all formulations of MPEC problems. Aside from these formulations, one of the main approaches for the solution of optimization problems with constraints is a reformulation of the problem as a standard nonlinear program which allows the solution to use existing non-linear programming algorithms. There have been three advances in the past two decades which have increased the capability of a modeler to solve large scale complementarity problems. First was the implementation of large-scale complementarity solvers which utilize advance methods in linear algebra and nonlinear optimization. Some of these solvers are MILES, PATH and SMOOTH. The second advancement is the start of modeling systems that are able to express complementarity problems as part of their syntax and pass the model to the solver. The third advancement was the interactions in which the first two develop. A modeler is able to generate realistic large-scale models which allow the solvers to be tested on large and more difficult class of models. By solving larger and complex programming problems with additional constraints, this furthers the development of new applied economic models [2].

At least one numerical example

encouraged to have more than one

References

[1] Joshi, B.C. Some Results on Mathematical Programs with Equilibrium Constraints. Oper. Res. Forum 2, 53 (2021). https://doi.org/10.1007/s43069-021-00061-4

[2] M. Ferris, S. Dirkse, and A. Meeraus. Mathematical Programs with Equilibrium Constraints: Automatic Reformulation and Solution via Constrained Optimization. Northwestern University, Evanston, Illinois, July 2002.

[3] Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints. Cambridge: Cambridge University Press, 1996. https://www-cambridge-org.proxy.library.cornell.edu/core/books/mathematical-programs-with-equilibrium-constraints/03981C32ABDD55A4001BF58BA0C57444