Difference between revisions of "Mathematical programming with equilibrium constraints"

From optimization
Jump to: navigation, search
(→‎Economics)
(→‎Economics)
Line 66: Line 66:
  
 
<math>u_i </math> = <math>y_i</math><math>p(T)</math> - <math>f_i</math><math>(y_i)</math>
 
<math>u_i </math> = <math>y_i</math><math>p(T)</math> - <math>f_i</math><math>(y_i)</math>
 +
 +
In this case, if company 1 were to product a product, their profitability would be based on the amount of other products in the market. Therefore, the portion of the profit that is a summation, is based on another optimization problem. This case is known as a bi-level problem.
  
 
=References=
 
=References=

Revision as of 23:13, 24 May 2015

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


Contents

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_ip(T) - f_i(y_i)

In this case, if company 1 were to product a product, their profitability would be based on the amount of other products in the market. Therefore, the portion of the profit that is a summation, is based on another optimization problem. This case is known as a bi-level problem.

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

Retrieved from "https://optimization.mccormick.northwestern.edu/index.php?title=Mathematical_programming_with_equilibrium_constraints&oldid=2676"