How to show that an optimization problem is equivalent to the Least Squares problem?

Question

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?

Answer 1

The minimum value of $\|Ax - b\|$ occurs at the same $x$ as the minimum value of $\|Ax−b\|^2$. I think that's what the author of this problem means when they say the two optimization problems are equivalent: Solving one will solve the other.