Improving Complexity of Structured Convex Optimization Problems Using Self-concordant Barriers

The purpose of this paper is to provide improved complexity results for several classes of structured convex optimization problems using the theory of self-concordant functions developed by Nesterov and Nemirovski in SIAM Studies in Applied Mathematics, SIAM Publications, Philadelphia, 1994. We describe the classical short-step interior-point method and optimize its parameters in order to provide the best possible iteration bound. We also discuss the necessity of introducing two parameters in the definition of self-concordancy and which one is the best to fix. A lemma due to den Hertog et al. in Mathematical Programming Series B 69 (1) (1995) is improved, which allows us to review several classes of structured convex optimization problems and improve the corresponding complexity results