Interior-point methods for the monotone semidefinite
linear complementarity problem in symmetric matrices
Masakazu Kojima, Susumu Shindoh, Shinji Hara
The SDLCP (semidefinite linear complementarity problem)
in symmetric matrices introduced in this paper provides a unified
mathematical model for various problems arising from systems and
control theory and combinatorial optimization. It is defined as
the problem of finding a pair $(\X,\Y)$ of $n \times n$ symmetric
positive semidefinite matrices which lies in a given $n(n+1)/2$
dimensional affine subspace $\FC$ of $\SC^2$ and satisfies the
complementarity condition $\X \bullet \Y = 0$, where $\SC$ denotes
the $n(n+1)/2$ dimensional linear spaces of symmetric matrices and
$\X \bullet \Y$ the inner product of $\X$ and $\Y$. The problem
enjoys a close analogy with the LCP in the Euclidean space.
In particular, the central trajectory leading to a solution of
the problem exists under the nonemptiness of the interior of the
feasible region and a monotonicity assumption on the affine
subspace $\FC$. The aim of this paper is to establish a theoretical
basis of interior-point methods with the use of Newton directions
toward the central trajectory for the monotone SDLCP.
Research Reports on Information Sciences, No. B-282,
Department of Mathematical and Computing Sciences,
Tokyo Institute of Technology, April, 1994, Revised April 1995.