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

(→Applications in Engineering Design) |
|||

Line 5: | Line 5: | ||

==Introduction== | ==Introduction== | ||

− | Mathematical programming with equilibrium constraints (MPEC) is a type of nonlinear programming with constrained optimization. | + | Mathematical programming with equilibrium constraints (MPEC) is a type of nonlinear programming with constrained optimization. |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

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

Line 32: | Line 24: | ||

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

+ | |||

+ | 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\> | ||

===Feasible set=== | ===Feasible set=== |

## Revision as of 21:04, 7 June 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.

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

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

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:

φ

φ

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

The complementarity constraints can be written equivalently as:

perp-to

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:

λ

λ

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

In comparison to a mixed-integer nonlinear program which uses binary variables, complementary constraints are used to model discrete decision.

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