Convergence of infeasible-interior-point methods for self-scaled conic programming

Bharath Kumar Rangarajan (bharathorie.cornell.edu)
Michael Todd (miketoddcs.cornell.edu)

Abstract: We present results on global and polynomial-time convergence of infeasible-interior-point methods for self-scaled conic programming, which includes linear and semidefinite programming. First, we establish global convergence for an algorithm using a wide neighborhood. Next, we prove polynomial complexity for the algorithm with a slightly narrower neighborhood. Both neighborhoods are related to the wide (minus infinity) neighborhood and are much larger than the 2-norm neighborhood. We also provide stopping rules giving an indication of infeasibility.

Keywords: Conic Programming, Self-Scaled Cones, Interior-Point Methods, Polynomial Convergence, Infeasibility Indicators.

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Technical Report TR1388, Department of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853. Date: October 10, 2003.

Download: [Postscript][Compressed Postscript]

Entry Submitted: 11/27/2003
Entry Accepted: 11/27/2003
Entry Last Modified: 11/27/2003

Modify/Update this entry