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