UC Berkeley

In this thesis, we study two generalizations of the classical linear complementarity problem (LCP) - the weighted extended linear complementarity problem (wXLCP) and the complementarity problem (CP) over a general closed cone. Our goal is twofold: extend some fundamental results of the LCP to a more general setting and identify a class of nonmonotone problems which could be solved numerically. The thesis is organized as follows:

In Chapter 1, we formulate problems relevant to our study and introduce background material that will be needed in the rest of the thesis.

In Chapter 2, we formulate the weighted extended linear complementarity problem (XLCP), which naturally generalizes the LCP, the horizontal linear complementarity problem (HLCP) and the extended linear complementarity problem (XLCP). Motivated by important roles played by matrix theoretic properties in the LCP theory, we study the monotonicity, sufficiency, $P$-property and $R_0$-property in the setting of the XLCP. Together with two optimization reformulations of the problem, we establish several fundamental results. Specifically, we show that the characterizing conditions of the row and column sufficiency properties in \cite{Gowda95} can be similarly described in the context of the wXLCP. Under the monotonicity property, the wXLCP is equivalent to a convex optimization problem and it is solvable whenever it is strictly feasible. Also, we show that the row sufficiency property ensures that every stationary point of some unconstrained optimization problem is a solution of the wXLCP.

In Chapter 3, we confine our discussions on the notion of \emph{uniform non-singularity property} for transformations defined over an Euclidean space $\Euclidsp$. The motivation is to identify a more general class of nonmonotone symmetric cone complementarity problems (SCCPs) which are numerically solvable. When $\Euclidsp = \reals^n$, the uniform non-singularity property lies strictly between the notion of $P$-function and uniform $P$-function; and it yields a new characterization of the $P$-matrix when the function is linear. Under suitable assumptions, the uniform non-singularity property recovers the strong monotonicity and a weaker version of the Cartesian $P$-property. We also make connections to other existing $P$-type properties, and show that they are all equivalent for two special cases.

\item In Chapter 3, we propose the general notion of uniform nonsingularity property for transformations over Euclidean spaces. We show that this property is closely related to a number of existing properties in the literature. In particular, the variants of the uniform non-singularity property recover $P$-property of a matrix, the strong monotonicity of a nonlinear transformation, and a weaker version of the Cartesian $P$-property \cite{ChenQi06} and the $P$-type property in \cite{ChuaYi10}. Also, we show that a form of this property implies the Lipschitzian GUS-property.

In Chapter 4, we present the applications of the uniform non-singularity property to the solution property of complementarity problems over general closed convex cones. With the help of the barrier based smoothing approximation of the normal-map formulation of complementarity problems, we develop a homotopy path whose accumulation point is a solution of the problem. Moreover, we show that the path is convergent and every solution of the complementarity problem comes from the limit of the path, whence establishing the uniqueness of solution.