Efficient First-Order Methods for Linear Programming and Semidefinite Programming

Abstract

The study of first-order methods has largely dominated research in continuous optimization for the last decade, yet still the range of problems for which "optimal" first-order methods have been developed is surprisingly limited, even though much has been achieved in some areas with high profile, such as compressed sensing. Even if one restricts attention to, say, linear programming, the problems proven to be solvable by first-order methods in O(1/ǫ) iterations all possess noticeably strong structure.