A self‑concordant function is a twice‑differentiable convex function whose third‑order behavior is controlled relative to its second‑order curvature. Formally, a function $f: \mathcal{D}\rightarrow\mathbb{R}$ defined on an open convex domain $\mathcal{D}\subseteq\mathbb{R}^n$ is called self‑concordant if it is three times continuously differentiable on $\mathcal{D}$ and for every point $x\in\mathcal{D}$ and direction $h\in\mathbb{R}^n$,
$$ |D^3 f(x)[h,h,h]|;\le;2\bigl(D^2 f(x)[h,h]\bigr)^{3/2}, $$
where $D^2 f(x)[h,h]$ and $D^3 f(x)[h,h,h]$ denote the quadratic and cubic forms of the Hessian and third derivative tensors, respectively. The inequality bounds the magnitude of the third derivative by a function of the Hessian, ensuring that the curvature of $f$ does not change too rapidly.
Key properties
| Property | Description |
|---|---|
| Affine invariance | If $f$ is self‑concordant, then for any affine transformation $x\mapsto Ax+b$ with nonsingular $A$, the transformed function $g(x)=f(Ax+b)$ is also self‑concordant. |
| Preservation under addition | The sum of two self‑concordant functions (with compatible domains) is self‑concordant. |
| Scaling | Multiplying a self‑concordant function by a positive scalar preserves self‑concordance, while division by a scalar may require adjusting the self‑concordance parameter. |
| Self‑concordance parameter | Often a function is said to be $M$-self‑concordant if the inequality above holds with constant $M$ (commonly $M=2$ is used). The standard definition uses $M=2$. |
| Local quadratic convergence of Newton’s method | For a self‑concordant function, Newton’s method exhibits a well‑characterized region of quadratic convergence, and a globally convergent damped Newton scheme can be designed with explicit iteration‑complexity bounds. |
Examples
- Logarithmic barrier: $f(x) = -\sum_{i=1}^m \log(b_i - a_i^{\top}x)$ for linear inequalities $a_i^{\top}x < b_i$. This barrier is a classic self‑concordant function used in interior‑point methods.
- Quadratic functions: Any positive‑definite quadratic form $f(x)=\tfrac12 x^{\top}Qx + c^{\top}x + d$ is self‑concordant with parameter $M=0$ because its third derivative vanishes.
- Negative log‑determinant: $f(X) = -\log\det X$ defined on the cone of symmetric positive‑definite matrices is self‑concordant and underlies semidefinite programming algorithms.
Applications
Self‑concordant functions play a central role in the theory and practice of interior‑point methods for convex optimization. Their controlled third‑order behavior yields explicit complexity bounds for Newton‑type algorithms, such as:
- Polynomial‑time convergence guarantees for linear, quadratic, and conic programming problems.
- Design of barrier functions in conic optimization (e.g., second‑order cone, semidefinite cone).
- Analysis of path‑following algorithms where the central path is defined via a self‑concordant barrier.
The concept was introduced by Yurii Nesterov and Arkadi Nemirovski in the early 1990s and is detailed in their seminal work Interior‑Point Polynomial Algorithms in Convex Programming (1994).
References
- Nesterov, Y., & Nemirovski, A. (1994). Interior‑Point Polynomial Algorithms in Convex Programming. SIAM.
- Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. (Chapter 9 discusses self‑concordant barriers.)
- Renegar, J. (2001). A Mathematical View of Interior‑Point Methods in Convex Optimization. SIAM.
These sources provide formal definitions, proofs of the properties listed above, and extensive discussion of algorithmic implications.
