How to show directly $\min \frac{1}{2}\|x-z\|_2^2$ has a unique global minimizer over $Ax=b$?

Question

Consider the following problem:

$$ \min_{Ax=b} \frac{1}{2}\|x-z\|_2^2 $$ where $z \in \mathbb{R}^{n}$ is a given vector, $x \in \mathbb{R}^{n}$, $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^{m}$.

Show that there exists a unique global minimizer?

My try:

It is clear that this problem is a convex optimization problem and the local minimizer is a global minimizer. Also, it is strogly convex so it has at most one global minimizer. However, can we show the uniqueness of the minimizer directly? To that end, we need to need to assume $x^*, y^* \in \mathbb{R}^{n}$ be to global minimizer.

$$ \frac{1}{2}\|x^*-z\|_2^2 \leq \frac{1}{2}\|x-z\|_2^2\,\,\, \forall x $$

Also, $$ \frac{1}{2}\|y^*-z\|_2^2 \leq \frac{1}{2}\|x-z\|_2^2\,\,\, \forall x $$

Using these two we need to come up with a contradiction. How?

Answer 1

The set $C:=\{x\in\Bbb R^n : Ax=b\}$ is an affine subset, hence it is closed and convex. The projection of $z$ into $C$ has a unique solution i.e. $\exists x_0\in C$ such that $$ ||x_0 - z||_2 = \min_{y\in C} ||y-z||_2. $$ It is easy to see that $x_0$ also solves your minimization problem. (You can prove the existence of $x_0$ by taking a minimizing sequence and use compactness argument to show that it converges. The statement is even true for a Hilbert space but the prove is a bit more involved.)

For the second part, $\frac 12||\cdot - z||^2_2$ is strictly convex. Assume for contradiction that there exist two distinct minimizers $x_1, x_2$ and show that $\frac {x_1+x_2}2$ is an even better minimizer. (In fact, the uniqueness of the projection from the previous part already implies uniqueness of the minimizer.)

Answer 2

If we introduce $y=x-z$, the problem takes the form of a least squares problem $$ \min_{Ay=b-Az} \frac12\|y\|_2^2, $$ which has an unique global minimizer $y= A^{+}(b-Az)$. Thus, the global minimizer of the original problem is $x=A^{+}(b-Az)+z$.