Convex Optimization · Problem 6.6

Statistical estimation — Boyd & Vandenberghe

Mathematics — Optimization · duals-penalty-function-approximation

Problem

Duals of some penalty function approximation problems. Derive a Lagrange dual for the problem

\begin{aligned} \text{minimize} & \quad \sum_{i=1}^m \phi(r_i) \\ \text{subject to} & \quad r = Ax - b, \end{aligned}

for the following penalty functions

\phi : \mathbf{R} \to \mathbf{R}

. The variables are

x \in \mathbf{R}^n

r \in \mathbf{R}^m

. (a) Deadzone-linear penalty (with deadzone width

a = 1

\phi(u) = \begin{cases} 0 & |u| \leq 1 \\ |u| - 1 & |u| > 1. \end{cases}

(b) Huber penalty (with

M = 1

\phi(u) = \begin{cases} u^2 & |u| \leq 1 \\ 2|u| - 1 & |u| > 1. \end{cases}

a = 1

\phi(u) = -\log(1 - u^2), \quad \mathbf{dom}\, \phi = (-1, 1).

(d) Relative deviation from one,

\phi(u) = \max\{u, 1/u\} = \begin{cases} u & u \geq 1 \\ 1/u & u \leq 1, \end{cases}

with

\mathbf{dom}\, \phi = \mathbf{R}_{++}