When QP is unbounded?and when is bounded?

Question

When the problem is

$$\min q(x)=(1/2)x^T Qx+c^T x$$

subject to

$$Ax\le b$$

Is it unbounded? More generally, when is it bounded?

And when is

$$\min q(x)= (1/2)x^TQx+c^Tx$$

bounded?

I think when $Q>0$? Is this correct?

Answer 1

For sure whenever $Q > 0$ (w.r.t. the semidefinite cone) this is bounded (no matter the constraints).

In the case of the linear inequality, you have to be far more careful: the inequality generates a convex set, so this program is bounded only when for every eigenvector $v$ of $Q$ corresponding to a negative eigenvalue, there exists a supporting hyperplane of the set generated by $Ax \le b$ whose normal vector is parallel to $v$. The same must also hold for $-c$. These are only sufficient, though, since generating necessary conditions is a bit more of a case by case basis.

Essentially, this says that we can't go 'too far' in the direction of a negative eigenvalue since the set given by $Ax \le b$ prevents us from doing so.

The case of linear equality is simpler. I'll leave it as an exercise with the following hint: consider the nullspace of $A$ in conjunction with the null space of $Q$ and their relationship with $b$.