In Example 5.6 of Boyd & Vandenberghe's Convex Optimization, the problem is
$$ \text{minimize} \quad \Vert Ax - b\Vert,$$
where $\Vert \cdot \Vert$ is any norm. Reformulating by introducing a new variable, we get:
$$ \text{minimize} \,\, \Vert y\Vert \quad s.t. \, Ax-b=y$$
The Lagrange dual of this problem he claims is: $$ \text{maximize} \,\, b^T\nu \quad s.t. \Vert \nu\Vert_{*} \leq 1 \quad\text{and} \quad A^T\nu=0$$
My question is, is this correct? For my dual formulation I am getting: $$ g(\nu)=\text{inf}_y \{ \Vert y\Vert - y^T \nu \} - b^T\nu,$$ taking into account that $A^T\nu=0$.
Using the fact that the dual of norm is the indicator, I get the dual as:
$$ \text{maximize} \,\, -b^T\nu \quad s.t. \Vert \nu\Vert_{*} \leq 1 \quad\text{and} \quad A^T\nu=0$$
That has a negative sign. I cannot seem to understand where I am making a mistake. Any help would be appreciated. Thanks.
Informally: $\min_x \|Ax-b\| = \min_x \sup_{\|\nu\|_* \le 1} \nu^T(Ax-b) = \sup_{\|\nu\|_* \le 1} \inf_x \nu^T(Ax-b)$.
Note that if $\nu^TA \neq 0$ we can pick $x$ so that $\nu^T(Ax-b)$ is unbounded below, so $\sup_{\|\nu\|_* \le 1} \inf_x \nu^T(Ax-b) = \sup_{\|\nu\|_* \le 1, \nu^TA = 0} \inf_x \nu^T(-b) = \sup_{\|\nu\|_* \le 1, \nu^TA = 0} -\nu^Tb$ and hence $\min_x \|Ax-b\| = \max_{\|\nu\|_* \le 1, \nu^TA = 0} \nu^Tb$.
Elaboration:
Note that $\max_{\|\nu\|_* \le 1, \nu^TA = 0} -\nu^Tb = \max_{\|-\nu\|_* \le 1, (-\nu)^TA = 0} -\nu^Tb = \max_{\|\nu\|_* \le 1, \nu^TA = 0} \nu^Tb $.