Optimization Online


Self-Concordant Barriers for Convex Approximations of Structured Convex Sets

Levent Tuncel(ltuncel***at***math.uwaterloo.ca)
A. Nemirovski(nemirovs***at***isye.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

  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