Derive the dual function $g(\lambda, \nu)$ for the least-norm problem

Question

I am trying to find the dual function $g(\lambda, \nu)$ to this problem

$$\min\limits_{Ax = b} \|x\|$$

Step 1. Form the Lagrangian

$$L(x, \lambda, \nu) = \|x\| + \nu^T(Ax-b) = \|x\| + \nu^TAx - \nu^Tb$$

Step 2. Take the inf over all $x$ to get $g(\lambda, \nu)$

$g(\lambda, \nu)$ = $\inf\limits_x (\|x\| + \nu^TAx - \nu^Tb)$

Then by property of $\inf$, we have:

$\inf\limits_x (\|x\| + \nu^TAx - \nu^Tb) = \inf\limits_x \|x\| + \inf\limits_x \nu^TAx - \inf\limits_x \nu^Tb$

Notice:

• $- \inf\limits_x \nu^Tb = -\nu^Tb$, not much to do here

• $ \inf\limits_x \nu^TAx = \inf\limits_x (A^T\nu)^Tx$ looks like a dual norm i.e. $\|A^T\nu\|_{*} = \inf\limits_x\{ (A^T\nu)^Tx | \|x\|\leq 1\}$, but here we have a constraint $\|x\|\leq 1$

Then we have

$g(\lambda, \nu)$ = $\inf\limits_x (\|x\| + \nu^TAx - \nu^Tb) = \inf\limits_x \|x\| + \|A^T\nu\|_{*} - \nu^Tb$, $\|x\| \leq 1$

Does anyone know how to deal with the $\|x\| \leq 1$ constraint and proceed from above?

Answer 1

Your're almost there...

Recall the definition of convex conjugates. Recall that the convex conjugate of a norm $\|.\|$ is the indicator function of the unit ball of the dual norm $\|.\|_*$. Now,

\begin{equation} \begin{split} g(\nu) &:= \underset{x}{\inf }L(x,\nu) = \underset{x}{\inf }\|x\| + \nu^T Ax - \nu^T b = \nu^Tb -\underset{x}{\sup }x^T(-A^T\nu) - \|x\|\\ &= \nu^Tb -\|.\|^*(-A^T\nu) = \begin{cases}\nu^Tb, &\mbox{ if }\|A^T\nu\|_* \le 1,\\-\infty, &\mbox{ else.}\end{cases} \end{split} \end{equation}

Thus the dual problem is: \begin{equation} \text{Maximize } \nu^Tb\text{ subject to }\|A^T\nu\|_* \le 1. \end{equation}

Example: For example, if $\|.\|$ is the $\ell_1$-norm, then your original problem is the well-known Basis Pursuit problem, and the dual we've obtained is a linear program (you're maximizing a linear function on a polytope).

Notes: Using the Fenchel-Rockafellar duality Theorem, you can obtain the sought-for dual formulation in exactly one line!