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

Arkadi Nemirovski (nemirovsie.technion.ac.il)
Levent Tuncel (ltuncelmath.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