%A Menglin Cao
%T Piecewise Linear Homotopies and Affine Variational Inequalities
%D January 1994
%R TR 1210
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X The purpose of this thesis is to apply the theory of piecewise linear
homotopies and the notion of a normal map in the construction and analysis
of algorithms for affine variational inequalities.
An affine variational inequality can be expressed as a piecewise linear
equation $A_C(x)=a$, where $A$ is a linear transformation from
$\real^n$ to $\real^n$, $C$ is a polyhedral convex subset of
$\real^n$, and $A_C$ is the associated normal map. We introduce
a path-following algorithm for solving the equation $A_C(x)=a$.
When $A_C$ is coherently oriented, we prove that the path
following method terminates at the unique solution of $A_C(x)=a$.
This generalizes the fact that Lemke's method terminates at the unique
solution of $\lcp{q}{M}$ with $M$ being a $P$--matrix.
In LCP study, termination of Lemke's method is established for two
major classes of matrices, the class of $L$--matrices introduced by
Eaves and the class of $P_0$--matrices studied by Cottle et al.
We generalize the notion of $L$--matrices for polyhedral convex sets
in $\real^n$ and prove that, when $A$ is a linear transformation
associated with such matrices, our algorithm will find a solution for
$A_C(x)=a$. unless the it is infeasible in a well specified sense.
Our approach to $P_0$ begins with the study of geometric
characteristics of an LCP that contribute to the finite termination
of Lemke's method. Given $K(M)$ as the set of
solvable right hand sides for the matrix $M$ and $\sol{q}{M}$
as the set of solutions for $\lcp{q}{M}$, we prove that the
convexity of $K(M)$ and the connectedness of $\sol{q}{M}$ for
all $q \in \real^n$ guarantee finite termination of Lemke's
method. We study those matrices such that $\sol{q}{M}$ is
connected for all $q \in \real^n$ as a matrix class, denoted
by $P_c$. We are interested in how $P_c$ is
related to $P_0$.
We also study variational inequalities from the perspective of
maximal monotone multifunction theory. Our results are presented
in the last two chapters.