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

(→Introduction) |
(→Introduction) |
||

(60 intermediate revisions by 2 users not shown) | |||

Line 1: | Line 1: | ||

− | + | Authors: Alexandra Rodriguez (ChE 345 Spring 2015) and Brandon Muncy (ChE345 Spring 2015) <br\> | |

+ | Stewards: Dajun Yue and Fengqi You | ||

− | |||

− | + | ==Introduction== | |

+ | Mathematical programming with equilibrium constraints (MPEC) is a type of nonlinear programming (NLP) with constrained optimization.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">1,2</span> An MPEC is quite a challenging problem to which no solvers are yet available.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">1,2,3,4</span> Therefore, to implement the MPEC model in GAMS the program should be transformed into an NLP model. The reformulation is an inner product reformulation with positive slack variables and constraint equalities set to zero. In comparison to a mixed-integer nonlinear program which uses binary variables, complementary constraints are used to model discrete decisions. A CONOPT solver can be used to solve the NLP model.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">5</span> <br/> | ||

− | + | MPEC plays a central role in the modeling of transportation problems, economics, and engineering design.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">1,4</span> | |

− | + | ==Problem formulation== | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | =Problem formulation= | + | |

<math>min </math> <math> f(x,y)</math><br\> | <math>min </math> <math> f(x,y)</math><br\> | ||

− | <math> s.t. </math> <math> g(x,y) \ge 0 </math><br\> | + | <math> s.t. </math> <math> g(x,y) \ge 0 </math><br\> |

− | <math> y \in Y(x) </math><br\> | + | <math> y \in Y(x) </math><br\> |

− | φ<math>(x,y,z) \ge 0 </math><br\> | + | φ<math>(x,y,z) \ge 0 </math><br\> |

<math> where </math> <math> f, g, </math> φ<math>, Y(x) \in \mathbb{R} </math><br\> | <math> where </math> <math> f, g, </math> φ<math>, Y(x) \in \mathbb{R} </math><br\> | ||

− | + | or, | |

− | + | <math>min </math> <math> f(x,y) </math><br\> | |

+ | <math> s.t. </math> <math> g(x,y) \ge 0 </math><br\> | ||

+ | <math> y \ge 0, F(x,y) \ge, y^TF(x,y)=0 </math><br\> | ||

+ | In the second case, f, g, and F are twice continuously differentiable functions. The x variables are first-level variables, or design variables, while the y variables are second-level variables, or state variables. <br\> <br\> | ||

+ | The lower level-constraints give rise to a parametric nonlinear complementarity problem: <math> y \ge 0, F(x,y) \ge, y^TF(x,y)=0. </math> The equilibrium constraints are complementarity constraints, or variational inequality constraints. Constraints must satisfy an equilibrium condition, which can be an equilibrium inequality or a complementarity condition, of which the simplest form is given by the critical point: | ||

− | = | + | <math>\nabla_y </math> φ <math> = 0</math> |

− | + | Therefore, an equilibrium constrained optimization model is given by: | |

− | + | ||

+ | <math> min </math> <math> f(x,y)</math><br\> | ||

+ | <math>s.t. </math> <math> \nabla_y </math> φ <math> (x,y) = 0 </math><br\> | ||

+ | <math>where </math> <math> f, </math> φ <math> \in \mathbb{R}</math><br\> | ||

+ | |||

+ | The solution set to the lower-level complementarity constraints is nonconvex, to which the best solution is a local solution. While this is a nonlinear program, the constraint conditions required to prove the convergence of basic nonlinear problems fail. Specialized algorithms are needed to solve an MPEC program.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">4</span> | ||

+ | |||

+ | ===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.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2</span> | ||

+ | |||

+ | ===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): | ||

<math> min </math> <math> f(x) </math><br\> | <math> min </math> <math> f(x) </math><br\> | ||

<math> s.t. </math> <math> g(x) \ge 0, </math><br\> | <math> s.t. </math> <math> g(x) \ge 0, </math><br\> | ||

− | <math> G_1(x) </math> <math> \ge 0, </math><br\> | + | <math> G_1(x) </math> <math> \ge 0, </math><br\> |

− | <math> G_2(x) </math> <math> \ge 0, </math><br\> | + | <math> G_2(x) </math> <math> \ge 0, </math><br\> |

− | <math> G_1(x) </math> <math> G_2(x) </math> <math> = 0 </math><br\> | + | <math> G_1(x) </math> <math> G_2(x) </math> <math> = 0 </math><br\> |

− | |||

− | |||

The complementarity constraints can be written equivalently as: | The complementarity constraints can be written equivalently as: | ||

<math> 0 \le G_1(x) </math> perp-to <math> G_2(x) </math> <math> \ge 0. </math> | <math> 0 \le G_1(x) </math> perp-to <math> G_2(x) </math> <math> \ge 0. </math> | ||

+ | A mathematical program with complementarity constraints (MPCC) is a relaxed MPEC.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2</span> | ||

− | + | ====Linear constrained optimization==== | |

− | + | ||

− | ===Linear constrained optimization=== | + | |

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: | ||

Line 58: | Line 68: | ||

<math> where </math> <math> b, </math><math>d, </math><math>B, </math><math>C \in \mathbb{R} </math><br\> | <math> where </math> <math> b, </math><math>d, </math><math>B, </math><math>C \in \mathbb{R} </math><br\> | ||

− | = | + | ==Applications in Economics== |

+ | |||

+ | As mentioned above, there are several applications of MPEC problems, one of which is in the area of economics. One of the most prominent examples is in market analysis. | ||

+ | |||

+ | For example, consider that ''n'' companies produce the same product. We will introduce an integer variable ''y'' to denote the number of units a company will sell. We will further denote ''y<sub>i</sub>'' 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 = <math>\sum_{i=1}^n { y_i }\!</math>. The total cost of production for a company will be given by ''f<sub>i</sub>(y<sub>i</sub>)''. With this notation, the profit can then be given by the expression: | ||

+ | |||

+ | <math>u_i </math> = <math>y_i</math><math>p(T)</math> - <math>f_i</math><math>(y_i)</math><sup>1</sup> | ||

+ | |||

+ | 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, which are very common in equilibrium constraint problems. | ||

+ | |||

+ | ==Applications in Engineering Design== | ||

+ | [[File:Screen_Shot_2015-06-07_at_8.46.59_PM.png|thumb|right|350px|MPEC Model of Heat-Integrated Water Allocation Network]] | ||

+ | An MPEC can be formulated to model the simultaneous optimization of water allocation and heat exchanger networks. The problem contains four water utilization operations and a contaminant. An optimal result is shown in the figure. <br/> | ||

+ | |||

+ | ==Tools for Solving MPEC Problems== | ||

+ | |||

+ | Although MPEC problems are difficult to solve using non-linear programming methods, they can still be solved using computer programs. For example, MPEC's can be solved in GAMS. For defining the objective function, use the same syntax as one normally would. Any general constraints (not equilibrium) are defined as normal. For the equilibrium constraints, use equationname.y, with the constraints being entered using normal syntax, with bounds introduced via y. Additionally, the dependence of the complementary relationship is demonstrated by the ".y". <br/> <br/> | ||

+ | |||

+ | The "trick" to solving MPEC problems in GAMS is to convert the problem to a nonlinear program. This is done by creating a solver that calls the convert tool. In Ferris, Dirske, and Meeraus, the specific solver used is ''nlpec''. This mapping into the nonlinear can be complicated, and is dependent on the specific set that is being reformulated. However, these mappings can be found in [http://faculty.wcas.northwestern.edu/~lchrist/Ferris_mathematical_programs2.pdf their paper].<sup>2</sup> | ||

=References= | =References= | ||

− | + | 1. G.B. Allende. Mathematical programs with equilibrium constraints: solution techniques from parametric optimization (1977). <br/> | |

− | + | 2. M.C. Ferris, S.P. Dirkse, A. Meeraus. Mathematical programs with equilibrium constraints: automatic reformation and solution via constrained optimization. Northwestern University (2002). <br/> | |

− | + | 3. H. Pieper. Algorithms for mathematical programs with equilibrium constraints with applications to deregulated electricity markets. Stanford University (2001). <br/> | |

− | + | 4. R. Andreani, J.M. Martinez. On the solution of mathematical programming problems with equilibrium constraints (2008). <br/> | |

+ | 5. L. Zhou. Z. Liao. J. Wang. Simultaneous Optimization of Heat-Integrated Water Allocation Networks Using the Mathematical Model with Equilibrium Constraints Strategy (2015). |

## Latest revision as of 20:25, 7 June 2015

Authors: 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 (NLP) with constrained optimization.1,2 An MPEC is quite a challenging problem to which no solvers are yet available.1,2,3,4 Therefore, to implement the MPEC model in GAMS the program should be transformed into an NLP model. The reformulation is an inner product reformulation with positive slack variables and constraint equalities set to zero. In comparison to a mixed-integer nonlinear program which uses binary variables, complementary constraints are used to model discrete decisions. A CONOPT solver can be used to solve the NLP model.5

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

## Problem formulation

φ

φ

or,

In the second case, f, g, and F are twice continuously differentiable functions. The x variables are first-level variables, or design variables, while the y variables are second-level variables, or state variables.

The lower level-constraints give rise to a parametric nonlinear complementarity problem: The equilibrium constraints are complementarity constraints, or variational inequality constraints. Constraints must satisfy an equilibrium condition, which can be an equilibrium inequality or a complementarity condition, of which the simplest form is given by the critical point:

φ

Therefore, an equilibrium constrained optimization model is given by:

φ

φ

The solution set to the lower-level complementarity constraints is nonconvex, to which the best solution is a local solution. While this is a nonlinear program, the constraint conditions required to prove the convergence of basic nonlinear problems fail. Specialized algorithms are needed to solve an MPEC program.4

### 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.2

### 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):

The complementarity constraints can be written equivalently as:

perp-to

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

#### Linear constrained optimization

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

λ

λ

## Applications in Economics

As mentioned above, there are several applications of MPEC problems, one of which is in the area of economics. One of the most prominent examples is in market analysis.

For example, consider that *n* companies produce the same product. We will introduce an integer variable *y* to denote the number of units a company will sell. We will further denote *y _{i}* 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 = . The total cost of production for a company will be given by

*f*. With this notation, the profit can then be given by the expression:

_{i}(y_{i}) = - ^{1}

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, which are very common in equilibrium constraint problems.

## Applications in Engineering Design

An MPEC can be formulated to model the simultaneous optimization of water allocation and heat exchanger networks. The problem contains four water utilization operations and a contaminant. An optimal result is shown in the figure.

## Tools for Solving MPEC Problems

Although MPEC problems are difficult to solve using non-linear programming methods, they can still be solved using computer programs. For example, MPEC's can be solved in GAMS. For defining the objective function, use the same syntax as one normally would. Any general constraints (not equilibrium) are defined as normal. For the equilibrium constraints, use equationname.y, with the constraints being entered using normal syntax, with bounds introduced via y. Additionally, the dependence of the complementary relationship is demonstrated by the ".y".

The "trick" to solving MPEC problems in GAMS is to convert the problem to a nonlinear program. This is done by creating a solver that calls the convert tool. In Ferris, Dirske, and Meeraus, the specific solver used is *nlpec*. This mapping into the nonlinear can be complicated, and is dependent on the specific set that is being reformulated. However, these mappings can be found in their paper.^{2}

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

5. L. Zhou. Z. Liao. J. Wang. Simultaneous Optimization of Heat-Integrated Water Allocation Networks Using the Mathematical Model with Equilibrium Constraints Strategy (2015).