
\chapter{Introduction}\label{chap:introduction}

A fundamental problem in mathematics is to solve a square system of nonlinear 
equations.  The complementarity problem, a generalization of such systems, is 
the subject of this thesis.  Prototypical examples of complementarity problems
include Wardropian \cite{wardrop:theoretical} and Walrasian equilibrium
\cite{arrow.debreu:existence} models encountered in the engineering and economic 
disciplines \cite{ferris.pang:engineering}, and the first order optimality 
conditions for nonlinear programs \cite{karush:minima,kuhn.tucker:nonlinear} 
from the optimization community.  Complementarity also has applications in 
game theory \cite{nash:equilibrium,nash:non-cooperative,lemke:bimatrix,lemke.howson:equilibrium}
and options pricing \cite{huang.pang:option,wilmott.dewynne.ea:option}.
Examples of complementarity problems arising in a wide variety of disciplines 
are surveyed in \cite{dirkse.ferris:mcplib,ferris.pang:complementarity}.

This chapter contains an overview of complementarity theory and algorithms.
We begin with a precise definition of mixed complementarity problems and
discuss their relationship to variational inequalities.  \secref{refm} then 
presents
two equivalent representations of the complementarity problem as unconstrained
systems of nonsmooth equations using the normal map and a semismooth 
reformulation.  Conditions sufficient for the existence of solutions to
complementarity problems are developed in \secref{existence}.  We then
discuss algorithms for solving complementarity problems based on the normal 
map and semismooth reformulations in \secref{algorithms} and provide
regularity conditions and local convergence results.  Finally, 
\secref{summary} summarizes the remainder of this thesis.

Before proceeding, we give a few words about the notation used.  If $F$ is a 
vector valued function, we denote its Jacobian at a point $x$ by $F'(x)$ and 
let $\nabla F(x)$ signify the transposed Jacobian.  The elements of
$F'(x)$ and $\nabla F(x)$ are defined componentwise as follows:
\begin{eqnarray*}
\begin{array}{lrl}
\left[F'(x)\right]_{i,j} & := & \frac{\partial F_i(x)}{\partial x_j} \\
\left[\nabla F(x)\right]_{i,j} & := & \frac{\partial F_j(x)}{\partial x_i}.
\end{array}
\end{eqnarray*}
The gradient of a real valued function $f$ will be denoted by 
$\nabla f$ and will always be viewed as a column vector.  Finally, 
$\ip{\cdot}{\cdot}$ denotes the inner product.

\section{Complementarity}\label{sec:complementarity}
Mixed complementarity problems are specified by three pieces of data, namely 
lower bounds $\ell$, upper bounds $u$, and a function $F$ where we will assume 
throughout this thesis that $F$ is continuously differentiable.

\begin{definition}[Mixed Complementarity Problem]
Given a continuously differentiable function $F:\real^n \rightarrow \real^n$,
and lower and upper bounds
\begin{eqnarray*}
\ell \in \{ \real\cup\{-\infty\}\}^n\\
u \in \{ \real\cup\{+\infty\}\}^n
\end{eqnarray*}
with $[\ell,u]$, the Cartesian product of the closed (possibly unbounded) 
intervals $[\ell_i,u_i]$, nonempty.
Then the {\em mixed complementarity problem},  MCP($F,\ell,u$), is to find 
a $z \in \real^n$ such that {\em precisely} one of the following holds for 
each $i \in \{1, \ldots, n\}$: 
\begin{equation}\label{eqn:comp-conditions}
   \begin{array}{rcl}
   F_i(z) = 0 & \text{ and } & \ell_i \leq z_i \leq u_i \\
   F_i(z) > 0 & \text{ and } & z_i = \ell_i \\
   F_i(z) < 0 & \text{ and } & z_i = u_i.
   \end{array}
\end{equation}
\end{definition}
Two specializations of this framework are easily recognizable.
\begin{definition}[Nonlinear System of Equations] 
The complementarity problem MCP($F,\{-\infty\}^n,\{\infty\}^n$) is equivalent 
to solving a {\em square system of nonlinear equations}: find $z \in \real^n$ 
such that
\[
    F(z) = 0.
\]
\end{definition}
\begin{definition}[Nonlinear Complementarity Problem \cite{cottle:nonlinear}] 
The mixed complementarity problem MCP($F,\{0\}^n,\{\infty\}^n$) is 
equivalent to finding a 
$z \in \real^n$ such that
\begin{equation*}
\begin{array}{rcl}
    0 \leq z & \perp & F(z) \geq 0
\end{array}
\end{equation*}  
where the $\perp$ notation is used to signify that $z$ and $F(z)$ are
orthogonal, $\ip{z}{F(z)} = 0$.  This problem is termed a 
{\em nonlinear complementarity problem}.
\end{definition}
A complete discussion of nonlinear systems of equations can be found in
\cite{ortega.rheinboldt:iterative} while surveys of theory, algorithms, 
and applications for nonlinear complementarity problems can be found in 
\cite{ferris.kanzow:complementarity,harker.pang:finite-dimensional}.
A special case of the nonlinear complementarity problem that has received 
much attention is when $F$ is a linear function, the standard linear 
complementarity problem \cite{cottle.pang.ea:linear}.

For convenience, we will write a mixed complementarity problem as:
\[
\begin{array}{rcl}
\ell \leq z \leq u & \perp & F(z)
\end{array}
\]
where the $\perp$ notation is used in a generalized sense to mean that
at a solution, $z$, \eqnref{comp-conditions} holds for each $z_i$ and $F_i(z)$ 
pair.

We can also pose the mixed complementarity problem as a variational inequality.
\begin{definition}[Variational Inequality \cite{hartman.stampacchia:nonlinear,lions.stampacchia:variational}]
Let $C \subseteq \real^n$ be nonempty, closed and convex, and
$F:\real^n \rightarrow \real^n$ be continuously differentiable.
Then the {\em variational inequality}, VI($F,C$), is to find a $z \in C$ 
such that
\[
\ip{F(z)}{\bar{z} - z} \geq 0 
\]
for all $\bar{z} \in C$.
\end{definition}

The variational inequality can also be written as the generalized 
equation \cite{robinson:generalized*1}:
\begin{eqnarray*}
0 \in F(z) + N_C(z)
\end{eqnarray*}
where $N_C(z)$ denotes the normal cone to $C$ at $z$.
\begin{definition}[Normal Cone \cite{rockafellar:convex}]\label{def:normal}
The {\em normal cone} to a closed convex set $C$ at $z$ is defined by
\[
N_C(z) :=
\left\{
\begin{array}{cl} 
\{y \mid \ip{\bar{z} - z}{y} \le 0,\; \forall \bar{z} \in C\} &
        \mbox{if } z \in C \\
\emptyset & 
        \mbox{otherwise.}
\end{array}\right.
\]
\end{definition}
For example, the normal cone to $[\ell,u]$ can be determined as a Cartesian 
product, namely
\[
N_{[\ell,u]}(z) = \prod_{i=1}^{n} N_{[\ell_i,u_i]}(z_i).
\]
Each component in this product depends on $z_i$, $\ell_i$ and
$u_i$ but is either $\real$, $\real_+$, $\real_-$, $\{ 0 \}$, or 
$\emptyset$, where $\real_+$ denotes the set of nonnegative real numbers 
and $\real_-$ denotes the set of nonpositive real numbers.  In particular,
\[
N_{[\ell_i,u_i]}(z_i) = 
\left\{
  \begin{array}{ll} 
    \real & \text{if } \ell_i = z_i = u_i \\
    \real_- & \text{if } \ell_i = z_i < u_i\\
    \{0\} & \text{if } \ell_i < z_i < u_i \\
    \real_+ & \text{if } \ell_i < z_i = u_i \\
    \emptyset & \text{otherwise.}
  \end{array}
\right.
\]

\begin{theorem}[\cite{karamardian:complementarity}]
The following are equivalent:
\begin{itemize}
\item[(a)] $z$ solves MCP($F,\ell,u$).
\item[(b)] $z$ solves VI($F,[\ell,u]$).
\item[(c)] $0 \in F(z) + N_{[\ell,u]}(z)$.
\end{itemize}
\end{theorem}

Note that variational inequalities are defined over general closed, convex
sets, while the mixed complementarity problem is defined over a box.
However, under suitable constraint qualifications \cite{mangasarian:nonlinear},
variational inequalities can be written as mixed complementarity problems by 
adding multipliers \cite{harker.pang:finite-dimensional}.  One special case we
consider in this thesis is when $C$ is a polyhedral set.
\begin{theorem}(Propositions 1 and 2 of \cite{robinson:reduction})
Let $F:\real^n \rightarrow \real^n$ and
\[
C = [\ell,u] \cap \{z \mid Az \geq b\}
\]
for some $A \in \real^{m\times n}$ and $b \in \real^m$.  Then the following 
hold:
\begin{itemize}
\item[(a)] If $(\bar{z}, \bar{\mu})$ solves the generalized equation
\begin{equation}\label{eqn:box}
0 \in \left[\begin{array}{c} F(z) -A^T\mu \\ Az - b\end{array}\right] +
\left[\begin{array}{c} N_{[\ell,u]}(z) \\ N_{\real^m_+}(\mu)\end{array}\right]
\end{equation}
then $\bar{z}$ solves VI($F,C$).
\item[(b)] If $\bar{z}$ solves VI($F,C$) then the linear optimization problem
\begin{equation}\label{eqn:box-opt}
\begin{array}{cc} \min_{\mu \in \real^m_+} & \ip{A\bar{z} - b}{\mu} \\
\mbox{s.t.} & 0 \in F(\bar{z}) - A^T\mu + N_{[\ell,u]}(\bar{z}).
\end{array}
\end{equation}
has a nonempty solution set.  Further, for any $\bar{\mu}$ 
solving \eqnref{box-opt}, $(\bar{z}, \bar{\mu})$ solves \eqnref{box}.
\end{itemize}
\end{theorem}

\section{Nonsmooth Reformulations}\label{sec:refm}
The mixed complementarity problem can be reformulated as an unconstrained 
system of nonsmooth equations.  The classical reformulation for nonlinear 
complementarity problems uses the minimum map
\[
	\min(z, F(z))
\]
where the minimum is defined componentwise.  Clearly, $\min(z,F(z)) = 0$ if 
and only if $z$ solves the nonlinear complementarity problem defined by $F$.  

Two reformulations of the mixed complementarity problem as an unconstrained 
systems of nonsmooth equation are used in this thesis.  The first is as a 
piecewise smooth system of equations using the normal map, while the second 
is as a semismooth system of equations using the Fischer-Burmeister function.

\subsection{Normal Map}
The first reformulation of the mixed complementarity problem we consider
is as a piecewise smooth system of equations using the normal map 
\cite{eaves:basic,robinson:normal}.  To explain this reformulation, let 
$[\ell,u]$ be a nonempty subset of $\real^n$.  Associated with each 
face $\calF_i$ of $[\ell,u]$ is a (full-dimensional) polyhedral set, 
$\sigma_i = \calF_i + N_{\calF_i}$ where $N_{\calF_i}$ is the normal cone to 
$\calF_i$ at any point in the relative interior of $\calF_i$.  Note that
$N_{\calF_i}$ is constant on the relative interior of $\calF_i$ 
\cite{robinson:normal}.
The collection of these polyhedra comprise a piecewise linear manifold 
of $\real^n$ called the {\em normal manifold} and is denoted by
$\calN_{[\ell,u]}$.  Each $\sigma_i$ is called a {\em cell} of 
$\calN_{[\ell,u]}$.  A full description along with important properties of
the normal manifold are given in \cite{robinson:normal,ralph:branching}.  
For example, the cells of $\calN_{\real^n_+}$ are the orthants of $\real^n$.  

We denote by $\pi_{[\ell,u]}(\cdot)$ the Euclidean projection mapping 
onto $[\ell,u]$.  We note that $\pi_{[\ell,u]}(x)$ can be defined
componentwise as:
\[
\pi_{[\ell_i,u_i]}(x_i) =
\left\{\begin{array}{cr} l_i & \mbox{if } x_i \leq l_i \\
                        u_i & \mbox{if } x_i \geq u_i \\
			x_i & \mbox{otherwise.}
\end{array}\right.
\]

The normal map \cite{robinson:normal} induced by $(F,[\ell,u])$ is the 
function $F_{[\ell,u]}:\real^n \to \real^n$ given by
\[
F_{[\ell,u]}(x) \;=\; F(\pi_{[\ell,u]}(x)) + x - \pi_{[\ell,u]}(x).
\]
The projection map $\pi_{[\ell,u]}(x)$ and hence the normal map 
$F_{[\ell,u]}(x)$ are smooth in the interior of each cell of 
$\calN_{[\ell,u]}$.  Furthermore, $F_{[\ell,u]}$ is a continuous map on
$\real^n$ and the points of nondifferentiability correspond to the 
boundaries of the cells of $\calN_{[\ell,u]}$.

\begin{theorem}
Let MCP($F,\ell,u$) be given.  Then the following hold:
\begin{itemize}
\item[(a)] If $z$ solves MCP($F,\ell,u$) then $F_{[\ell,u]}(z - F(z)) = 0$.
\item[(b)] If $F_{[\ell,u]}(x) = 0$ then $\pi_{[\ell,u]}(x)$ solves MCP($F,\ell,u$).
\end{itemize}
\end{theorem}

\subsection{Semismooth Formulation}
An alternative reformulation writes the mixed complementarity problem as
a system of semismooth equations.  Semismooth functions were introduced 
in \cite{mifflin:semismooth} and have subsequently been extended to vector 
valued functions \cite{qi:convergence,qi.sun:nonsmooth}.  In order to
define the semismooth property, we let $G:\rn\to \rn$ be a locally 
Lipschitzian function and note that by Rademacher's theorem $G$ is 
differentiable almost everywhere.  Let $D_G$ denote the set of points
where $G$ is 
differentiable.
\begin{definition}[B-subdifferential \cite{qi.sun:nonsmooth}]
Let $G:\real^n \rightarrow \real^n$ be locally Lipschitzian at $x$.  
The {\em B-subdifferential} of $G$ at $x$ is
$$
\partial_B G(x):= \left\{
H\mid \exists\{x^k\}, x^k\in D_G,\;\, \hbox{with}\;\, \lim_{x^k\to x}
G'(x^k)=H\right\}.
$$
\end{definition}
\begin{definition}[Clarke subdifferential \cite{clarke:optimization}]
Let $G:\real^n \rightarrow \real^n$ be locally Lipschitzian at $x$.  The 
{\em Clarke subdifferential} of $G$ at $x$ is defined as
$$
\partial G(x):= co\;\partial_B G(x),
$$
where $co$ denotes the convex hull of a set.
\end{definition}

We can now define semismooth functions, which lie between Lipschitz functions 
and continuously differentiable functions.
\begin{definition}[Semismooth]
Let $G: \rn\to \rn$ be locally Lipschitzian at $x\in\rn$.  We say 
that $G$ is {\em semismooth at $x$} if  
\[
\lim_{\stackrel{\scriptstyle H\in\partial G(x+tv')}{v'\to
v,t\downarrow 0}} Hv' 
\]
exists for all $v\in \rn$.  Furthermore, if $G$ is semismooth at each 
$x \in \real^n$ then $G$ is said to be a {\em semismooth function}.
\end{definition}
\begin{definition}[Strongly Semismooth]
Let $G: \rn\to\rn$ be locally Lipschitzian and suppose that $G$ is 
semismooth at $x$. We say that $G$ is {\em strongly semismooth at $x$} 
if for any $H\in \partial G(x+d)$, and for any $d\to 0$,
\[
Hd-G'(x;d)= O(\|d\|^2).
\]
Furthermore, if $G$ is strongly semismooth at each $x \in \real^n$, then
$G$ is said to be a {\em strongly semismooth function}.
\end{definition}
Note that if $G$ is semismooth at $x$ then it is also directionally 
differentiable at $x$.

To describe the semismooth reformulation of a complementarity problem we first 
define an NCP-function.
\begin{definition}[NCP-function]
We call a mapping
$ \phi : \real^2 \to \real $ an {\em NCP-function} if it satisfies
\[
   \phi (a,b) = 0 \Longleftrightarrow 0 \leq a \;\perp\; b \ge 0.
\]
\end{definition}
One example of an NCP-function is the Fischer-Burmeister
\cite{fischer:special} function
\begin{equation*}
   \phi_{FB} (a,b) := \sqrt{a^2+b^2}-a-b.
\end{equation*}

We then partition the index set $ I = \{ 1, \ldots, n \} $ in 
the following way:
\begin{eqnarray*}
   I_l & := & \{ i \in I \, | \, - \infty < l_i < u_i = + \infty \}, \\
   I_u & := & \{ i \in I \, | \, - \infty = l_i < u_i < + \infty \}, \\
   I_{lu} & := & \{ i \in I \, | \, - \infty < l_i < u_i < + \infty \}, \\
   I_f & := & \{ i \in I \, | \, - \infty = l_i < u_i = + \infty \}.
\end{eqnarray*}
That is, $ I_l, \, I_u, \, I_{lu} $ and $ I_f $ denote the set of 
indices $ i \in I $ with finite lower bounds only, finite
upper bounds only, finite lower and upper bounds, and no finite bounds
on the variable $ x_i $, respectively.  Hence, the subscripts in the above
index sets indicate which bounds are finite, with the only exception 
of $ I_f $ which contains the free variables.

Following the idea in \cite{billups:algorithms}, we then define the operator 
$ \Phi : \rn \to \rn $ componentwise as:
\[
   \Phi_i (x) := \left\{ \begin{array}{ll}
   \phi_{FB} (x_i- l_i, F_i (x)) & \mbox{if } i \in I_l, \\
   - \phi_{FB} (u_i-x_i, - F_i (x)) & \mbox{if } i \in I_u, \\
   \phi_{FB} (x_i - l_i, \phi_{FB} (u_i - x_i, - F_i (x))) &
   \mbox{if } i \in I_{lu}, \\
   - F_i(x) & \mbox{if } i \in I_f.
   \end{array} \right.
\]
\begin{theorem}[\cite{billups:algorithms}]  
The following hold:
\begin{itemize}
\item[(a)] $\Phi(z) = 0$ if and only if $z$ solves MCP($F,\ell,u$).
\item[(b)] $\Phi$ is semismooth.
\item[(c)] If $F$ has Lipschitz derivatives, then $\Phi$ is 
strongly semismooth.
\end{itemize}
\end{theorem}

\section{Existence of Solutions}\label{sec:existence}
Having defined the mixed complementarity problem and presented the 
reformulations used in this thesis, we now turn our attention toward 
conditions guaranteeing the existence of a solution to a mixed complementarity 
problem.  
We split the existence results into those for linear and nonlinear models.

\subsection{Linear Problems}
Existence and uniqueness results for linear complementarity problems
have to do with matrix classes.  Throughout this section we will deal
with the linear mixed complementarity problem LMCP($M,q,\ell,u$) where
$M \in \real^{n\times n}$ and $q \in \real^n$.  LMCP($M,q,\ell,u$) is
the mixed complementarity problem defined by $F(z) := Mz + q$, $\ell$, and $u$.

We then define the following matrix classes \cite{cottle.pang.ea:linear}:
\begin{definition}[Positive Semidefinite] 
If 
\[
x^TMx \geq 0
\]
for all $x \in \real^n$, then $M$ is a {\em positive semidefinite} matrix.
\end{definition}
\begin{definition}[Positive Definite] 
If 
\[
x^TMx > 0
\]
for all $x \in \real^n$ with $x \neq 0$, then $M$ is a {\em positive definite}
matrix.
\end{definition}
\begin{definition}[$P_0$-Matrix] 
If all the principal minors of $M$ are nonnegative,
$M$ is called a {\em $P_0$-matrix}.
\end{definition}
\begin{definition}[$P$-Matrix] 
If all the principal minors of $M$ are positive, then
$M$ is called a {\em $P$-matrix}.  
Alternative characterizations of $P$-matrices 
can be found in \cite{fiedler.ptak:matrices}.  
\end{definition}

Using these definitions, we have the following existence results for
any linear mixed complementarity problem LMCP($M,q,\ell,u$).
\begin{theorem}[\cite{cottle.pang.ea:linear}]
The following hold:
\begin{itemize}
\item[(a)] If $M$ is positive semidefinite then LMCP($M,q,\ell,u$) has a convex
solution set.
\item[(b)] If $M$ is positive definite, then LMCP($M,q,\ell,u$) has a unique
solution for all $q$.
\end{itemize}
\end{theorem}
See \cite{cottle.pang.ea:linear} for further matrix classes and results
for standard linear complementarity problems.

A complete characterization of existence and uniqueness of a solution
for the standard linear complementarity problem can be made using the 
$P$-matrix property.
\begin{theorem}[\cite{cottle.pang.ea:linear}] The following are
equivalent:
\begin{itemize}
\item[(a)] $M$ is a $P$-matrix.
\item[(b)] LMCP($M,q,\{0\}^n,\{\infty\}^n$) has a unique solution for all $q$.
\end{itemize}
\end{theorem}

A generalization of the $P$-matrix property used with linear mixed 
complementarity problems is for $M_{[\ell,u]}$, the normal map associated 
with $M$, to be coherently oriented.
\begin{definition}[Coherent Orientation \cite{robinson:normal}] 
$M_{[\ell,u]}$ is {\em coherently oriented} if the determinants of the 
affine maps associated with each cell of the normal manifold of $M_{[\ell,u]}$ 
have the same nonzero sign.
\end{definition}
\begin{theorem}[\cite{robinson:normal}]
The following are equivalent:
\begin{itemize}
\item[(a)] The normal map $M_{[\ell,u]}$ is a Lipschitzian homeomorphism of
$\real^n$ onto $\real^n$.
\item[(b)] $M_{[\ell,u]}$ is coherently oriented.
\end{itemize}
In particular, if $M_{[\ell,u]}$ is coherently oriented, then 
$M_{[\ell,u]} + q = 0$ has a unique solution for all $q$.
\end{theorem}
For standard linear complementarity problems, coherent orientation of the
normal map is equivalent to $M$ being a $P$-matrix since the orthants are
precisely the cells of $M_{[\{0\}^n,\{\infty\}^n]}$.

\subsection{Nonlinear Problems}
Existence results for nonlinear mixed complementarity problems are 
generalizations of those encountered when dealing with linear problems.
A basic existence result for nonlinear models based on Brouwer's fixed-point 
theorem is when $[\ell,u]$ is nonempty and compact.
\begin{theorem}
If $[\ell,u]$ is nonempty and compact then MCP($F,\ell,u$) has a solution
for any continuous $F$.
\end{theorem}

Monotonicity plays a key role in existence results for nonlinear models.  
Let $C \subseteq \real^n$ be nonempty, closed, and convex.  We then 
distinguish between three forms of monotonicity over the set $C$.
\begin{definition}[Monotone]  
If 
\[
\ip{z - \bar{z}}{F(z) - F(\bar{z})} \geq 0
\]
for all $z \in C$ and $\bar{z} \in C$ then $F$ is {\em monotone} on $C$.
\end{definition}
\begin{definition}[Strictly Monotone] 
If 
\[
\ip{z - \bar{z}}{F(z) - F(\bar{z})} > 0
\]
for all $z \in C$ and $\bar{z} \in C$ with $z \neq \bar{z}$, then $F$ is 
{\em strictly monotone} on $C$.   
\end{definition}
\begin{definition}[Strongly Monotone] 
If for some scalar $\mu > 0$, 
\[
\ip{z - \bar{z}}{F(z) - F(\bar{z})} \geq \mu\norm{z - \bar{z}}^2
\] 
for all $z \in C$ and $\bar{z} \in C$ then $F$ is {\em strongly monotone with 
modulus $\mu$} on $C$.
\end{definition}

Using these definitions, we have the following existence results for nonlinear
complementarity problems.
\begin{theorem}[\cite{harker.pang:finite-dimensional}]
Let $F:\real^n \rightarrow \real^n$ be continuous on $\real^n$.  Then the
following statements hold:
\begin{itemize}
\item[(a)] If $F$ is monotone on $[\ell,u]$, then MCP($F,\ell,u$) has a convex 
solution set.
\item[(b)] If $F$ is strictly monotone on $[\ell,u]$, then MCP($F,\ell,u$) has at
most one solution.
\item[(c)] If $F$ is strongly monotone on $[\ell,u]$, then MCP($F,\ell,u$) has a
unique solution.
\end{itemize}
\end{theorem}
Note that monotone and strictly monotone problems might have \textit{no}
solution.  

Since we are assuming that $F$ is continuously differentiable on $\real^n$, 
we can characterize monotonicity using the Jacobian of $F$.
\begin{theorem}[\cite{ortega.rheinboldt:iterative}]
The following hold:
\begin{itemize}
\item[(a)] $F$ is monotone on $C$ if and only if $F'(x)$ is positive semidefinite 
for all $x \in C$.
\item[(b)] If $F$ is strictly monotone on $C$ then $F'(x)$ is positive definite for
all $x \in C$.
\item[(c)] $F$ is strongly monotone with modulus $\mu$ on $C$ if and only if
for all $\bar{x} \in C$,
\[
x^TF'(\bar{x})x \geq \mu x^Tx
\]
for all $x \in C$.
\end{itemize}
\end{theorem}

The $P$-matrix property for linear complementarity problems can be extended 
to nonlinear mixed complementarity problems using the notion of a
$P$-function.
\begin{definition}[$P$-function] 
If 
\[
\max_{1 \le i \le n} (F_i(x) - F_i(y))(x_i - y_i) > 0
\]
for all $(x,y) \in [\ell,u]$ with $x \neq y$, then $F$ is called a 
{\em $P$-function}.
\end{definition}
\begin{definition}[Uniform $P$-function]
If there exists a scalar $\mu > 0$ such that 
\[
\max_{1 \le i \le n} (F_i(x) - F_i(y))(x_i - y_i) \ge \mu \norm{x - y}_2^2
\]
for all $(x,y) \in [\ell,u]$ then $F$ is called a
uniform $P$-function.
\end{definition}
\begin{theorem}[\cite{harker.pang:finite-dimensional}]
The following hold:
\begin{itemize}
\item[(a)] If $F$ is a $P$-function then MCP($F,\ell,u$) has at most one solution.
\item[(b)] If $F$ is a uniform $P$-function then MCP($F,\ell,u$) has a
unique solution.
\end{itemize}
\end{theorem}
Note that a strictly monotone function is a $P$-function, while a strongly 
monotone function is a uniform $P$-function.

Additional conditions using degree theory for the existence of a solution 
can be found in \cite{gowda.pang:stability}.

\section{Algorithms and Regularity}\label{sec:algorithms}
We now have conditions that guarantee the existence of a solution to
a mixed complementarity problem.  This section discusses some algorithms
for computing a solution.

Newton's method, perhaps the most famous solution technique, has been 
extensively used in practice to solve nonlinear systems of equations.
The essential idea is to form a linear approximation to the nonlinear
function.  Solving the resulting linear system of equations produces
the next iterate.
\begin{equation}\label{eqn:sm_newt}
	x^{k+1} = x^k - F'(x^k)^{-1}F(x^k)
\end{equation}
\begin{theorem}[\cite{ortega.rheinboldt:iterative}]
Let $F:\rn\to\rn$ be continuously differentiable and $x^*$ be such that 
$F(x^*) = 0$ and $F'(x^*)$ is nonsingular.  Then the following hold:
\begin{itemize}
\item[(a)] The iteration in \eqnref{sm_newt} is well-defined and converges to
$x^*$ superlinearly in a neighborhood of $x^*$.
\item[(b)] If in addition $F$ has locally Lipschitz derivatives at $x^*$, then 
the rate of convergence is quadratic.
\end{itemize}
\end{theorem}
Nonsingularity of the Jacobian is a regularity condition used in conjunction 
with Newton's method to show the convergence and rate of convergence results.
We will be dealing with generalizations of Newton's method for nonsmooth 
systems of equations and will therefore define generalized regularity 
conditions.

We consider two algorithms based on Newton's method in this thesis.  
The first method is the nonsmooth Newton method developed in 
\cite{josephy:newton,josephy:newtons*1,josephy:newtons} for generalized 
equations \cite{robinson:generalized*1}.  Each iteration solves a (linear) 
generalized equation for $z^{k+1}$:
\begin{equation}\label{eqn:josephy}
	0 \in F(z^k) + F'(z^k)(z^{k+1} - z^k) + N_{[\ell,u]}(z^{k+1}).
\end{equation}
This system is a linear complementarity problem which can be solved using
Lemke's method \cite{lemke:bimatrix,lemke.howson:equilibrium}.

To show the local convergence of this method, we need to use a generalization 
of the nonsingularity of the Jacobian matrix.  The generalization used is the 
notion of strong regularity at a solution.  In order to define strong 
regularity, we introduce a partitioning of the set $I = \{1, \cdots, n\}$ 
given $z^*$, a solution to MCP($F,\ell,u$).
\begin{equation}\label{eqn:iidx}
\begin{array}{rcr}
   \alpha(z^*) & := & \{ i \, | \, l_i < z_i^* < u_i, F_i (z^*) = 0 \}, \\
   \beta(z^*) & := & \{ i \, | \, z_i^* \in \{ l_i, u_i \}, F_i (z^*) = 0 \}, \\
   \gamma(z^*) & := & \{ i \, | \, z_i^* \in \{ l_i, u_i \}, F_i (z^*) \not= 0\}.
\end{array}
\end{equation}
\begin{definition}[Strong Regularity \cite{robinson:strongly,facchinei.fischer.ea:semismooth}]
Let $z^*$ be a solution to the complementarity problem MCP($F,\ell,u$).  Then 
MCP($F,\ell,u$) is {\em strongly regular at $z^*$} if the submatrix 
$F'(z^*)_{\alpha\alpha}$ is nonsingular and the Schur-complement
\[
 F'(x^*)_{\alpha \cup \beta, \alpha \cup \beta} (z^*)/
         F'(z^*)_{\alpha \alpha} := F'(z^*)_{\beta \beta} -
         F'(z^*)_{\beta \alpha} F'(z^*)_{\alpha \alpha}^{-1}
         F'(z^*)_{\alpha \beta}
\]
is a $P$-matrix, where the index sets $\alpha$ and $\beta$ are defined in
\eqnref{iidx}.
\end{definition}
If MCP($F,\ell,u$) is strongly regular at a solution $z^*$ and $F'(z^*)$
satisfies a Lipschitz continuity assumption, then the Newton-like method 
in \eqnref{josephy} is locally quadratic convergent.  However, it is not
globally convergent.  An ad-hoc linesearch was proposed for this method
\cite{mathiesen:computation,mathiesen:computational,mathiesen:algorithm} 
in an attempt to obtain global convergence and implemented in 
MILES \cite{rutherford:miles}.  

A similar method uses the normal map reformulation of the 
complementarity 
problem \cite{robinson:newtons}.  Global convergence of this method
is achieved by damping the Newton method with a pathsearch \cite{ralph:global}
on the two-norm of the normal map squared as a merit function.  The resulting 
method is the basis for the implementation in PATH 
\cite{dirkse:robust,dirkse.ferris:path,dirkse.ferris:pathsearch}.
A nonmonotone pathsearch 
\cite{grippo.lampariello.ea:nonmonotone,grippo.lampariello.ea:class,ferris.lucidi:nonmonotone} 
and a crashing method \cite{dirkse.ferris:crash} are used in the code to 
improve robustness and efficiency.

An alternative algorithm is based on the semismooth reformulation. 
If $G:\rn\to\rn$ is a semismooth function, we can define the Newton iteration 
as
\begin{equation}\label{eqn:newton}
x^{k+1}=x^k-(H^k)^{-1}G(x^k),\qquad
\end{equation}
where $H^k$ is any element in $\partial_B G(x^k)$.  The generalization of 
the nonsingularity of the Jacobian used with this method is the notion of 
BD-regularity.
\begin{definition}[BD-Regularity] 
A semismooth function $G$ is BD-regular at a point $x$ if all the
elements in $\partial_B G(x)$ are nonsingular.
\end{definition}
\begin{theorem}[\cite{deluca.facchinei.ea:semismooth}]
Let $G:\rn\to\rn$ be a semismooth function and $x^*$ be such that 
$G(x^*)=0$ and $G$ is BD-regular at $x^*$.  Then the following hold:
\begin{itemize}
\item[(a)] The iteration in \eqnref{newton} is well-defined and converges to
$x^*$ superlinearly in a neighborhood of $x^*$.
\item[(b)] If in addition $G$ is directionally differentiable in a
neighborhood of $x^*$ and strongly semismooth at $x^*$, then the rate
of convergence is quadratic.
\end{itemize}
\end{theorem}
We can then apply this method to solve the system $\Phi(x) = 0$.  To obtain 
global convergence, the basic method is damped with an Armijo 
\cite{armijo:minimization} linesearch on the two-norm of $\Phi(\cdot)$.


Note that strong regularity and BD-regularity are related.  As proven in
\chapref{path}, if $F$ is strongly regular at $x^*$ then $\Phi$ is BD-regular 
at $x^*$.

\section{Summary}\label{sec:summary}
We have presented a precise definition of the mixed
complementarity problem and
have investigated several reformulations as nonsmooth systems of equations
along with basic existence results.  We also mentioned two algorithms
for solving the complementarity problem that are globally and locally fast
convergent under suitable conditions.  

The remainder of this thesis concentrates on algorithms and environments 
for solving complementarity problems.  Many environments are available to 
practitioner for expressing complementarity problems.  Modeling languages 
\cite{bisschop.meeraus:development,fourer.gay.ea:modeling}, such as AMPL 
\cite{fourer.gay.ea:ampl} and GAMS \cite{brooke.kendrick.ea:gams}, provide 
natural facilities for representing mathematical programs.  Recently, 
improvements to these packages for modeling complementarity relationships 
\cite{dirkse.ferris.ea:gams,ferris.fourer.ea:expressing} have been made.  
Other tools, such as MATLAB \cite{matlab:users} and NEOS 
\cite{czyzyk.mesnier.ea:network-enabled,ferris.mesnier.ea:neos}, can also be 
used to communicate a complementarity problem to a solver.
\chapref{environments} surveys the mechanisms available in these packages
for conveying complementarity problems.  In particular, the new links to the 
MATLAB and NEOS tools that have been developed are documented.

Support for these packages is provided in PATH 4.x and SEMI through the
customizable solver interface specified in \chapref{interfaces}.  The main 
design feature is the abstraction of core components from the algorithm with 
implementations tailored to a particular environment supplied either at 
compile or 
run time.  The components include mechanisms for specifying the function 
and Jacobian evaluations required in the complementarity problem definition.
Other components deal with memory allocation and interrupt handling.  
Individuals who want to embed the PATH 4.x or SEMI codes into larger 
applications will benefit from the documentation in \chapref{interfaces}.

New techniques for preprocessing 
complementarity problems are documented in \chapref{preprocessing}.  
The benefits of preprocessing have long been known to the linear 
\cite{andersen.andersen:presolving,brearley.mitra.ea:analysis} and 
mixed integer \cite{savelsbergh:preprocessing} programming communities, where
preprocessing techniques typically are used to reduce the size and complexity 
of a model prior to solving it.  For example, wasted computation is avoided 
when the preprocessor determines that a model has no solution.  In 
complementarity, we use the variational inequality representation and
existence and uniqueness results to eliminate variables from a model.  An 
implementation of the preprocessing techniques developed in 
\chapref{preprocessing} are contained in PATH 4.x and SEMI, which are the 
first codes for solving complementarity problems with preprocessing 
technology.

Developing a practical model of a complex situation is a difficult task in 
which an approximate representation is initially constructed and then 
iteratively refined until an accurate formulation is obtained.  During the 
intermediate stages, the models generated have a tendency to be ill-defined, 
poorly conditioned, and/or singular.  Information generated by a solver can 
help the modeler to detect these problems, quickly locate the source, and make 
appropriate modifications to the model.  The diagnostic information
reported by PATH 4.x and SEMI is the subject of \chapref{diagnostic}.

The remaining chapters of the thesis concentrate on the PATH 4.x and SEMI
algorithms and implementations.  
PATH 4.x offers improved reliability over prior versions of the code and
has been able to find solutions to previously unsolvable models.
PATH is based on a nonsmooth Newton method for the normal map 
\cite{robinson:newtons,ralph:global}.  A key 
problem encountered by this method is when a solution to the linear 
complementarity subproblem cannot be found.  PATH uses heuristics in this
case in an attempt to overcome the difficulty.  New theory is developed 
in \chapref{path} for a globalization scheme based on the Fischer-Burmeister 
merit function \cite{fischer:special} as modified in 
\cite{billups:algorithms} for mixed complementarity problems and incorporated
into PATH 4.x.
Using this new theory, we can resort to a projected gradient step on the
(differentiable) 
merit function when a solution to the linear complementarity problem
cannot be found.  The resulting algorithm is well-defined for arbitrary 
complementarity problems, has strong global convergence properties, and is 
locally fast convergent under a strong regularity assumption.
Enhancements made to the linear complementarity solver, nonmonotone 
linesearch, and restart strategies are also partially responsible for 
the improved robustness of PATH 4.x.  These enhancements are documented 
in \chapref{path}.

The main computation per iteration in PATH 4.x is to solve a linear
complementarity problem, which can be an expensive operation.  A seemingly
more attractive approach is to use an algorithm that only solves a linear
system of equations at each iteration.  SEMI is based on the semismooth 
algorithm \cite{deluca.facchinei.ea:theoretical} and has this property.
The method uses the Fischer-Burmeister \cite{fischer:special} and penalized 
Fischer-Burmeister \cite{chen.chen.ea:penalized} functions in the 
implementation and can use iterative methods, such as 
LSQR \cite{paige.saunders:lsqr}, 
GMRES \cite{saad:iterative,walker:implementation}, and QMR 
\cite{freund.nachtigal:qmrpack}, to solve the linear system of equations
generated at each iteration.  The iterative methods can be used in the code 
to solve very large models.  A complete description of the new SEMI code is 
contained in \chapref{semi}.

The theme of this thesis is ``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.  

\begin{comment}
\chapref{mpec} ties the algorithms, solver interfaces,
and environments together to solve mathematical programs with equilibrium 
constraints \cite{luo.pang.ea:mathematical} using the bundle method
\cite{outrata.kocvara.ea:nonsmooth}.  
\end{comment}

