Self-Concordant Barriers for Convex Approximations of Structured Convex Sets
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.
Entry Submitted: 02/27/2007
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|