Primal-dual interior-point Methods for Semidefinite Programming from an algebraic point of view, or: Using Noncommutativity for Optimization

Abstract

Since more than three decades, interior-point methods proved very useful for optimization, from linear over semidefinite to conic (and partly beyond non-convex) programming; despite the fact that already in the semidefinite case (even when strong duality holds) "hard" problems are known. We shade a light on a rather surprising restriction in the non-commutative world (of semidefinite programming), namely "commutative" paths and propose a new family of solvers that is able to use the full richness of "non-commutative" search directions: (primal) feasible-interior-point methods. Beside a detailed basic discussion, we illustrate some variants of "non-commutative" paths and provide a simple implementation for further (problem specific) investigations.

49 pages, 10 figures, 3 tables, 5 Octave/Matlab files; slightly updated version