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.
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. $