A Polynomial-Time Affine-Scaling Method for Semidefinite and Hyperbolic Programming

James Renegar, Mutiara Sondjaja

Published 2014-10-24Version 1

We develop a natural variant of Dikin's affine-scaling method, first for semidefinite programming and then for hyperbolic programming in general. We match the best complexity bounds known for interior-point methods. All previous polynomial-time affine-scaling algorithms have been for conic optimization problems in which the underlying cone is symmetric. Hyperbolicity cones, however, need not be symmetric. Our algorithm is the first polynomial-time affine-scaling method not relying on symmetry.