---
title: Self-concordant function
slug: self-concordant-function
qid: 
snapshot: enwiki-001353057094
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1353057094
tags: [101634858, 22175909, 29176345]
---

# Self-concordant function

> [!note] Provenance
> Snapshot `enwiki-001353057094` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1353057094> · Licensed CC BY-SA 4.0

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.

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. 2. Differential inequality: for every point x in C, and any direction h in R n , let g h be the function f restricted to the direction h, that is: g h (t) = f(x+t*h). Then the one-dimensional function g h should satisfy the following differential inequality: |g_h(x)| \leq 2 g_h(x)^{3/2} . Equivalently: \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) and satisfies f(x) = 0 elsewhere. Any function f(x) = -\log(-g(x))-\log x where g(x) is defined and convex for all x > 0 and verifies | g(x) | \leq 3g(x)/x , is self concordant on its domain which is \{ x \mid x > 0, g(x) . Some examples are g(x) = -x^p for 0 g(x) = -\log x g(x) = x^p for -1 \leq p \leq 0 g(x) = (ax+b)^2 / x for any function g satisfying the conditions, the function g(x) + a x^2 + bx + c with a \geq 0 also satisfies the conditions. Some functions that are not self-concordant: f(x) = e^x f(x) = \frac{1}{x^p}, x >0, p >0 f(x) = |x^p|, p > 2 2. For every point x in interior(C), and any direction h in R n , let g h be the function f restricted to the direction h, that is: g h (t) = f(x+t*h). Then the one-dimensional function g h should satisfy the following differential inequality: |g_h'(x)| \leq M^{1/2}\cdot g_h(x)^{1/2} . Every constant is a self-concordant barrier for all R n , with parameter M=0. It is the only self-concordant barrier for the entire space, and the only self-concordant barrier with M \mathbb R_+ ( x > 0 ), f(x) = -\ln x is a self-concordant barrier with parameter M = 1 . This can be proved directly from the definition. Let G be a closed convex domain in R n , and g an M-SCB for G. Let x = Ay+b be an affine mapping from R k to R n with its image intersecting the interior of G. Let H be the inverse image of G under the mapping: H = {y in R k | Ay+b in G}. Let h be the composite function h(y) := g(Ay+b). Then, h is an M-SCB for H. For example, take n=1, G the positive half-line, and g(x) = -\ln x . For any k, let a be a k-element vector and b a scalar. Let H = {y in R k | a T y+b ≥ 0} = a k-dimensional half-space. By the substitution rule, h(y) = -\ln (a^T y+b) is a 1-SCB for H. A more common format is H = {x in R k | a T x ≤ b}, for which the SCB is h(y) = -\ln (b - a^T y) . The substitution rule can be extended from affine mappings to a certain class of "appropriate" mappings, and to quadratic mappings. For all i in 1,...,m, let G i be a closed convex domains in R ni , and let g i be an M i -SCB for G i . Let G be the cartesian product of all G i . Let g(x 1 ,...,x m ) := sum i g i (x i ). Then, g is a SCB for G, with parameter sum i M i . For example, take all G i to be the positive half-line, so that G is the positive orthant \mathbb R_+^m . Let g(x) = -\sum_{i=1}^m \ln x_i is an m-SCB for G. We can now apply the substitution rule. We get that, for the polytope defined by the linear inequalities a j T x ≤ b j for j in 1,...,m, if it satisfies Slater's condition, then f(x) = -\sum_{i=1}^m \ln (b_j-a_j^T x) is an m-SCB. The linear functions b_j-a_j^T x can be replaced by quadratic functions. Let G 1 ,...,G m be closed convex domains in R n . For each i in 1,...,m, let g i be an M i -SCB for G i , and r i a real number. Let G be the intersection of all G i , and suppose its interior is nonempty. Let g := sum i r i *g i . Then, g is a SCB for G, with parameter sum i r i *M i . Therefore, if G is defined by a list of constraints, we can find a SCB for each constraint separately, and then simply sum them to get a SCB for G. For example, suppose the domain is defined by m linear constraints of the form a j T x ≤ b j , for j in 1,...,m. Then we can use the Intersection rule to construct the m-SCB f(x) = -\sum_{i=1}^m \ln (b_j-a_j^T x) (the same one that we previously computed using the Cartesian product rule). Let g(t) be a 3-times continuously differentiable concave function on t>0, such that t\cdot | g(t)| / |g(t)| is bounded by a constant (denoted 3*b) for all t>0. Let G be the 2-dimensional convex domain: G=\text{closure}(\{ (x,t) \in \mathbb{R}^2: t>0, x \leq g(t) \}). Then, the function f(x,t) = -ln(f(t)-x) - max[1,b 2 ]*ln(t) is a self-concordant barrier for G, with parameter (1+max[1,b 2 ]). Examples: Let g(t) = t 1/p , for some p≥1, and b=(2p-1)/(3p). Then G_1=\{ (x,t) \in \mathbb{R}^2: (x_+)^p \leq t \} has a 2-SCB. Similarly, G_2=\{ (x,t) \in \mathbb{R}^2: ([-x]_+)^p \leq t \} has a 2-SCB. Using the Intersection rule, we get that G = G_1\cap G_2= \{ (x,t) \in \mathbb{R}^2: |x|^p \leq t \} has a 4-SCB. Let g(t)=ln(t) and b=2/3. Then G=\{ (x,t) \in \mathbb{R}^2: e^x \leq t \} has a 2-SCB. We can now construct a SCB for the problem of minimizing the p-norm: \min_x \sum_{j=1}^n |v_j - x^T u_j|^p , where v j are constant scalars, u j are constant vectors, and p>0 is a constant. We first convert it into minimization of a linear objective: \min_x \sum_{j=1}^n t_j , with the constraints: t_j \geq |v_j - x^T u_j|^p for all j in [m]. For each constraint, we have a 4-SCB by the affine substitution rule. Using the Intersection rule, we get a (4n)-SCB for the entire feasible domain. Similarly, let g be a 3-times continuously differentiable convex function on the ray x>0, such that: x\cdot |g(x)| / |g(x)| \leq 3 b for all x>0. Let G be the 2-dimensional convex domain: closure({ (t,x) in R 2 : x>0, t ≥ g(x) }). Then, the function f(x,t) = -ln(t-f(x)) - max[1,b 2 ]*ln(x) is a self-concordant barrier for G, with parameter (1+max[1,b 2 ]). Examples: Let g(x) = x −p , for some p>0, and b=(2+p)/3. Then G_1=\{ (x,t) \in \mathbb{R}^2: x^{-p} \leq t, x\geq 0 \} has a 2-SCB. Let g(x)=x ln(x) and b=1/3. Then G=\{ (x,t) \in \mathbb{R}^2: x\ln x \leq t, x\geq 0 \} has a 2-SCB. For the second order cone \{ (x,y) \in \mathbb R^{n-1} \times \mathbb R \mid \| x \| \leq y \} , the function f(x,y) = -\log(y^2 - x^T x) is a self-concordant barrier. For the cone of positive semidefinite of m*m symmetric matrices, the function f(A) = - \log \det A is a self-concordant barrier. For the quadratic region defined by \phi(x) > 0 where \phi(x) = \alpha +\langle a, x \rangle - \frac{1}{2} \langle Ax, x \rangle where A = A^T \geq 0 is a positive semi-definite symmetric matrix, the logarithmic barrier f(x) = -\log \phi(x) is self-concordant with M = 2 For the exponential cone \{ (x,y,z) \in \mathbb R^3 \mid ye^{x/y} \leq z, y > 0 \} , the function f(x,y,z) = -\log (y \log(z/y) - x) - \log z - \log y is a self-concordant barrier. For the power cone \{ (x_1,x_2,y) \in \mathbb R_+^2 \times \mathbb R \mid |y| \leq x_1^{\alpha} x_2^{1-\alpha} \} , the function f(x_1,x_2,y) = -\log(x_1^{2\alpha} x_2^{2(1-\alpha)} - y^2) - \log x_1 - \log x_2 is a self-concordant barrier. As mentioned in the "Bibliography Comments" of their 1994 book, self-concordant functions were introduced in 1988 by Yurii Nesterov and further developed with Arkadi Nemirovski. As explained in their basic observation was that the Newton method is affine invariant, in the sense that if for a function f(x) we have Newton steps x_{k+1} = x_k - [f(x_k)]^{-1}f'(x_k) then for a function \phi(y) = f(Ay) where A is a non-degenerate linear transformation, starting from y_0 = A^{-1} x_0 we have the Newton steps y_k = A^{-1} x_k which can be shown recursively y_{k+1} = y_k - [\phi(y_k)]^{-1} \phi'(y_k) = y_k - [A^T f(A y_k) A]^{-1} A^T f'(A y_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 f is Lipschitz continuous, that is \|f(x) - f(y)\| \leq M\| x-y \| for some constant M . If we suppose that f is 3 times continuously differentiable, then this is equivalent to | \langle f(x)[u]v, v \rangle | \leq M \|u\| \|v\|^2 for all u,v \in \mathbb{R}^n where 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 f(x) \to \phi(y) = f(A y), 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 f defined as \| w \|_{f(x)} = \langle f(x)w, w \rangle^{1/2} for w \in \mathbb R^n . They then arrive at the definition of a self concordant function as | \langle f(x)[u]u, u \rangle | \leq M \langle f(x) u, u \rangle^{3/2} . If f is self-concordant with constant M and Ax + b is an affine transformation of \mathbb R^n , then \phi(x) = f(Ax+b) is also self-concordant with parameter M . Conversely, if for some x in the domain of f and u \in \mathbb R^n, u \neq 0 we have \langle f(x) u, u \rangle = 0 , then \langle f(x + \alpha u) u, u \rangle = 0 for all \alpha for which x + \alpha u is in the domain of f and then f(x + \alpha u) is linear and cannot have a maximum so all of x + \alpha u, \alpha \in \mathbb R is in the domain of f . We note also that f cannot have a minimum inside its domain. 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 f is a standard self-concordant function, that is it is self-concordant with parameter M = 2 . We define the Newton decrement \lambda_f(x) of f at x as the size of the Newton step [f(x)]^{-1} f'(x) in the local norm defined by the Hessian of f at x \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 x in the domain of f , if \lambda_f(x) then it is possible to prove that the Newton iterate x_+ = x - [f(x)]^{-1}f'(x) will be also in the domain of f . This is because, based on the self-concordance of f , it is possible to give some finite bounds on the value of f(x_+) . We further have \lambda_f(x_+) \leq \Bigg( \frac{\lambda_f(x)}{1-\lambda_f(x)} \Bigg)^2 Then if we have \lambda_f(x) then it is also guaranteed that \lambda_f(x_+) , so that we can continue to use the Newton method until convergence. Note that for \lambda_f(x_+) for some \beta \in (0, \bar\lambda) we have quadratic convergence of \lambda_f to 0 as \lambda_f(x_+) \leq (1-\beta)^{-2} \lambda_f(x)^2 . This then gives quadratic convergence of f(x_k) to f(x^*) and of x to x^* , where x^* = \arg\min f(x) , by the following theorem. If \lambda_f(x) then \omega(\lambda_f(x)) \leq f(x)-f(x^*) \leq \omega_*(\lambda_f(x)) \omega'(\lambda_f(x)) \leq \| x-x^* \|_x \leq \omega_*'(\lambda_f(x)) with the following definitions \omega(t) = t - \log(1+t) \omega_*(t) = -t-\log(1-t) \| u \|_x = \langle f(x) u, u \rangle^{1/2} If we start the Newton method from some x_0 with \lambda_f(x_0) \geq \bar\lambda then we have to start by using a damped Newton method defined by 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 f(x_{k+1}) \leq f(x_k) - \omega(\lambda_f(x_k)) with \omega as defined previously. Note that \omega(t) is an increasing function for t > 0 so that \omega(t) \geq \omega(\bar\lambda) for any t \geq \bar\lambda , so the value of f is guaranteed to decrease by a certain amount in each iteration, which also proves that x_{k+1} is in the domain of f .
