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

2018/12/26 by Schrempf, Konrad
#90C05 (Secondary) #90C22 #90C51 (Primary) #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1812.10278

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.

Related

• Semidefinite Programming
• Complexity analysis of interior-point methods for second-order stationary points of nonlinear semidefinite optimization problems
• Primal-Dual Interior-Point Methods for Domain-Driven Formulations
• Interior-point algorithms with full Newton steps for nonsymmetric convex conic optimization
• Analysis of the primal-dual central path for nonlinear semidefinite optimization without the nondegeneracy condition