2
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

$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$.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Ted Shifrin Dec 8 '17 at 4:47
  • $\begingroup$ Yeah. I assumed it to be symmetric $\endgroup$ – Abishanka Saha Dec 8 '17 at 4:50
  • $\begingroup$ 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? $\endgroup$ – hklel Dec 8 '17 at 4:52
  • $\begingroup$ @TedShifrin sorry I should have mentioned that $A$ is symmetric in the question. Edited. $\endgroup$ – hklel Dec 8 '17 at 4:54
  • $\begingroup$ 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. $\endgroup$ – Abishanka Saha Dec 8 '17 at 4:57
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.