Convex Optimization · Problem 6.3

Statistical estimation — Boyd & Vandenberghe

Mathematics — Optimization · penalty-approximation-formulations

Problem

Formulate the following approximation problems as LPs, QPs, SOCPs, or SDPs. The problem data are

A \in \mathbf{R}^{m \times n}

and

b \in \mathbf{R}^m

. The rows of

A

are denoted

a_i^T

. (a) Deadzone-linear penalty approximation: minimize

\sum_{i=1}^m \phi(a_i^T x - b_i)

, where

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

where

a > 0

. (b) Log-barrier penalty approximation: minimize

\sum_{i=1}^m \phi(a_i^T x - b_i)

, where

\phi(u) = \begin{cases} -a^2 \log(1-(u/a)^2) & |u| < a \\ \infty & |u| \geq a, \end{cases}

with

a > 0

. (c) Huber penalty approximation: minimize

\sum_{i=1}^m \phi(a_i^T x - b_i)

, where

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

with

M > 0

. (d) Log-Chebyshev approximation: minimize

\max_{i=1,\ldots,m} |\log(a_i^T x) - \log b_i|

. We assume

b \succ 0

. An equivalent convex form is

\begin{aligned} \text{minimize} & \quad t \\ \text{subject to} & \quad 1/t \leq a_i^T x/b_i \leq t, \quad i = 1, \ldots, m, \end{aligned}

with variables

x \in \mathbf{R}^n

and

t \in \mathbf{R}

, and domain

\mathbf{R}^n \times \mathbf{R}_{++}

. (e) Minimizing the sum of the largest

k

residuals:

\begin{aligned} \text{minimize} & \quad \sum_{i=1}^k |r|_{[i]} \\ \text{subject to} & \quad r = Ax - b, \end{aligned}

where

|r|_{[1]} \geq |r|_{[2]} \geq \cdots \geq |r|_{[m]}

are the numbers

|r_1|, |r_2|, \ldots, |r_m|

sorted in decreasing order. (For

k = 1

, this reduces to

\ell_\infty

-norm approximation; for

k = m

, it reduces to

\ell_1

-norm approximation.) Hint. See exercise 5.19.