Convex Optimization · Problem 9.17

Equality constrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · upper-lower-bounds-hessian-self-concordant

Problem

Upper and lower bounds on the Hessian of a self-concordant function. ((a)) Let f:R2→Rf : \mathbf{R}^2 \to \mathbf{R} be a self-concordant function. Show that ∣∂3f(x)∂3xi∣≤2(∂2f(x)∂xi2)3/2,i=1,2,\left| \frac{\partial^3 f(x)}{\partial^3 x_i} \right| \leq 2 \left( \frac{\partial^2 f(x)}{\partial x_i^2} \right)^{3/2}, \quad i = 1, 2, ∣∂3f(x)∂xi2∂xj∣≤2∂2f(x)∂xi2(∂2f(x)∂xj2)1/2,i≠j\left| \frac{\partial^3 f(x)}{\partial x_i^2 \partial x_j} \right| \leq 2 \frac{\partial^2 f(x)}{\partial x_i^2} \left( \frac{\partial^2 f(x)}{\partial x_j^2} \right)^{1/2}, \quad i \neq j for all x∈dom fx \in \mathbf{dom}\, f. Hint. If h:R2×R2×R2→Rh : \mathbf{R}^2 \times \mathbf{R}^2 \times \mathbf{R}^2 \to \mathbf{R} is a symmetric trilinear form, i.e., h(u,v,w)=a1u1v1w1+a2(u1v1w2+u1v2w1+u2v1w1)+a3(u1v2w2+u2v1w1+u2v2w1)+a4u2v2w2,\begin{aligned} h(u, v, w) &= a_1 u_1 v_1 w_1 + a_2(u_1 v_1 w_2 + u_1 v_2 w_1 + u_2 v_1 w_1) \\ &\quad + a_3(u_1 v_2 w_2 + u_2 v_1 w_1 + u_2 v_2 w_1) + a_4 u_2 v_2 w_2, \end{aligned} then sup⁡u,v,w≠0h(u,v,w)∥u∥2∥v∥2∥w∥2=sup⁡u≠0h(u,u,u)∥u∥23.\sup_{u,v,w \neq 0} \frac{h(u,v,w)}{\|u\|_2 \|v\|_2 \|w\|_2} = \sup_{u \neq 0} \frac{h(u,u,u)}{\|u\|_2^3}. ((b)) Let f:Rn→Rf : \mathbf{R}^n \to \mathbf{R} be a self-concordant function. Show that the nullspace of ∇2f(x)\nabla^2 f(x) is independent of xx. Show that if ff is strictly convex, then ∇2f(x)\nabla^2 f(x) is nonsingular for all x∈dom fx \in \mathbf{dom}\, f. Hint. Prove that if wT∇2f(x)w=0w^T \nabla^2 f(x) w = 0 for some x∈dom fx \in \mathbf{dom}\, f, then wT∇2f(y)w=0w^T \nabla^2 f(y) w = 0 for all y∈dom fy \in \mathbf{dom}\, f. To show this, apply the result in (a) to the self-concordant function f~(t,s)=f(x+t(y−x)+sw)\tilde{f}(t, s) = f(x + t(y - x) + sw). ((c)) Let f:Rn→Rf : \mathbf{R}^n \to \mathbf{R} be a self-concordant function. Suppose x∈dom fx \in \mathbf{dom}\, f, v∈Rnv \in \mathbf{R}^n. Show that (1−tα)2∇2f(x)⪯∇2f(x+tv)⪯1(1−tα)2∇2f(x)(1 - t\alpha)^2 \nabla^2 f(x) \preceq \nabla^2 f(x + tv) \preceq \frac{1}{(1 - t\alpha)^2} \nabla^2 f(x) for x+tv∈dom fx + tv \in \mathbf{dom}\, f, 0≤t<α0 \leq t < \alpha, where α=(vT∇2f(x)v)1/2\alpha = (v^T \nabla^2 f(x) v)^{1/2}.
Intuitive explanation

Self-concordance is a special convexity property that tightly controls how the Hessian (curvature) can change—the third derivatives are bounded by the Hessian's own magnitude. The key insight is that the self-concordance inequality, applied strategically to univariate or bivariate restrictions of ff, lets you extract bounds on individual third-derivative components by relating them to Hessian entries via the trilinear form hint. For part (b), the self-concordance constraint is so restrictive that any direction in the Hessian's nullspace at one point must remain in the nullspace everywhere. Part (c) shows how the Hessian evolves along a direction: the denominator (1−tα)−2(1 - t\alpha)^{-2} quantifies the "local norm" of that direction, controlling curvature change in a precise, quantifiable way.

Intuitive explanation

Self-concordance is a special convexity property that tightly controls how the Hessian (curvature) can change—the third derivatives are bounded by the Hessian's own magnitude. The key insight is that the self-concordance inequality, applied strategically to univariate or bivariate restrictions of ff, lets you extract bounds on individual third-derivative components by relating them to Hessian entries via the trilinear form hint. For part (b), the self-concordance constraint is so restrictive that any direction in the Hessian's nullspace at one point must remain in the nullspace everywhere. Part (c) shows how the Hessian evolves along a direction: the denominator (1−tα)−2(1 - t\alpha)^{-2} quantifies the "local norm" of that direction, controlling curvature change in a precise, quantifiable way.

Related theory

Browse the problem library