A self-concordant function is a function satisfying a certain differential inequality, which makes it particularly easy for optimization using Newton's method A self-concordant barrier is a particular self-concordant function, that is also a barrier function for a particular convex set. Self-concordant barriers are important ingredients in interior point methods for optimization.
Self-concordant functions
Multivariate self-concordant function Here is the general definition of a self-concordant function. Let C be a convex nonempty open set in Rn. Let f be a function that is three-times continuously differentiable defined on C. We say that f is self-concordant on C if it satisfies the following properties: 1. Barrier property: on any sequence of points in C that converges to a boundary point of C, f converges to ∞.
2. Differential inequality: for every point x in C, and any direction h in Rn, let gh be the function f restricted to the direction h, that is: gh(t) = f(x+t*h). Then the one-dimensional function gh should satisfy the following differential inequality: | g h ‴ ( x ) | ≤ 2 g h ″ ( x ) 3 / 2 {\displaystyle |g_{h}'''(x)|\leq 2g_{h}''(x)^{3/2}} . Equivalently: d d α ∇ 2 f ( x + α y ) | α = 0 ⪯ 2 y T ∇ 2 f ( x ) y ∇ 2 f ( x ) {\displaystyle \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)}
Univariate self-concordant function A function f : R → R {\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} } is self-concordant on R {\displaystyle \mathbb {R} } if:
| f ‴ ( x ) | ≤ 2 f ″ ( x ) 3 / 2 {\displaystyle |f'''(x)|\leq 2f''(x)^{3/2}}
Equivalently: if wherever f ″ ( x ) > 0 {\displaystyle f''(x)>0} it satisfies:
| d d x 1 f ″ ( x ) | ≤ 1 {\displaystyle \left|{\frac {d}{dx}}{\frac {1}{\sqrt {f''(x)}}}\right|\leq 1}
and satisfies f ‴ ( x ) = 0 {\displaystyle f'''(x)=0} elsewhere.
Examples Linear and convex quadratic functions are self-concordant, since their third derivative is zero. Any function f ( x ) = − log ( − g ( x ) ) − log x {\displaystyle f(x)=-\log(-g(x))-\log x} where g ( x ) {\displaystyle g(x)} is defined and convex for all x > 0 {\displaystyle x>0} and verifies | g ‴ ( x ) | ≤ 3 g ″ ( x ) / x {\displaystyle |g'''(x)|\leq 3g''(x)/x} , is self concordant on its domain which is { x ∣ x > 0 , g ( x ) < 0 } {\displaystyle \{x\mid x>0,g(x)<0\}} . Some examples are
g ( x ) = − x p {\displaystyle g(x)=-x^{p}} for 0 < p ≤ 1 {\displaystyle 0<p\leq 1}
g ( x ) = − log x {\displaystyle g(x)=-\log x}
g ( x ) = x p {\displaystyle g(x)=x^{p}} for − 1 ≤ p ≤ 0 {\displaystyle -1\leq p\leq 0}
… excerpt ends here. Continue reading the full article.
