I hope you guys can lend me a hand with this one.
Let $A\in \mathbb{R}^{m\times{n}}$ and $b\in \mathbb{R}^{m}$, and consider the following optimization problem:
$\min_{x\in\mathbb{R}^{n}} \max_{y\in\mathbb{R}^{m}, ||y||_{2}\le1} y^T(Ax-b)$
I need to show that this problem is equivalent to the Least Squares problem, aka: $\min_{x\in\mathbb{R}^{n}} ||Ax-b||_{2}^{2}$
Here's my take on this problem: I'm first considering only the inner optimization problem, which is $\max_{y\in\mathbb{R}^{m}, ||y||_{2}\le1} y^T(Ax-b)$.
When using the substitution $d=Ax-b$, I get:
$y^{T}(Ax-b) \le ||d||_{2}\cdot||Ax-b||_{2}$
(This can be done by using the Cauchy-Schwarz inequality and by the fact that $||y||_2 \le 1$) Thus I can choose $y=\frac{d}{||d||_{2}}$, and this particular $y$ is the solution to the inner optimization problem.
The thing is, when I choose this particular $y$, I get that the optimization problem is actually
$\min_{x\in\mathbb{R}^{n}} \max_{y\in\mathbb{R}^{m}, ||y||_{2}\le1} y^T(Ax-b) = \min_{x\in\mathbb{R}^{n}} ||Ax-b||_{2}$
But I need it to be $\min_{x\in\mathbb{R}^{n}} ||Ax-b||_{2}^{2}$, and I had some problems getting to that term squared.
Any suggestions?