Mathematical programming with equilibrium constraints

Authors: Andrew Amerman, Hannah Levy, Juan Henriquez, Matthew Baccaro, and Taha Shamshudin (SYSEN 5800 Fall 2021)

Introduction

A Mathematical Program with Equilibrium Constraint (MPEC) are special class of constrained optimization problems inside of nonlinear programming (NLP) . These are constrained optimization problems where the constraints include equilibrium constraints like variational inequalities or complementary conditions. Variational inequalities are inequalities that involve a function and must be solved for all possible values of a given variable . MPECs have applications in fields of engineering design, economic equilibrium, high level games, and modeling of transportation . The feasible set of MPEC violates most of the standard constraint qualifications and are difficult to solve due to the feasible region not necessarily being convex or connected . Constraint qualifications are assumptions of a feasible set of optimization problem. These qualifications confirm that Karush–Kuhn–Tucker (KKT) conditions are true at any local minimum . It is necessary to consider suitable optimality conditions, which are derived studying the behavior of the functions and their derivatives at that point, for solving these optimization problems. Throughout this article, the theory and methodology behind MPEC will be discussed and an example will be given as well discussion on the applications pertaining to MPEC will occur.

Theory/Methodology/Algorithms

Definition

The MPEC problem is defined as a nonlinear programming optimization problem which includes variables based on the sets of $x\in R^{n}$ and  $y\in R^{m}$ where there are one or more parametric variational inequality constraints for primary variables y and parameter vector x, where vector x contains the design variables of an engineering process .

The standard form for MPEC problems is:

$\min f(x,y)$

$s.t.(x,y)\in Z$

$y\in S(x)$

where $(v-y)^{T}$$F(x,y)\geq 0$ for all $v\in C(x)$

$F$ refers to the equilibrium function of the inner problem.

Note that the above definition defines a nonlinear programming problem. The constraint:

$y\in S(x)$

represents the equilibrium constraints. The MPEC optimization problem becomes useful when these equilibrium constraints represent engineering or economic equilibrium states that can be modeled here as variational inequalities .

Given vector x:

$x\in C$

Denoted by:

$T(x;C)$, is the set of all vectors.

Targeted Approaches

Four different types of algorithmic approaches can be used to solve MPEC. Of the 4 techniques, three of these specialized techniques include the penalty interior point approach (PIPA), the implicit programming approach, and the piecewise sequential quadratic programming (SQP) approach . Additionally, some MPEC problems can be reformulated as a relaxed NLP which can then be solved using other NLP techniques.

PIPA

The PIPA methodology has been applied to applications in finance, target classification, and electricity markets. This technique generates a sequence of iterates as shown below that are strictly within the bounds. The iterates are calculated by solving a quadratic direction-finding problem. PIPA combines aspects of interior-point and SQP methods.

This approach considers an MPEC optimization problem with parametric complementary constraints as follows:

$\min f(x,y,w,z)$

$s.t.x\in X$

$F(x,y,w,z)=0$

$(y,w)\geq 0,w^{T}y=0$

And defines the following optimality constraint:

Given:

$u^{*}=(x^{*},y^{*},w^{*},z^{*})\in F$

$u^{*}$ is a stationary point if and only if:

$du\in T(u^{*};F)\Longrightarrow \bigtriangledown f(u^{*})^{T}du\geq 0$

The following algorithm is employed:

Step 0: Initialize scalars and the initial iterate.

Step 1: Solve the quadratic programming subproblem at v such that $(dx^{v},dy^{v},dw^{v},dz^{v})$ is the unique solution. Set penalty parameter α_v using the selected penalty update rule.

Step 2: Calculate the step size.

Step 3: Compute the termination check to see if the optimal solution has been reached. If the optimal solution has not been reached, repeat steps 1-3 for $v=v+1$ .

A basic termination condition is:

$\parallel dx^{v},dy^{v},dw^{v},dz^{v}\parallel \leq tolerance$

Implicit Programming

The implicit programming approach is appropriate for use when complementarity constraints meet specific regularity conditions. This occurs when they are limited to solve the resulting nonsmooth problem in the variable x, as seen below.

This approach solves MPEC problems of the form:

$minf(x,y)$

$s.t.(x,y)\in F{\overset {\underset {\mathrm {def} }{}}{=}}(X*R^{m})\cap Gr(S)$

The following subproblem can be defined:

$min(df_{x}^{v})^{T}dx+(df_{y}^{v})^{T}(y^{v})'(x^{v};dx)+0.5(dx)^{T}Q_{v}dx$

$s.t.x^{v}+dx\in X$

Where Q_v is a symmetric positive definite matrix.

The following method can be used to solve this formulation:

Step 0: Initialize scalars and the initial iterate.

Step 1: Solve the defined subproblem to obtain the solution $dx^{v}$if $dx^{v}=0$, the optimal solution has been found and $(x^{v},y^{v})$ is a stationary point. If not, determine the step size and repeat until the optimal solution has been found .

Piecewise SQP

The Piecewise SQP technique is a numerical method for solving certain MPECs, based on the different sequential quadratic programming method for NLP problems. This can be applied to any MPEC whose lower-level problem is a mixed complementarity problem and indirectly to any MPEC where the lower-level problem is at the class of variational inequalities.

This approach solves MPEC problems of the form:

$\min f(x)$

$s.t.g_{i}(x)=0$, $i=1,...,l$

$g_{i}(x)\leq 0$, $i=l+1,...,m+l$

The following Newton-type method is employed:

Step 0: Initialize $x^{0}\in R^{n}$, $\pi ^{0}\in R^{l+m}$, $v=0$

Step 1: Let ($dx^{v}$, $\pi ^{v+1}$) be a KKT pair for:

$min\bigtriangledown f(x^{v})^{T}dx+0.5dx^{T}\bigtriangledown _{xx}^{2}L^{NLP}(v^{v},\pi ^{v})dx$

$s.t.g_{i}(x^{v})+\bigtriangledown g_{i}(x^{v})^{T}dx=0,i=1...,l$

$g_{i}(x^{v})+\bigtriangledown g_{i}(x^{v})^{T}dx\leq 0,i=l+1,...,l+m$

Step 2: Set $x^{v+1}=x^{v}+dx^{v}$ and check for termination. If check fails, repeat steps 1 and 2 with $v=v+1$.

NLP Reformulation

NLP Reformulation technique is applicable to MPECs that fall into the same grouping as piecewise SQP. It is possible to generate positive slack variables on optimization function and constraints while setting the constraint equalities to zero. With this reformulation is it now possible to apply other NLP techniques to solving a MPEC such as the Karush- Kuhn-Tucker approach. The general form of MPECs that can be reformulated is:

$\min f(x)$

$s.t.g_{i}(x)=0$, $i=1,...,l$

$g_{i}(x)\leq 0$, $i=l+1,...,m+l$

From here, the KKT method is used to address this NLP problem and find the minimum of the optimization function. This process consists of 4 steps :

Step 0: Let $J=\{j|g_{j}(x)=0\}$ where $J$ is an index of active inequalities.

Step 1: Set $J=\emptyset ,\mu _{j}=0,j=1,2,...,p.$

Step 2: Formulate equations for linear dependence of gradients and constraint feasibility; solve for $x,\lambda _{i},i=1,2,...,m,$ and $\mu _{j},j\in J$

$\bigtriangledown f(x)+\sum _{i=1}^{m}\lambda _{i}\cdot \bigtriangledown h_{i}(x)+\sum _{j\in J}\mu _{j}\cdot \bigtriangledown g_{j}(x)=0$

$h_{i}(x)=0,i=1,...,m$

$g_{j}(x)=0,j\in J$

Step 3: If $g_{j}(x)\leq 0$ and $\mu _{j}\geq 0,j=1,2,...,p.\Longrightarrow$STOP. Solution has been found.

Step 4: If any $g_{j}(x)>0$ and/or any $\mu _{j}<0$, then:

1. Drop the active constraint (ie. violates the condition above) with the largest magnitude.
2. Add the violated constraints to $J$ making them active.
3. Return to Step 2 .

General Approaches

Note that the above approaches do not cover all formulations of MPEC problems. Aside from these formulations, one of the main approaches for the solution of optimization problems with constraints is a reformulation of the problem as a standard nonlinear program which allows the solution to use existing non-linear programming algorithms. Some of these algorithms are mentioned here on this wiki including Quasi-Newton methods and trust-region method. There have been three advances in the past two decades which have increased the capability of a modeler to solve large scale complementarity problems. First was the implementation of large-scale complementarity solvers which utilize advance methods in linear algebra and nonlinear optimization. Some of these solvers are MILES, PATH and SMOOTH. The second advancement is the start of modeling systems that are able to express complementarity problems as part of their syntax and pass the model to the solver. The third advancement was the interactions in which the first two develop. A modeler is able to generate realistic large-scale models which allow the solvers to be tested on large and more difficult class of models. By solving larger and complex programming problems with additional constraints, this furthers the development of new applied economic models .

Numerical example

The numerical example below contains a feasible region that is not necessarily convex or connected. The example also involves variational inequalities as shown by the two constraints. The methodology utilized below has the initial form as an NLP problem. Realistically, the initial problem would start as an MPEC and transform into an NLP.

Consider the following MPEC example by Savard and Gauvin

$\min x_{1}^{2}+(x_{2}-10)^{2}$

s.t. $-4x_{1}-8x_{2}-x_{3}+120\leq 0$

$x_{1}+x_{2}-20\leq 0$

$0\leq x_{1}\leq 15,x_{2}\geq 0,x_{3}\geq 0$

Solving the MPEC by technique of identifying a KTT point:

$\min f(x)=x_{1}^{2}+(x_{2}-10)^{2}$

s.t. $g_{1}=-4x_{1}-8x_{2}-x_{3}+120\leq 0$

$g_{2}=x_{1}+x_{2}-20\leq 0$

$g_{3}=x_{1}-15\leq 0$

$g_{4}=-x_{1}\leq 0$

$g_{5}=-x_{2}\leq 0$

$g_{6}=-x_{3}\leq 0$

$\nabla f={\begin{bmatrix}2x_{1}\\\ 2x_{2}-20\\0\end{bmatrix}}$, $\nabla g_{1}={\begin{bmatrix}-4\\\ -8\\-1\end{bmatrix}}$, $\nabla g_{2}={\begin{bmatrix}1\\\ 1\\0\end{bmatrix}}$,$\nabla g_{3}={\begin{bmatrix}1\\\ 0\\0\end{bmatrix}}$, $\nabla g_{4}={\begin{bmatrix}-1\\\ 0\\0\end{bmatrix}}$, $\nabla g_{5}={\begin{bmatrix}0\\\ -1\\0\end{bmatrix}}$, $\nabla g_{6}={\begin{bmatrix}0\\\ 0\\-1\end{bmatrix}}$

Iteration 1: $J=\phi ,\mu _{1}=\mu _{2}=\mu _{3}=\mu _{4}=\mu _{5}=\mu _{6}=0$

With $\nabla f=0$, $x_{1}=0,x_{2}=10,x_{3}=0$

Point (0,10,0) violates $g_{1}$

Set $J=\{1\},$ make $g_{1}$ active:

$g_{1}=-4x_{1}-8x_{2}-x_{3}+120=0$

Solving the following system of equations:

$\nabla f(x)+\mu _{1}\cdot \nabla g_{1}(x)=0$

$g_{1}(x)=0$

${\begin{bmatrix}2x_{1}\\\ 2x_{2}-20\\0\end{bmatrix}}+\mu _{1}\cdot {\begin{bmatrix}-4\\\ -8\\-1\end{bmatrix}}={\begin{bmatrix}0\\\ 0\\0\end{bmatrix}}$

$x_{1}=2,x_{2}=14,\mu _{1}=1,x_{3}=0$

Point (2,14,0) satisfies $g_{2},g_{3},g_{4},g_{5},g_{6}<0,$so $\mu _{2}=\mu _{3}=\mu _{4}=\mu _{5}=\mu _{6}=0$

KKT point lies at $x_{1}=2,x_{2}=14,x_{3}=0$

The following numerical example was also solved with GAMS using an MPEC solver to verify solution accuracy

Applications

MPEC can be found in a variety of real world applications such as: power management , highway pricing, chemical process engineering , and traffic planning . One of the common two-level problems solved through MPEC is a single-leader Stackelberg game. This model is defined by a leader firm which moves first in the market, then other firms follow. Two of the most common fields this theory is applied is energy pricing and transportation tolls.

Energy Pricing

One type of problem solved using MPEC is finding market equilibrium in the energy sector. If we assume that there is only one strategic player in an energy market (leader) and there are several smaller fringe firms we can setup an MPEC with the constraints bounded by a fixed demand in the network and firms focused on maximizing profits. In this case the top level of the problem is solved with the market leader, and the lower-level equilibrium problem is made up of the competitive fringe firms where an independent system operator (ISO) is making decisions on the quantities produced by each fringe firm. This lower level problem is used as a starting point for the equilibrium constraints of the MPEC. This technique is shown to solve a fifteen-node network representative of the Western European power grid .

A similar model is presented for the United States power grid by Hobbs, Metzler, and Pang . The single-firm model consists of a dominant firm that interprets competitor firms’ bids and seeks to maximize its own profits. An MPEC is utilized with a penalty interior point algorithm to iterate through the single-firm problem to determine the optimum profit of the system, and ensure it is a global solution.

Transportation Tolls

MPEC problems are also used to solve pricing for highway tolls in a given area. Congestion on highways is one of the leading causes of accidents which has led to safety researchers to investigate ways to reduce traffic flow in certain areas. These problems are set up in a way that the different roadways between nodes are evaluated for demand and whether tolls can be placed on the road. This type of setup is considered a second-best toll pricing problem, which can be represented as a MPEC formulation of a bi-level optimization problem .

Conclusions

MPEC optimization problems are complex constrained optimization problems commonly used to approach feasible sets that are not convex or connected. The problems are generally approached three different way: PIPA, implicit descent, and piecewise SQP which provides for a technique to solve a MPEC of a variety of forms. With the ability to solve complex bi-level optimization problems, MPEC are commonly applied to transportation problems along with Stackelberg leadership game scenarios to find the optimal solution.