# Prove this function is unbounded below

Given a function

$$f(x) = \frac{1}{2}x^TAx + b^Tx + c$$

, where $A \succeq 0$, $A \in \mathbf S^n$, and equation $\nabla f = Ax + b = 0$ has no solution. We need to prove that $f(x)$ is unbounded below.

Here's my approach:

$Ax + b = 0$ has no solution means $b \notin \mathcal R(A)$.

$$b \notin \mathcal R(A) \Rightarrow \mathcal N(A) = \mathcal N(A^T) \ne \{0\}$$

so we have:

$$\exists\ v \ne 0,\ Av = 0$$

Let $x = tv$, where $t \in \mathbb R$, we have

$$f = tb^Tv + c$$

This is a linear function of $t$, and $f$ is unbounded below if $b^Tv \ne 0$. The problem is I can't think of a way to prove $b^Tv \ne 0$.

$b$ doesn't belong to column space of $A$. Consider an orthogonal basis for null space of $A$. $b$ can be written as a linear combination of these basis vectors and columns of $A$, and in that linear combination the coefficient of at least one of the vectors from the basis of $null(A)$ must be non zero. Take that vector as $v$.

• Although I take it for granted that to say $A$ is positive semidefinite means that $A$ is symmetric, some people don't have that convention. So perhaps you want the nullspace of $A^\top$? – Ted Shifrin Dec 8 '17 at 4:47
• Yeah. I assumed it to be symmetric – QED Dec 8 '17 at 4:50
• Thanks. I see that such a $v$ satisfies $Av = 0$, but I still don't understand why $b^Tv \ne 0$. Could you please explain this in more details? – hklel Dec 8 '17 at 4:52
• @TedShifrin sorry I should have mentioned that $A$ is symmetric in the question. Edited. – hklel Dec 8 '17 at 4:54
• If $b=Ax+c_1v_1+\cdots c_kv_k$ where $\{v_1,\cdots,v_k\}$ is an orthogonal basis for null space of $A$, and also if $c_i$ is non zero, then $b^tv_i=c_iv^tv$, which is non zero. – QED Dec 8 '17 at 4:57

I've accepted @AbishankaSaha 's answer, but I just found another way of proving the statement, so I am posting it here in case it helps someone.

Since $Ax + b = 0$ has no solution, we know that $b \ne 0$, and

$$b \notin \mathcal R(A) \Rightarrow b \in \mathcal N(A^T) = \mathcal N(A)$$

That is

$$b \ne 0,\ Ab = 0$$

. Let $x = tb$, where $t \in \mathbb R$, we have

$$f = tb^Tb + c$$

, which is a linear function of $t$ with the term $b^Tb$ being non-zero. Thus $f$ is unbounded below.

• Thank you for your response. About your answer, why you have assumed $x=tb$? Can't $x$ take other values? – Media Apr 11 '20 at 16:50