Self-Concordant Barriers for Convex Approximations of Structured Convex Sets

Levent Tuncel(ltuncelmath.uwaterloo.ca)
A. Nemirovski(nemirovsisye.gatech.edu)

Abstract: We show how to approximate the feasible region of structured convex optimization problems by a family of convex sets with explicitly given and efficient (if the accuracy of the approximation is moderate) self-concordant barriers. This approach extends the reach of the modern theory of interior-point methods, and lays the foundation for new ways to treat structured convex optimization problems with a very large number of constraints. Moreover, our approach provides a strong connection from the theory of self-concordant barriers to the combinatorial optimization literature on solving packing and covering problems.

Keywords: convex optimization, self-concordant barriers, semidefinite programming, interior-point methods, packing-covering problems

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Research Report 2007--03, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, February 2007.

Download: [PDF]

Entry Submitted: 02/27/2007
Entry Accepted: 02/27/2007
Entry Last Modified: 02/27/2007

Modify/Update this entry