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.
Citation
Research Report 2007--03, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, February 2007.