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