Multivariate self-concordant function

Here is the general definition of a self-concordant function.^{[2]: Def.2.0.1}

Let C be a convex nonempty open set in Rⁿ. 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 Rⁿ, 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:

${\displaystyle |g_{h}'''(x)|\leq 2g_{h}''(x)^{3/2}}$.

Equivalently:^[3]

${\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 ${\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} }$ is self-concordant on ${\displaystyle \mathbb {R} }$ if:

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

Equivalently: if wherever ${\displaystyle f''(x)>0}$ it satisfies:

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

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

Examples

• Linear and convex quadratic functions are self-concordant, 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.

Some 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}$

Constructing SCBs

Due to the importance of SCBs in interior-point methods, it is important to know how to construct SCBs for various domains.

In theory, it can be proved that every closed convex domain in Rⁿ has a self-concordant barrier with parameter O(n). But this “universal barrier” is given by some multivariate integrals, and it is too complicated for actual computations. Hence, the main goal is to construct SCBs that are efficiently computable.^{[4]: Sec.9.2.3.3}

SCBs can be constructed from some basic SCBs, that are combined to produce SCBs for more complex domains, using several combination rules.

Basic SCBs

Every constant is a self-concordant barrier for all Rⁿ, with parameter M=0. It is the only self-concordant barrier for the entire space, and the only self-concordant barrier with M < 1.^{[2]: Example 3.1.1} [Note that linear and quadratic functions are self-concordant functions, but they are not self concordant barriers].

For the positive half-line ${\displaystyle \mathbb {R} _{+}}$(${\displaystyle x>0}$), ${\displaystyle f(x)=-\ln x}$ is a self-concordant barrier with parameter ${\displaystyle M=1}$. This can be proved directly from the definition.

Substitution rule

Let G be a closed convex domain in Rⁿ, and g an M-SCB for G. Let x = Ay+b be an affine mapping from R^k to Rⁿ 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.^{[2]: Prop.3.1.1}

For example, take n=1, G the positive half-line, and ${\displaystyle 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^Ty+b ≥ 0} = a k-dimensional half-space. By the substitution rule, ${\displaystyle h(y)=-\ln(a^{T}y+b)}$ is a 1-SCB for H. A more common format is H = {x in R^k | a^Tx ≤ b}, for which the SCB is ${\displaystyle h(y)=-\ln(b-a^{T}y)}$.

The substitution rule can be extended from affine mappings to a certain class of "appropriate" mappings,^{[2]: Thm.9.1.1} and to quadratic mappings.^{[2]: Sub.9.3}

Cartesian product rule

For all i in 1,...,m, let G_i be a closed convex domains in Rⁿⁱ, 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₁,...,x_m) := sum_i g_i(x_i). Then, g is a SCB for G, with parameter sum_i M_i.^{[2]: Prop.3.1.1}

For example, take all G_i to be the positive half-line, so that G is the positive orthant ${\displaystyle \mathbb {R} _{+}^{m}}$. Let ${\displaystyle 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^Tx ≤ b_j for j in 1,...,m, if it satisfies Slater's condition, then ${\displaystyle f(x)=-\sum _{i=1}^{m}\ln(b_{j}-a_{j}^{T}x)}$ is an m-SCB. The linear functions ${\displaystyle b_{j}-a_{j}^{T}x}$ can be replaced by quadratic functions.

Intersection rule

Let G₁,...,G_m be closed convex domains in Rⁿ. 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.^{[2]: Prop.3.1.1}

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^Tx ≤ b_j, for j in 1,...,m. Then we can use the Intersection rule to construct the m-SCB ${\displaystyle 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).

SCBs for epigraphs

The epigraph of a function f(x) is the area above the graph of the function, that is, ${\displaystyle \{(x,t)\in \mathbb {R} ^{2}:t\geq f(x)\}}$. The epigraph of f is a convex set if and only if f is a convex function. The following theorems present some functions f for which the epigraph has an SCB.

Let g(t) be a 3-times continuously differentiable concave function on t>0, such that ${\displaystyle 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: ${\displaystyle 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²]*ln(t) is a self-concordant barrier for G, with parameter (1+max[1,b²]).^{[2]: Prop.9.2.1}

Examples:

• Let g(t) = t^1/p, for some p≥1, and b=(2p-1)/(3p). Then ${\displaystyle G_{1}=\{(x,t)\in \mathbb {R} ^{2}:(x_{+})^{p}\leq t\}}$ has a 2-SCB. Similarly, ${\displaystyle G_{2}=\{(x,t)\in \mathbb {R} ^{2}:([-x]_{+})^{p}\leq t\}}$ has a 2-SCB. Using the Intersection rule, we get that ${\displaystyle 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 ${\displaystyle 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: ${\displaystyle \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: ${\displaystyle \min _{x}\sum _{j=1}^{n}t_{j}}$, with the constraints: ${\displaystyle 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: ${\displaystyle x\cdot |g'''(x)|/|g''(x)|\leq 3b}$ for all x>0. Let G be the 2-dimensional convex domain: closure({ (t,x) in R²: x>0, t ≥ g(x) }). Then, the function f(x,t) = -ln(t-f(x)) - max[1,b²]*ln(x) is a self-concordant barrier for G, with parameter (1+max[1,b²]).^{[2]: Prop.9.2.2}

Examples:

• Let g(x) = x^−p, for some p>0, and b=(2+p)/3. Then ${\displaystyle 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 ${\displaystyle G=\{(x,t)\in \mathbb {R} ^{2}:x\ln x\leq t,x\geq 0\}}$ has a 2-SCB.

SCBs for cones

• For the second order cone ${\displaystyle \{(x,y)\in \mathbb {R} ^{n-1}\times \mathbb {R} \mid \|x\|\leq y\}}$, the function ${\displaystyle 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 ${\displaystyle f(A)=-\log \det A}$ is a self-concordant barrier.
• 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, the logarithmic barrier ${\displaystyle f(x)=-\log \phi (x)}$ is self-concordant with ${\displaystyle M=2}$
• For the exponential cone ${\displaystyle \{(x,y,z)\in \mathbb {R} ^{3}\mid ye^{x/y}\leq z,y>0\}}$, the function ${\displaystyle f(x,y,z)=-\log(y\log(z/y)-x)-\log z-\log y}$ is a self-concordant barrier.
• For the 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 }\}}$, the function ${\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}}$ is a self-concordant barrier.

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.^[6][11]

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.

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}$.