Convex Optimization 2026, 39 - Self-Concordance

In practice, the required constants for complex applications of the Newton method are rarely known, so the bound on the step number is often unknown. Newton's method is also affinely invariant, so its analysis depends on the coordinate system. This can be changed by imposing self-concordance: f: ℝ → ℝ | |f'''(x)| ≤ 2f''(x)^3/2 ∀ x ∈ dom f (Eq. 9.41). Linear and convex quadratic functions have no third derivative, so then self-concordance is given automatically. The constant 2 in the definition is chosen for convenience of later expressions. On ℝⁿ, a function is self-concordant if it is so along every line in its domain (9.6.1). Self-concordance is preserved by positive scaling and addition with other self-concordant functions (p 499). For self-concordant f: ℝⁿ → ℝ, A ∈ ℝ^{n × m}, b ∈ ℝⁿ then f(Ax + b) is also self-concordant. For log functions, f(x) = -log(-g(x)) - log(x) is self-concordant, iff

(Eq. 9.43), which is homogenous and preserved under addition (9.6.2). Strictly convex self-concordant functions are bound in terms of the Newton decrement for the suboptimality of a point. These are not affected by affine changes of coordinates.

(Eq. 9.44). If f: ℝ → ℝ is strictly convex self-concordant, the second derivative in the self-concordance inequality leads to bounds for all nonnegative parameters in the domain of f. Given a descent direction v, then g(t) = f(x + tv) is a self-concordant function. The bounds can be approximated from those of f, more or less directly.

Given Newton's method with backtracking line search applied to a strictly convex self-concordant function can be analyzed analogously to the classical Newton analysis. The damped Newton phase has two additional parameters α, β:

The bound on the number of iterations comes out to about 375(f(x⁽⁰⁾) - p^*) + 6 (Eq. 9.57) (9.6.4)