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