Polynomial Convergence of Infeasible-Interior-Point Methods over Symmetric Cones

We establish polynomial-time convergence of infeasible-interior-point methods for conic programs over symmetric cones using a wide neighborhood of the central path. The convergence is shown for a commutative family of search directions used in Schmieta and Alizadeh [Math. Program., 96 (2003), pp. 40...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on optimization 2006-01, Vol.16 (4), p.1211-1229
Main Author: Rangarajan, Bharath Kumar
Format: Article
Language:English
Subjects:
Algebra
Algorithms
Neighborhoods
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We establish polynomial-time convergence of infeasible-interior-point methods for conic programs over symmetric cones using a wide neighborhood of the central path. The convergence is shown for a commutative family of search directions used in Schmieta and Alizadeh [Math. Program., 96 (2003), pp. 409-438]. Monteiro and Zhang [Math. Program., 81 (1998), pp. 281-299] introduced this family of directions when analyzing semidefinite programs. These conic programs include linear and semidefinite programs. This extends the work of Rangarajan and Todd [Tech. rep. 1388, School of OR & IE, Cornell University, Ithaca, NY, 2003], which established convergence of infeasible-interior-point methods for self-scaled conic programs using the NT direction. Our work is built on earlier analyses by Faybusovich [J. Comput. Appl. Math., 86 (1997), pp. 149-175] and Schmieta and Alizadeh [Math. Program., 96 (2003), pp. 409-438]. Of independent interest, we provide a constructive proof of Lyapunov lemma in the Jordan algebraic setting.
ISSN:1052-6234
1095-7189
DOI:10.1137/040606557