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