Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices

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 x n symmetric positive semidefinite matrices which lies in a given n(n + 1)/2 dimensional affine subspace F of S-2 and satisfies the complementarity condition X . Y = 0, where S denotes the n(n + 1)/2-dimensional linear space of symmetric matrices and X . 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 F. 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.