Convex Optimization · Problem 6.1

Statistical estimation — Boyd & Vandenberghe

Mathematics — Optimization · quadratic-bounds-log-barrier-penalty

Problem

Quadratic bounds for log barrier penalty. Let ϕ:R→R\phi : \mathbf{R} \to \mathbf{R} be the log barrier penalty function with limit a>0a > 0: ϕ(u)={−a2log⁡(1−(u/a)2)∣u∣<a∞otherwise.\phi(u) = \begin{cases} -a^2 \log(1-(u/a)^2) & |u| < a \\ \infty & \text{otherwise.} \end{cases} Show that if u∈Rmu \in \mathbf{R}^m satisfies ∥u∥∞<a\|u\|_\infty < a, then ∥u∥22≤∑i=1mϕ(ui)≤ϕ(∥u∥∞)∥u∥∞2∥u∥22.\|u\|_2^2 \leq \sum_{i=1}^m \phi(u_i) \leq \frac{\phi(\|u\|_\infty)}{\|u\|_\infty^2} \|u\|_2^2. This means that ∑i=1mϕ(ui)\sum_{i=1}^m \phi(u_i) is well approximated by ∥u∥22\|u\|_2^2 if ∥u∥∞\|u\|_\infty is small compared to aa. For example, if ∥u∥∞/a=0.25\|u\|_\infty/a = 0.25, then ∥u∥22≤∑i=1mϕ(ui)≤1.033⋅∥u∥22.\|u\|_2^2 \leq \sum_{i=1}^m \phi(u_i) \leq 1.033 \cdot \|u\|_2^2.

Browse the problem library