Self-concordant function

In optimization, a self-concordant function is a function $f:\mathbb {R} \rightarrow \mathbb {R}$ for which

$|f'''(x)|\leq 2f''(x)^{3/2}$

or, equivalently, a function $f:\mathbb {R} \rightarrow \mathbb {R}$ that, wherever $f''(x)>0$, satisfies

$\left|{\frac {d}{dx}}{\frac {1}{\sqrt {f''(x)}}}\right|\leq 1$

and which satisfies $f'''(x)=0$ elsewhere.

More generally, a multivariate function $f(x):\mathbb {R} ^{n}\rightarrow \mathbb {R}$ is self-concordant if

$\left.{\frac {d}{d\alpha }}\nabla ^{2}f(x+\alpha y)\right|_{\alpha =0}\preceq 2{\sqrt {y^{T}\nabla ^{2}f(x)\,y}}\,\nabla ^{2}f(x)$

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

History

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

Properties

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

Applications

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.