Self-concordant function

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In optimization, a self-concordant function is a function for which

or, equivalently, a function that, wherever , satisfies

and which satisfies elsewhere.

More generally, a multivariate function is self-concordant if

or, equivalently, if its restriction to any arbitrary line is self-concordant. [1]

History[edit]

The self-concordant functions are introduced by Yurii Nesterov and Arkadi Nemirovski in their 1994 book.[2]

Properties[edit]

Self concordance is preserved under addition, affine transformations, and scalar multiplication by a value greater than one.

Applications[edit]

Among other things, self-concordant functions are useful in the analysis of Newton's method. Self-concordant barrier functions are used to develop the barrier functions used in interior point methods for convex and nonlinear optimization.

References[edit]

  1. ^ Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved October 15, 2011. 
  2. ^ Nesterov, Yurii; Arkadii, Nemirovskii (1995). Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics. ISBN 0898715156.