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

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

0.00 Avg rating0 Votes
Article ID: iaor20051140
Country: Germany
Volume: 99
Issue: 1
Start Page Number: 149
End Page Number: 174
Publication Date: Jan 2004
Journal: Mathematical Programming
Authors: ,
Keywords: barrier function
Abstract:

In this paper we study special barrier functions for convex cones, which are the sum of a self-concordant barrier for the cone and a positive-semidefinite quadratic form. We show that the central path of these augmented barrier functions can be traced with linear speed. We also study the complexity of finding the analytic center of the augmented barrier, a problem that has some interesting applications. We show that for some special classes of quadratic forms and some convex cones, the computation of the analytic center requires an amount of operations independent of the particular data set. We argue that these problems form a class that is endowed with a property which we call finite polynomial complexity.

Reviews

Required fields are marked *. Your email address will not be published.