Optimization Online


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

James Renegar(renegar***at***cornell.edu)
Mutiara Sondjaja(sondjaja***at***sims.nyu.edu)

Abstract: 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.

Keywords: affine-scaling, interior-point methods, semidefinite programming, hyperbolic programming

Category 1: Linear, Cone and Semidefinite Programming

Citation: arXiv:1410.6734

Download: [PDF]

Entry Submitted: 10/26/2014
Entry Accepted: 10/27/2014
Entry Last Modified: 10/26/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society