Wikipedia / Self-concordant function
Wikipedia / Self-concordant function
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: . Equivalently:
Univariate self-concordant function
A function if:
it satisfies:
elsewhere.
Examples
Linear and convex quadratic functions are self-concordant, since their third derivative is zero.
. Some examples are
also satisfies the conditions.
Some functions that are not self-concordant:
Self-concordant barriersbarrier
Here is the general definition of a self-concordant barrier (SCB).
Let C be a convex closed set in Rn with a non-empty interior. Let f be a function from interior(C) to R. Let M>0 be a real parameter. We say that f is a M-self-concordant barrier for C if it satisfies the following:
1. f is a self-concordant function on interior(C).
2. For every point x in interior(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:.
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 Rn 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.
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 Rn, with parameter M=0. It is the only self-concordant barrier for the entire space, and the only self-concordant barrier with M < 1. [Note that linear and quadratic functions are self-concordant functions, but they are not self concordant barriers].
. This can be proved directly from the definition.
Substitution rule
Let G be a closed convex domain in Rn, and g an M-SCB for G. Let x = Ay+b be an affine mapping from Rk to Rn with its image intersecting the interior of G. Let H be the inverse image of G under the mapping: H = {y in Rk | 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. For any k, let a be a k-element vector and b a scalar. Let H = {y in Rk | aTy+b ≥ 0} = a k is a 1-SCB for H. A more common format is H = {x in Rk | aTx.
The substitution rule can be extended from affine mappings to a certain class of "appropriate" mappings, and to quadratic mappings.
Cartesian product rule
For all i in 1,...,m, let Gi be a closed convex domains in Rni, and let gi be an Mi-SCB for Gi. Let G be the cartesian product of all Gi. Let g(x1,...,xm) := sumi gi(xi). Then, g is a SCB for G, with parameter sumi Mi.
For example, take all Gi to be the positive half-line, so that G is an m-SCB for G.
We can now apply the substitution rule. We get that, for the polytope defined by the linear inequalities ajTx ≤ bj for j in 1,...,m, if it satisfies Slater's condition is an m can be replaced by quadratic functions.
Intersection rule
Let G1,...,Gm be closed convex domains in Rn. For each i in 1,...,m, let gi be an Mi-SCB for Gi, and ri a real number. Let G be the intersection of all Gi, and suppose its interior is nonempty. Let g := sumi ri*gi. Then, g is a SCB for G, with parameter sumi ri*Mi.
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 ajTx ≤ bj, for j in 1,...,m. Then we can use the Intersection rule to construct the m (the same one that we previously computed using the Cartesian product rule).
SCBs for epigraphs
The epigraph of a function 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 is bounded by a constant (denoted 3*b) for all t>0. Let GThen, the function f(x,t) = -ln(f(t)-x) - max[1,b2]*ln(t) is a self-concordant barrier for G, with parameter (1+max[1,b2]).
Examples:
Let g(t) = t1/p, for some p≥1, and b=(2p-1)/(3p has a 4-SCB.
Let g(t)=ln(t) and b has a 2-SCB.
We can now construct a SCB for the problem of minimizing the p, where vj are constant scalars, uj are constant vectors, and pfor 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 for all x>0. Let G be the 2-dimensional convex domain: closure({ (t,x) in R2: x>0, t ≥ g(x) }). Then, the function f(x,t) = -ln(t-f(x)) - max[1,b2]*ln(x) is a self-concordant barrier for G, with parameter (1+max[1,b2]).
Examples:
Let g(x) = x−p, for some p>0, and b=(2+p has a 2-SCB.
Let g(x)=x ln(x) and b has a 2-SCB.
SCBs for cones
For the second order cone is a self-concordant barrier.
For the cone of positive semidefinite is a self-concordant barrier.
For the exponential cone is a self-concordant barrier.
For the power cone is a self-concordant barrier.
History
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 which can be shown recursively
.
is Lipschitz continuous is 3 times continuously differentiable, then this is equivalent to
. Then the left hand side of the above inequality is invariant under the affine transformation, however the right hand side is not.
. They then arrive at the definition of a self concordant function as
.
Properties
Linear combination
.
Affine transformation
.
Convex conjugate
is self-concordant, then its convex conjugate is also self-concordant.
Non-singular Hessian
is non-singular.
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.
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
is a standard.
We define the Newton decrement
then it is possible to prove that the Newton iterate
. We further have
Then if we have
then
with the following definitions
then we have to start by using a damped Newton method defined by
.