Augmented self-concordant barriers and nonlinear optimization problems with finite complexity
by
Yurii Nesterov
CORE, UCL, Louvain-la-Neuve, Belgium
Coauthors: Jean-Philippe Vial, Geneva University, Switzerland

In this talk we discuss some special barrier functions for convex cones, which are formed as a sum of a self-concordant barrier and a positive-semidefinite quadratic form. We show that the central path of such barrier functions can be traced with linear speed. We study the complexity of finding the analytic center of the augmented barrier and some interesting applications. We show that in some special situations the computation of the analytic center requires an amount of operations independent on the particular data set.

Date received: April 2, 2001