$Px=q $ doesn't have a solution? I was solving a problem in which I had to prove that (from Boyd's Convex optimization):$$ \text{minimize} \ (1/2)x^T P x + q^T x+ r $$ is a problem which is unbounded below if $P x^* = -q$ doesn't have a solution.
So clearly, $q \notin R(P)$, but what does this mean precisely? How can I use this fact to solve the problem?
 A: Assuming $r$ is constant, the problem is equivalent to minimizing:
$$\left\langle \frac12Px+q,x\right\rangle,$$
or minimizing $\langle Px+2q,x\rangle$. Writing $x=t\cdot u$, where $t\in \mathbb{R}$, we get the expression:
\begin{align}\tag{1}\label{ex}t^2\cdot\langle Pu,u\rangle + 2t\langle q,u\rangle\end{align}
Letting $t$ vary, we conclude that whenever there is some $u$ such that $\langle Pu,u\rangle < 0$, then $\eqref{ex}$ is unbounded from below. In other words, unless $P$ is positive semidefinite, $\eqref{ex}$ is unbounded from below.
When $P$ is positive definite, for each $u$, $\eqref{ex}$ attains its minimum at
$$t=-\frac{\langle q,u\rangle}{\langle Pu,u\rangle}$$
with value
$$m(u)=-\frac{{\langle q,u\rangle}^2}{\langle Pu,u\rangle}$$
Notice that $m(u)=m(t\cdot u)$. Moreover, since $P$ is positive definite, $\langle Pu,u\rangle >0$ whenever $u\neq 0$. This implies that $m$ is continuous on the sphere of radius $1$, a compact set. It follows that $m$ attains a minimum, and hence the minimization has a solution.
When $P$ is positive semidefinite (but not definite), there is some nonzero $u$ with $\langle Pu,u\rangle = 0$. For those $u$, expression $\eqref{ex}$ becomes $2t\langle q,u\rangle$, so that unless $\langle q,u\rangle = 0$ the expression is unbounded from below.
Now, suppose $P$ is positive semidefinite (but not definite) and that is has the property that $\langle Pu,u\rangle = 0 \implies \langle q,u\rangle=0$. This implies that $Z=\{u\,|\,\langle Pu,u\rangle=0\}\subset q^{\perp}$. I could not quite solve this case.

Notice that if $u$ is such that $Pu=-q$, then expression $\eqref{ex}$ becomes
$$(2t-t^2)\langle q,u\rangle$$
and hence if $\langle q, u\rangle>0$ then the expression is unbounded from below, even if a solution exists to $Px^*=-q$.
