Difference between revisions of "Mathematical programming with equilibrium constraints"

From optimization
Jump to: navigation, search
(Linear constrained optimization)
(Linear constrained optimization)
Line 53: Line 53:
 
The KKT approach may also lead to an MPCC with only linear functions:
 
The KKT approach may also lead to an MPCC with only linear functions:
  
&nbsp; <math> min </math> &nbsp; <math> c^T (x,y) </math> <br\>
+
&nbsp; <math> min </math> &nbsp; <math> c^T (x,y) </math> <br\>
&nbsp; <math> s.t. </math> &nbsp;  <math>  C(x,y) </math><math>+d</math><math>-BY^T </math> &#955; <math> = 0 </math> <br\>
+
&nbsp; <math> s.t. </math> &nbsp;  <math>  C(x,y) </math><math>+d</math><math>-BY^T </math> &#955; <math> = 0 </math> <br\>
&nbsp; <math> B(x,y) \ge b </math> <br\>
+
&nbsp;  &nbsp; &nbsp; <math> B(x,y) \ge b </math> <br\>
&nbsp; &nbsp;  &#955; <math> \ge 0 </math> <br\>
+
&nbsp;   &nbsp;  &nbsp; &#955; <math> \ge 0 </math> <br\>
&nbsp; <math> [B(x,y) </math><math> - b]^T = 0 </math> <br\>
+
&nbsp;  &nbsp; &nbsp; <math> [B(x,y) </math><math> - b]^T = 0 </math> <br\>
&nbsp; <math> where </math><math> b, </math><math>d, </math><math>B, </math><math>C \in \mathbb{R} </math><br\>
+
&nbsp; <math> where </math> &nbsp; <math> b, </math><math>d, </math><math>B, </math><math>C \in \mathbb{R} </math><br\>
  
 
=Conclusion=
 
=Conclusion=

Revision as of 22:36, 24 May 2015

Contents

Introduction

Mathematical programming with equilibrium constraints (MPEC) is a type of nonlinear programming with constrained optimization. Constraints must satisfy an equilibrium 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}

Conclusion

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).