Consider the problem $$\text{min}_{x\in\mathbb R^n}\lvert Ax-b\rvert,$$
where $A$ is a $m \times n$ matrix and $b\in\mathbb R^m.$
Rewrite the problem into the form$$(P)\qquad \text{Minimize }\lvert z\rvert, \text{subject to }Ax-b=z.$$
My problem is how to show the dual problem is indeed $$(D)\qquad\text{Maximize }b\cdot y, \text{subject to }\lvert y\rvert\le1,A^Ty=0.$$
My attempt:
I tried to use the Lagrangian Dual (c.f. http://www.stat.cmu.edu/~ryantibs/convexopt-F15/scribes/11-dual-gen-scribed.pdf )
The Lagrangian function will be $L(z,u,v)=L(z,v)=\lvert z\rvert+ v\cdot (z+b-Ax)$, and $g(u,v)=g(v)=\inf_zL(z,v).$ The Lagrangian Dual theory says that, $$\text{maximize }g(v) \text{ for }v\in \mathbb R^m,$$ is the dual problem $(D).$
But I can't show that $g(v)=b\cdot v$, and I don't know how to get the constraints $\lvert y\rvert\le1,A^Ty=0$ from the Lagrangian Dual. And furthermore, since $x$ is changing, $L$ should also depend on $x$. But in the Lagrangian Dual theory, $L$ can only depend on $z$ and $u,v$. I am quite confused with this point.
Hope someone can help me out of this.
Any help will be appreciated.
Best Answer
Let me help you with your problem for the case that $|\cdot|$ is the Euclidean norm.
Regarding $ g(u,v)=g(v)=\inf_{z,x} L(z,v),$ we have to minimize $\lVert z\rVert+ v^T (z+b-Ax)$ with respect to $z$ and $x$.
Therefore, we have $ g(v)= \inf_{z,x} \lVert z\rVert+ v^T (z+b-Ax) = v^T b $ when $ v^T A = 0$ and $ \lVert v\rVert \leq 1. $ Otherwise we have $ g(v)= \inf_{z,x} \lVert z\rVert+ v^T (z+b-Ax) = -\infty$.
If one wants to maximize $ g(v)$ it is consequently necessary to assure that $ v^T A = 0$ and $ \lVert v\rVert \leq 1. $