Augmented self-concordant barriers and nonlinear optimization problems with finite complexity (Q1424292)

Augmented self-concordant barrier functions for convex cones, which are the sum of self-concordant barrier for the cone and a positive-semidifinite quadratic form, are studied. The complexity of finding the analytic center of these barrier functions is studied. It is shown that the complexity of a path-following method of barrier functions is independent of the particular data set for some special classes of quadratic forms and some convex cones. These problems form a class with finite polynomial complexity.