Convex Optimization · Problem 9.19

Equality constrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · bound-distance-from-optimum-self-concordant

Problem

Bound on the distance from the optimum. Let

f : \mathbf{R}^n \to \mathbf{R}

be a strictly convex self-concordant function. ((a)) Suppose

\lambda(\bar{x}) < 1

and the sublevel set

\{x \mid f(x) \leq f(\bar{x})\}

is closed. Show that the minimum of

f

is attained and

\left( (\bar{x} - x^\star)^T \nabla^2 f(\bar{x})(\bar{x} - x^\star) \right)^{1/2} \leq \frac{\lambda(\bar{x})}{1 - \lambda(\bar{x})}.

((b)) Show that if

f

has a closed sublevel set, and is bounded below, then its minimum is attained.