Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices

TLDR

The SDLCP generalizes the linear complementarity problem, with a central trajectory guaranteed when the feasible region has nonempty interior and the affine subspace is monotone. This work aims to develop a theoretical foundation for interior‑point methods that use Newton directions to follow the central trajectory of the monotone SDLCP. The authors formulate the SDLCP as finding symmetric positive semidefinite matrices in an affine subspace that satisfy a zero inner‑product complementarity condition, and design interior‑point algorithms that exploit this structure.

Abstract

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