The purpose of this paper is to provide improved complexity results for several classes of structured convex optimization problems using to the theory of self-concordant functions developed in [2]. 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 from [1] is improved, which allows us to review several classes of structured convex optimization problems and improve the corresponding complexity results. [1] D. den Hertog, F. Jarre, C. Roos, and T. Terlaky, A sufficient condition for self-concordance with application to some classes of structured convex programming problems, Mathematical Programming, Series B 69 (1995), no. 1, 75–88. [2] Y. E. Nesterov and A. S. Nemirovsky, Interior-point polynomial methods in convex programming, SIAM Studies in Applied Mathematics, SIAM Publications, Philadelphia, 1994.
Citation
IMAGE0102, Service MATHRO, Facultâ–’ Polytechnique de Mons, Mons, Belgium, Aug/01, to appear in EJOR