Optimization Online


''Cone-Free'' Primal-Dual Path-Following and Potential Reduction Polynomial Time Interior-Point Methods

Arkadi Nemirovski (nemirovs***at***ie.technion.ac.il)
Levent Tuncel (ltuncel***at***math.uwaterloo.ca)

Abstract: We present a framework for designing and analyzing primal-dual interior-point methods for convex optimization. We assume that a self-concordant barrier for the convex domain of interest and the Legendre transformation of the barrier are both available to us. We directly apply the theory and techniques of interior-point methods to the given good formulation of the problem (as is, without a conic reformulation) using the very usual primal central path concept and a less usual version of a dual path concept. We show that many of the advantages of the primal-dual interior-point techniques are available to us in this framework and therefore, they are not intrinsically tied to the conic reformulation and the logarithmic homogeneity of the underlying barrier function.

Keywords: convex optimization, interior-point methods, primal-dual algorithms, self-concordant barriers

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Research Report CORR 2002-32, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, October 2002

Download: [Compressed Postscript]

Entry Submitted: 10/22/2002
Entry Accepted: 10/22/2002
Entry Last Modified: 10/22/2002

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 Programming Society