Etude théorique et numérique de quelques méthodes de points intérieurs pour l’optimisation quadratique semi-définie

Abstract

The primal-dual central-path method is effective for solving various optimization problems, particularly Semidefinite Quadratic Programming (QSDP). Theoretically, it offers superior polynomial complexity—on the order of $O(n \log(1/\epsilon))$—yet the method presents challenges due to the lack of directional symmetry and the difficulty of obtaining a strictly feasible point (an issue not addressed in this study) given the proximity measure $\delta(X, Z, \mu) < 1/2$. In this thesis, we develop a small-step primal-dual central-path algorithm to solve the QSDP problem. Our study makes the following contributions: - Establishing a sufficient condition to ensure the strict feasibility of the full Newton step. - Determining the impact of the full Newton step on the duality gap. - Establishing the rate of $\mu$-reduction required to remain close to the central path in the QSDP case, where directions are not orthogonal. - Establishing the existence and uniqueness of the (NT) displacement direction via a sufficient condition, which generalizes the result obtained by Todd, Toh, and Tütüncü for SDP.