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

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?

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.