Conditions necessary to ensure unique minimizer of $\min_x \frac{1}{2} \| Ax−b \|^2 $?

Question

I'm doing a few exercises of convex optimization using notes for a previous course offering, and one of them asks for conditions necessary to ensure unique minimizer. I looked at the solution, but I have some doubts about its legitimacy.

My answer:
*The necessary condition for a unique minimizer is $\nabla f(\vec x)= \vec 0 $ has a unique solution.

Just to confirm, I also stated: convexity is neither necessary nor sufficient, and strictly convex is necessary, but not sufficient.

For the specific subproblems, here are my answers:

• $\min_{x} \frac{1}{2} ‖Ax−b‖^2 $, since the gradient is $\nabla f(x) = A^T (Ax-b) = \vec 0$, the conditions are that $(Ax-b)=0$ and hence that $A$ is non-singular.

Solutions:

• $\min_{x} \frac{1}{2} ‖Ax−b‖^2 $ the conditions are that $A$ is full rank.

My questions Is it true in general that convexity is neither necessary nor sufficient, and strictly convex is necessary, but not sufficient?

I have some doubt about the solutions. If the matrix $A$ is not square, then full-rank would only guarantee there to exist a solution to $Ax=b$, but it would not guarantee that the $x$ vector would be unique. So how does it guarantee unique minimization?

(If I rearrange the equation to be $A^T A x = A^T b$, then I'm able to see that we only require $A^T A$ to be invertible, which occurs IFF $A$ is full rank. But when the expression is arranged as $A^T(Ax-b)=0$, it still seems to me as if we require $(Ax-b)=0$)

Answer 1

In geometric terms, the problem can be restated as find $x$ such that

$$ Ax=y=\operatorname{arg.min}\{\|z-b\|_2: z\in A(\mathbb{R}^n)\} $$ that is, $y$ is the best approximation to $b$ by vectors in the range of $A$.

A solution to the problem is $x=A^+b$ where $A^+$ is the Moore-Penrose pseudo inverse. This solution will also give you the $x$ among all minimizers of the least square problem with the minimum Euclidean norm.

The following links contain useful information about all this. https://en.wikipedia.org/wiki/Linear_least_squares

https://en.wikipedia.org/wiki/Moore–Penrose_inverse

Some comments:

• There is always a solution to the least square problem: (this has to do with the existence and uniqueness of orthogonal projection onto subspaces.
• The Generalize inverse of a matrix alway exists (there are different types of inverses)
• The Moonro-Penroese $A^+$ is a special generalized inverse and it is unique.
• When $A$ is of full rank, $A^+=(A^*A)^{-1}A^*b$.

Answer 2

There are many perspectives that are possible here, I will try to answer this from an optimization/convex analysis perspective. First, it is true that an unconstrained convex function has a unique minimum if and only it is strictly convex (if the function is not convex there's not much we can say about it's global minima. If the feasible set is not the entire space $\mathbb{E}$ then a unique minimum can exist on the boundry, even if the function is convex but not strictly convex).

Now, in your case $\min_{\mathbf{x}\in\mathbb{R}^n}\frac{1}{2}\|A\mathbf{x}-\mathbf{b}\|^2$ is an unconstrained convex problem. Meaning we need to find conditions that will make the objective function strictly convex. The necessary and sufficient condition for that is $A$ being full rank.

Why is full-rank of $A$ required? The most simple answer here is that a twice differentiable function is strictly convex if and only if it's Hessian is positive-definite. For your function $\nabla^2 f(\mathbf{x})=A^T A$ is always PSD, but since we want it to be PD we need $A$ to be full rank.