SELF-CONCORDANT FUNCTIONS IN STRUCTURED CONVEX OPTIMIZATION

This paper provides a self-contained introduction to the theory of
self-concordant functions [2] and applies it to several classes of structured
convex optimization problems. We describe the classical short-step
interior-point method and optimize its parameters to provide its best possible
iteration bound. We also discuss the necessity of introducing two parameters
in the definition of self-concordancy, how they react to addition and scaling
and which one is the best to fix. A lemma from [1] is improved and allows us
to review several classes of structured convex optimization problems and
evaluate their algorithmic complexity, using the self-concordancy of the
associated logarithmic barriers.

[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.