Self-concordant function

This article needs additional citations for verification. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  –  ·  ·  · scholar · JSTOR (June 2012) (Learn how and when to remove this template message)

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

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

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

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

and which satisfies ${\displaystyle f'''(x)=0}$ elsewhere.

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

${\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)}$

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

History[]

As mentioned in the "Bibliography Comments"^[2] of their 1994 book,^[3] self-concordant functions were introduced in 1988 by Yurii Nesterov^[4][5] and further developed with Arkadi Nemirovski.^[6] As explained in^[7] their basic observation was that the Newton method is affine invariant, in the sense that if for a function ${\displaystyle f(x)}$ we have Newton steps ${\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k})}$ then for a function ${\displaystyle \phi (y)=f(Ay)}$ where ${\displaystyle A}$ is a non-degenerate linear transformation, starting from ${\displaystyle y_{0}=A^{-1}x_{0}}$ we have the Newton steps ${\displaystyle y_{k}=A^{-1}x_{k}}$ which can be shown recursively

${\displaystyle y_{k+1}=y_{k}-[\phi ''(y_{k})]^{-1}\phi '(y_{k})=y_{k}-[A^{T}f''(Ay_{k})A]^{-1}A^{T}f'(Ay_{k})=A^{-1}x_{k}-A^{-1}[f''(x_{k})]^{-1}f'(x_{k})=A^{-1}x_{k+1}}$.

However the standard analysis of the Newton method supposes that the Hessian of ${\displaystyle f}$ is Lipschitz continuous, that is ${\displaystyle \|f''(x)-f''(y)\|\leq M\|x-y\|}$ for some constant ${\displaystyle M}$. If we suppose that ${\displaystyle f}$ is 3 times continuously differentiable, then this is equivalent to

${\displaystyle |\langle f'''(x)[u]v,v\rangle |\leq M\|u\|\|v\|^{2}}$for all ${\displaystyle u,v\in \mathbb {R} ^{n}}$

where ${\displaystyle f'''(x)[u]=\lim _{\alpha \to 0}\alpha ^{-1}[f''(x+\alpha u)-f''(x)]}$ . Then the left hand side of the above inequality is invariant under the affine transformation ${\displaystyle f(x)\to \phi (y)=f(Ay),u\to A^{-1}u,v\to A^{-1}v}$, however the right hand side is not.

The authors note that the right hand side can be made also invariant if we replace the Euclidean metric by the scalar product defined by the Hessian of ${\displaystyle f}$ defined as ${\displaystyle \|w\|_{f''(x)}=\langle f''(x)w,w\rangle ^{1/2}}$ for ${\displaystyle w\in \mathbb {R} ^{n}}$. They then arrive at the definition of a self concordant function as

${\displaystyle |\langle f'''(x)[u]u,u\rangle |\leq M\langle f''(x)u,u\rangle ^{3/2}}$.

Properties[]

Linear combination[]

If ${\displaystyle f_{1}}$ and ${\displaystyle f_{2}}$ are self-concordant with constants ${\displaystyle M_{1}}$ and ${\displaystyle M_{2}}$ and ${\displaystyle \alpha ,\beta >0}$, then ${\displaystyle \alpha f_{1}+\beta f_{2}}$ is self-concordant with constant ${\displaystyle \max(\alpha ^{-1/2}M_{1},\beta ^{-1/2}M_{2})}$.

Affine transformation[]

If ${\displaystyle f}$ is self-concordant with constant ${\displaystyle M}$ and ${\displaystyle Ax+b}$ is an affine transformation of ${\displaystyle \mathbb {R} ^{n}}$, then ${\displaystyle \phi (x)=f(Ax+b)}$ is also self-concordant with parameter ${\displaystyle M}$.

Convex conjugate[]

If ${\displaystyle f}$ is self-concordant, then its convex conjugate ${\displaystyle f^{*}}$ is also self-concordant.^[8][9]

Non-singular Hessian[]

If ${\displaystyle f}$ is self-concordant and the domain of ${\displaystyle f}$ contains no straight line (infinite in both directions), then ${\displaystyle f''}$ is non-singular.

Conversely, if for some ${\displaystyle x}$ in the domain of ${\displaystyle f}$ and ${\displaystyle u\in \mathbb {R} ^{n},u\neq 0}$ we have ${\displaystyle \langle f''(x)u,u\rangle =0}$, then ${\displaystyle \langle f''(x+\alpha u)u,u\rangle =0}$ for all ${\displaystyle \alpha }$ for which ${\displaystyle x+\alpha u}$ is in the domain of ${\displaystyle f}$ and then ${\displaystyle f(x+\alpha u)}$ is linear and cannot have a maximum so all of ${\displaystyle x+\alpha u,\alpha \in \mathbb {R} }$ is in the domain of ${\displaystyle f}$. We note also that ${\displaystyle f}$ cannot have a minimum inside its domain.

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. The usual analysis of the Newton method would not work for barrier functions as their second derivative cannot be Lipschitz continuous, otherwise they would be bounded on any compact subset of ${\displaystyle \mathbb {R} ^{n}}$.

Self-concordant barrier functions

• are a class of functions that can be used as barriers in constrained optimization methods
• can be minimized using the Newton algorithm with provable convergence properties analogous to the usual case (but these results are somewhat more difficult to derive)
• to have both of the above, the usual constant bound on the third derivative of the function (required to get the usual convergence results for the Newton method) is replaced by a bound relative to the Hessian

Minimizing a self-concordant function[]

A self-concordant function may be minimized with a modified Newton method where we have a bound on the number of steps required for convergence. We suppose here that ${\displaystyle f}$ is a standard self-concordant function, that is it is self-concordant with parameter ${\displaystyle M=2}$.

We define the Newton decrement ${\displaystyle \lambda _{f}(x)}$ of ${\displaystyle f}$ at ${\displaystyle x}$ as the size of the Newton step ${\displaystyle [f''(x)]^{-1}f'(x)}$ in the local norm defined by the Hessian of ${\displaystyle f}$ at ${\displaystyle x}$

${\displaystyle \lambda _{f}(x)=\langle f''(x)[f''(x)]^{-1}f'(x),[f''(x)]^{-1}f'(x)\rangle ^{1/2}=\langle [f''(x)]^{-1}f'(x),f'(x)\rangle ^{1/2}}$

Then for ${\displaystyle x}$ in the domain of ${\displaystyle f}$, if ${\displaystyle \lambda _{f}(x)<1}$ then it is possible to prove that the Newton iterate

${\displaystyle x_{+}=x-[f''(x)]^{-1}f'(x)}$

will be also in the domain of ${\displaystyle f}$. This is because, based on the self-concordance of ${\displaystyle f}$, it is possible to give some finite bounds on the value of ${\displaystyle f(x_{+})}$. We further have

${\displaystyle \lambda _{f}(x_{+})\leq {\Bigg (}{\frac {\lambda _{f}(x)}{1-\lambda _{f}(x)}}{\Bigg )}^{2}}$

Then if we have

${\displaystyle \lambda _{f}(x)<{\bar {\lambda }}={\frac {3-{\sqrt {5}}}{2}}}$

then it is also guaranteed that ${\displaystyle \lambda _{f}(x_{+})<\lambda _{f}(x)}$, so that we can continue to use the Newton method until convergence. Note that for ${\displaystyle \lambda _{f}(x_{+})<\beta }$ for some ${\displaystyle \beta \in (0,{\bar {\lambda }})}$ we have quadratic convergence of ${\displaystyle \lambda _{f}}$ to 0 as ${\displaystyle \lambda _{f}(x_{+})\leq (1-\beta )^{-2}\lambda _{f}(x)^{2}}$. This then gives quadratic convergence of ${\displaystyle f(x_{k})}$ to ${\displaystyle f(x^{*})}$ and of ${\displaystyle x}$ to ${\displaystyle x^{*}}$, where ${\displaystyle x^{*}=\arg \min f(x)}$, by the following theorem. If ${\displaystyle \lambda _{f}(x)<1}$ then

${\displaystyle \omega (\lambda _{f}(x))\leq f(x)-f(x^{*})\leq \omega _{*}(\lambda _{f}(x))}$

${\displaystyle \omega '(\lambda _{f}(x))\leq \|x-x^{*}\|_{x}\leq \omega _{*}'(\lambda _{f}(x))}$

with the following definitions

${\displaystyle \omega (t)=t-\log(1+t)}$

${\displaystyle \omega _{*}(t)=-t-\log(1-t)}$

${\displaystyle \|u\|_{x}=\langle f''(x)u,u\rangle ^{1/2}}$

If we start the Newton method from some ${\displaystyle x_{0}}$ with ${\displaystyle \lambda _{f}(x_{0})\geq {\bar {\lambda }}}$ then we have to start by using a damped Newton method defined by

${\displaystyle x_{k+1}=x_{k}-{\frac {1}{1+\lambda _{f}(x_{k})}}[f''(x_{k})]^{-1}f'(x_{k})}$

For this it can be shown that ${\displaystyle f(x_{k+1})\leq f(x_{k})-\omega (\lambda _{f}(x_{k}))}$ with ${\displaystyle \omega }$ as defined previously. Note that ${\displaystyle \omega (t)}$ is an increasing function for ${\displaystyle t>0}$ so that ${\displaystyle \omega (t)\geq \omega ({\bar {\lambda }})}$ for any ${\displaystyle t\geq {\bar {\lambda }}}$, so the value of ${\displaystyle f}$ is guaranteed to decrease by a certain amount in each iteration, which also proves that ${\displaystyle x_{k+1}}$ is in the domain of ${\displaystyle f}$.

Examples[]

Self-concordant functions[]

• Linear and convex quadratic functions are self-concordant with ${\displaystyle M=0}$ since their third derivative is zero.
• Any function ${\displaystyle f(x)=-\log(-g(x))-\log x}$ where ${\displaystyle g(x)}$ is defined and convex for all ${\displaystyle x>0}$ and verifies ${\displaystyle |g'''(x)|\leq 3g''(x)/x}$, is self concordant on its domain which is ${\displaystyle \{x\mid x>0,g(x)<0\}}$. Some examples are
  • ${\displaystyle g(x)=-x^{p}}$ for ${\displaystyle 0<p\leq 1}$
  • ${\displaystyle g(x)=-\log x}$
  • ${\displaystyle g(x)=x^{p}}$ for ${\displaystyle -1\leq p\leq 0}$
  • ${\displaystyle g(x)=(ax+b)^{2}/x}$
  • for any function ${\displaystyle g}$ satisfying the conditions, the function ${\displaystyle g(x)+ax^{2}+bx+c}$ with ${\displaystyle a\geq 0}$ also satisfies the conditions

Functions that are not self-concordant

• ${\displaystyle f(x)=e^{x}}$
• ${\displaystyle f(x)={\frac {1}{x^{p}}},x>0,p>0}$
• ${\displaystyle f(x)=|x^{p}|,p>2}$

Self-concordant barriers[]

• positive half-line ${\displaystyle \mathbb {R} _{+}}$: ${\displaystyle f(x)=-\log x}$ with domain ${\displaystyle x>0}$ is a self-concordant barrier with ${\displaystyle M=1}$.
• positive orthant ${\displaystyle \mathbb {R} _{+}^{n}}$: ${\displaystyle f(x)=-\sum _{i=1}^{n}\log x_{i}}$ with ${\displaystyle M=n}$
• the logarithmic barrier ${\displaystyle f(x)=-\log \phi (x)}$ for the quadratic region defined by ${\displaystyle \phi (x)>0}$ where ${\displaystyle \phi (x)=\alpha +\langle a,x\rangle -{\frac {1}{2}}\langle Ax,x\rangle }$ where ${\displaystyle A=A^{T}\geq 0}$ is a positive semi-definite symmetric matrix is self-concordant for ${\displaystyle M=2}$
• second order cone ${\displaystyle \{(x,y)\in \mathbb {R} ^{n-1}\times \mathbb {R} \mid \|x\|\leq y\}}$: ${\displaystyle f(x,y)=-\log(y^{2}-x^{T}x)}$
• semi-definite cone ${\displaystyle A=A^{T}\geq 0}$: ${\displaystyle f(A)=-\log \det A}$
• exponential cone ${\displaystyle \{(x,y,z)\in \mathbb {R} ^{3}\mid ye^{x/y}\leq z,y>0\}}$: ${\displaystyle f(x,y,z)=-\log(y\log(z/y)-x)-\log z-\log y}$
• power cone ${\displaystyle \{(x_{1},x_{2},y)\in \mathbb {R} _{+}^{2}\times \mathbb {R} \mid |y|\leq x_{1}^{\alpha }x_{2}^{1-\alpha }\}}$: ${\displaystyle f(x_{1},x_{2},y)=-\log(x_{1}^{2\alpha }x_{2}^{2(1-\alpha )}-y^{2})-\log x_{1}-\log x_{2}}$

References[]