# $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?

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