Convex Optimization · Problem 9.4

Equality constrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · l1-norm-approximation-newton-method

Problem

Do you agree with the following argument? The

\ell_1

-norm of a vector

x \in \mathbf{R}^m

can be expressed as

\|x\|_1 = (1/2) \inf_{y \succ 0} \left( \sum_{i=1}^m x_i^2 / y_i + \mathbf{1}^T y \right).

Therefore the

\ell_1

-norm approximation problem

\text{minimize} \quad \|Ax - b\|_1

is equivalent to the minimization problem

\text{minimize} \quad f(x, y) = \sum_{i=1}^m (a_i^T x - b_i)^2 / y_i + \mathbf{1}^T y, \tag{9.62}

with

\mathbf{dom}\, f = \{(x, y) \in \mathbf{R}^n \times \mathbf{R}^m \mid y \succ 0\}

, where

a_i^T

is the

i

th row of

A

. Since

f

is twice differentiable and convex, we can solve the

\ell_1

-norm approximation problem by applying Newton's method to (9.62).