# Difference between revisions of "Mathematical programming with equilibrium constraints"

Author: Alexandra Rodriguez (ChE 345 Spring 2015) and Brandon Muncy (ChE345 Spring 2015)
Stewards: Dajun Yue and Fengqi You

# Introduction

Mathematical programming with equilibrium constraints (MPEC) is a type of nonlinear programming with constrained optimization. Constraints must satisfy an equilibrium condition, which can be an equilibrium inequality or a complimentarity condition, of which the simplest form is given by the critical point:

$\nabla_y$ φ $= 0$

Therefore, an equilibrium constrained optimization model is given by:

  $min$     $f(x,y)$
$s.t.$     $\nabla_y$ φ $(x,y) = 0$
$where$     $f,$ φ $\in \mathbb{R}$


MPEC plays a central role in the modeling of transportation problems, economics, and engineering design.

# Problem formulation

  $min$   $f(x,y)$
$s.t.$   $g(x,y) \ge 0$
$y \in Y(x)$
φ$(x,y,z) \ge 0$
$where$   $f, g,$ φ$, Y(x) \in \mathbb{R}$


## Feasible set

For a feasible set, the conditions for convexity and closedness are as follows. If Y(x) is convex, and functions f, g, and ∅ are concave, then the mathematical program is convex. Furthermore, if the Mangasarian-Fromovitz constraint qualification holds at all z ∈ Y(x), then Y(x) is the lower semi-continuous bound, and the mathematical program is closed.

## KKT transformation

### Complementarity constrained optimization

By applying the Karush-Kuhn-Tucker (KKT) approach to solving an equilibrium constraint problem (EC), a program with complementarity constraints can be obtained (CC):

  $min$   $f(x)$
$s.t.$    $g(x) \ge 0,$
$G_1(x)$ $\ge 0,$
$G_2(x)$ $\ge 0,$
$G_1(x)$ $G_2(x)$ $= 0$



The complementarity constraints can be written equivalently as:

$0 \le G_1(x)$ perp-to $G_2(x)$ $\ge 0.$

A mathematical program with complementarity constraints (MPCC) is a relaxed MPEC.

### Linear constrained optimization

The KKT approach may also lead to an MPCC with only linear functions:

  $min$   $c^T (x,y)$
$s.t.$    $C(x,y)$$+d$$-BY^T$ λ $= 0$
$B(x,y) \ge b$
λ $\ge 0$
$[B(x,y)$$- b]^T = 0$
$where$   $b,$$d,$$B,$$C \in \mathbb{R}$


## Applications

As mentioned above, there are several applications of MPEC problems. Two published examples deal with economics and mathematical physics.

### Economics

For this application, consider that n companies product the same product. We will introduce an integer variable y to denote the number of units a company will sell. We will further denote yi as the number of items that company i decides to sell. The total price of the product on the market will be notated P(T), where T = $\sum_{i=1}^n { y_i }\!$. The total cost of production for a company will be given by fi(yi). With this notation, the profit can then be given by the expression:

$u_i$ = $y_i$$p(T)$ - $f_i$$(y_i)$

# References

[1] G.B. Allende. Mathematical programs with equilibrium constraints: solution techniques from parametric optimization (1977).
[2] M.C. Ferris, S.P. Dirkse, A. Meeraus. Mathematical programs with equilibrium constraints: automatic reformation and solution via constrained optimization. Northwestern University (2002).
[3] H. Pieper. Algorithms for mathematical programs with equilibrium constraints with applications to deregulated electricity markets. Stanford University (2001).
[4] R. Andreani, J.M. Martinez. On the solution of mathematical programming problems with equilibrium constraints (2008).