
\chapter{Conclusion}\label{chap:mpec}

Interest in formulating and solving large-scale complementarity problems
has become significant and continues to grow.  One of the reasons for this 
growth is the availability of high-quality software built on strong 
theoretical foundations that can be accessed within convenient modeling 
environments.  

Environments, such as the AMPL and GAMS modeling languages, and, to a lesser 
extent, the MATLAB and NEOS packages, have
given practitioners the ability to quickly model complementarity problems and 
apply standard techniques to solve them.  We surveyed the features of each of
these environments in \chapref{environments} and presented the low-level 
solver interface used by PATH 4.x and SEMI to support them in 
\chapref{interfaces}.  The main contributions found in these two chapters 
were the introduction of the MATLAB and NEOS links and the specification of 
the solver interface, which can be used to make PATH 4.x or SEMI available
in other environments.

Theory is used to ensure that an algorithm is well-defined and efficiently 
processes 
models.  \chapref{path} developed a globalization strategy for successive 
linearization methods and proved that the method is well-defined for arbitrary
complementarity problems, and globally and locally-fast convergent under a 
strong regularity assumption.  This method was later used in the PATH 4.x
algorithm.

Sufficient conditions guaranteeing that an algorithm converges have been 
studied in the literature.  However, models can be easily generated which 
will cause most algorithms to fail.  There are many reasons for this failure. 
For example, a code will fail when the model has no solution.
In some cases, the preprocessor in \chapref{preprocessing} can detect 
this infeasibility and report the variables or constraints causing the 
infeasibility.
Other examples include cases where the function is ill-defined, or the 
Jacobian matrix is ill-conditioned, poorly-scaled, or singular.  The 
diagnostic information documented in \chapref{diagnostic} and provided by 
PATH 4.x and SEMI can be used to detect some of these problems. 

Finally, sophisticated algorithm implementations, such as PATH 4.x and SEMI, 
are used to calculate solutions to complementarity problems.
\chapref{path} presented the PATH 4.x code, which is a nonsmooth
Newton method globalized with the Fischer-Burmeister merit function.
The SEMI algorithm was developed in \chapref{semi} and based on
a semismooth algorithm applied to the penalized Fischer-Burmeister function.  
We studied methods for overcoming numerical problems in the code and 
investigated the use of iterative methods to solve the linear systems of 
equations.  The resulting PATH 4.x and SEMI implementations were shown to 
be very robust on available test sets.  

% The theme of this thesis was ``enabling'' technologies in complementarity: 
% environments enable practitioners to easily specify models; sophisticated 
% codes enable them to solve the models; and theory assures them that the 
% algorithm is well-defined and efficiently processes models.
% All three are extremely important to the continued success of the 
% complementarity framework.

% Tools for analyzing general 
% nonlinear complementarity problems and reporting the source of any
% difficulties to a modeler are currently not available and are the subject 
% of future research.

\begin{comment}
The theme of this thesis was ``enabling'' technologies in complementarity: 
environments enable practitioners to easily specify models; sophisticated 
codes enable them to solve the models; and theory assures them that the 
algorithm is well-defined and efficiently processes models.  We surveyed 
several natural environments for modeling complementarity problems in 
\chapref{environments} and presented the low-level solver interface used to 
support these environments in \chapref{interfaces}.  We then discussed 
mechanisms that can be used to preprocess complementarity problems in 
\chapref{preprocessing} and developed the PATH 4.x and SEMI codes in 
\chapref{path} and \chapref{semi} respectively.

We now combine all of these ingredients to solve mathematical programs 
with equilibrium constraints \cite{luo.pang.ea:mathematical} using the 
bundle method \cite{outrata.kocvara.ea:nonsmooth}.  A mathematical 
program with equilibrium constraints (MPEC) is a nonlinear program in which 
one of the constraints is a complementarity problem.  Specifically, let 
$\theta: \Re^{m+n} \rightarrow \Re$, $g: \Re^{m+n} \rightarrow \Re^p$, and 
$f: \Re^{m+n} \rightarrow \Re^n$.  Then, $\bar{x} \in \Re^m$ and 
$\bar{y} \in [\ell, u]$ solves MPEC($\theta,g,f,\ell,u$) if and only 
if $(\bar{x},\bar{y})$ solves the following optimization problem:
\begin{eqnarray*}
\begin{array}{rc}
\min_{x,y} & \theta(x,y) \\
\text{subject to } & g(x,y) \le 0 \\
& 0 \in f(x,y) + N_{[\ell,u]}(y).
\end{array}
\end{eqnarray*}
We call $x$ the design variables, $y$ the state variables, and $g$ the joint 
feasibility constraints.  Optimality conditions and associated theory for 
this problem are developed in \cite{luo.pang.ea:mathematical}.

The history of MPEC can be traced to the Stackelberg game 
\cite{stackelberg:theory} from economics and the bilevel program 
\cite{bracken.mcgill:mathematical}.  In the Stackelberg game, one 
party, the leader, makes a decision and other parties, the followers, react 
optimally to that decision.  The goal of this problem is for leader to 
select an optimal strategy with knowledge of the reactions of the followers.
The bilevel program is an optimization problem with another optimization 
problem as a constraint.  Under suitable assumptions 
\cite{mangasarian:nonlinear}, the second level optimization problem can be 
rewritten using the first order optimality conditions 
\cite{karush:minima,kuhn.tucker:nonlinear} to form a complementarity 
constraint.

Since its inception, a large number of applications using the MPEC formulation
have been developed.  One such application is the tolling problem 
\cite{dirkse.ferris:traffic} in which we want to minimize the amount of 
congestion in a particular transportation network by choosing a tolling 
strategy.  The equilibrium constraint in this example is that every 
driver choose the ``shortest'' path from their origin to destination, taking 
congestion into account.  This condition is known as Wardropian equilibrium 
\cite{wardrop:theoretical}.

Recall the simple transportation model developed in \chapref{environments}
in which demand for a single good must be satisfied by suppliers at a
minimal transportation cost.  We formulated this problem as a linear
complementarity problem and demonstrated how a supply side tax could
be added to the model.  One way to transform this complementarity problem
into an MPEC is to make the taxes variable and maximize the tax revenue.
\[
\begin{array}{rc}
\max_{x,p^s,p^d,t} & \sum_{(i,j) \in \arcs} t_ip^s_ix_{i,j} \\
\text{subject to} 
& 0 \leq p^s_i \; \perp \; 
    s_i \geq \sum_{j: (i,j) \in \arcs} x_{i,j},\; \forall i \\
& 0 \leq p^d_i \; \perp  \;
    \sum_{i: (i,j) \in \arcs} x_{i,j} \geq d_j,\; \forall j \\
& 0 \leq x_{i,j} \; \perp \;
    p^s_i (1 + t_i) + c_{i,j} \geq p^d_j,\; \forall (i,j) \in \arcs
\end{array}
\]

 The final
algorithm considered is a bundle method \cite{kocvara.outrata:optimization, 
kocvara.outrata:solution, outrata:optimization, outrata.zowe:numerical} which 
uses nondifferentiable
optimization techniques to solve the problem.

The bundle method reformulates the problem as a nondifferentiable program.
We then use a nondifferentiable optimization package \cite{schramm.zowe:version} to solve the problem.
We begin by defining the following:
\begin{eqnarray}
y(x) := \mbox{SOL}(\mbox{MCP}(F(x, \cdot), B))
\end{eqnarray}
We note that for the algorithm to work, if the MCP has a solution, it must
have exactly one solution.  Therefore $y$ is a single valued function.  The 
nonlinear program then solved is:
\begin{eqnarray*}
\mbox{min } \theta(x, y(x))
\end{eqnarray*}
We calculate the required subdifferential using PATH 3.0 and the technique
given in \cite{outrata.zowe:numerical}.

All of the aforementioned algorithms were tested using available MPEC
problems.  
The first problem set used are mainly academic problems found in 
\cite{bard:convex, desilva:sensitivity, facchinei.jiang.ea:smoothing, 
harker:generalized, henderson.quandt:microeconomic, 
murphy.sherali.ea:mathematical}.  Two additional real world problems were 
also added to the test suite.  The ``find'' and ``nappi'' problems are 
identification models from a structural engineering application 
\cite{tin-loi.ferris:simple, ferris.tin-loi:nonlinear}.  Basically, some 
measurements of a structure are taken and we try to predict the 
characteristics of the underlying materials.  The ``aamcp'' model is an 
optimal taxation problem obtained from T. F. Rutherford.  In this problem, we 
want to maximize a sector's utility subject to the economy being in 
Walrasian equilibrium \cite{walras:elements} by varying the tax rates.  A 
contour plot of the objective function for one such taxation problem, along 
with the solution found by the penalty algorithm, is given in Figure 3.  We 
note that the objective function is not concave but the solution found is 
very reasonable.

The mathematical program with equilibrium constraints (MPEC) is an important
problem class with applications in many areas, including structural and
traffic engineering and economic policy.
\end{comment}
