optimality of quadratic programming problems

Question

Suppose we have a general quadratic programming problem:

\begin{align} \min_{x}\,\,&c^Tx+\frac{1}{2}x^TQx,\\ \mbox{s.t.}\,\,& Ax=b,\\ &x\geq0, \end{align} where $Q$ is positive semi-definite, $A$ has full column rank. Suppose the problem is feasible.

Is it possible to prove that: if the problem is lower bounded, then there must be a feasible solution $x^{\ast}$ which optimizes the problem?

Answer 1

The problem is in my opinion the lag of positivity in Q. Usually You would start by stating that if the problem is bounded from below we can find a minimizing sequence $(x_{n})_{n\in N}$, such that $$\forall n: x_{n}\hbox{ is feasible, that is: } x_{n}\geq0\wedge Ax_{n}=b \ \forall n\in N$$ Now the question of will the $x_{n}$ converge, has to be answered: Assuming we have this minimizing sequence we know that there is $C>0$ such that $$ c^{T}x_{n}+\tfrac{1}{2}x_{n}^{T}Qx_{n}\leq C\ \forall n\in N. $$ If we could now argue that $x_{n}$ is uniformly bounded (for instance if $Q$ would be positiv definite, we had the postulated property, also if the kernel of $Q$ would be compensated by the equality constraint), we could use Bolzano Weierstrass, to conclude that there is a subsequnce converging to $x_{\infty}$). Then showing that the limit will also be feasible You are almost done. Nevertheless this is not possible here...but maybe it is helpful?

Answer 2

Let us consider the problem without the non-negativity constraint: \begin{align} \min_{x}\,\,&f(x):=c^Tx+\frac{1}{2}x^TQx,\\ \mbox{s.t.}\,\,& Ax=b \end{align} where $Q$ is positive semi-definite, $A$ has full column rank.

Any solution to the linear problem $Ax=b$ can be written as $x=x_p+Zy$, where $x_p$ is a particular solution to the problem (which we know exists since the QP is feasible by assumption), $Z$ is a base of $Ker(A)$ and $y$ a vector. Substituting $x$ into the objective function, we can transform the original constrained QP into an unconstrained QP in $y$. The equivalent QP thus reads: \begin{align} \min_{y}\,\,&f(x_p)+\frac{1}{2}y^TZ^TQZy+c^TZy+x_p^TQZy \end{align} The first order necessary condition for this problem is then: \begin{equation} (Z^TQ^TZ)y=-Z^T(Qx_p+c) \end{equation} At this point, there are two possibilities:

1. Either $(Z^TQ^TZ)$ is positive definite and all is good, the above system has a unique solution $y^*$ given by: \begin{equation} y^*=-(Z^TQ^TZ)^{-1}Z^T(Qx_p+c) \end{equation} from which we retrieve a unique optimal $x^*$ as: \begin{equation} x^*=x_p+Zy^* \end{equation}
2. Or $(Z^TQ^TZ)$ is positive semi-definite and we must be more careful. Remember from linear algebra that a linear system $Px=q$ has solutions if and only if $q$ is orthogonal to $Ker(P^T)$. In our case, this implies that the system \begin{equation} (Z^TQ^TZ)y=-Z^T(Qx_p+c) \end{equation} has solutions (and thus so does the QP) if and only if $Z^T(Qx_p+c)$ is orthogonal to $Ker(Z^TQ^TZ)$. Suppose this is not the case, then there exists a vector $y$ such that: \begin{align} y^T Z^T(Qx_p+c)&\neq 0\\ (Z^TQ^TZ)y&=0 \end{align} which also holds for any vector $w=\alpha y$, where $\alpha\in\mathbb{R}$ ($\alpha\neq 0$). Plugging this $w$ into the objective of the unconstrained QP yields an objective function of the form: \begin{align} f(x_p)+\frac{\alpha^2}{2}y^TZ^TQZy+\alpha c^TZy+\alpha x_p^TQZy&=f(x_p)+\alpha y^TZ^T(Qx_p+c) \end{align} and since $y^TZ^T(Qx_p+c)\neq 0$, we could let the value of the objective function fall arbitrarily low by letting $\alpha\to\infty$ or $\alpha\to-\infty$ (depending on the sign of $y^TZ^T(Qx_p+c)$ ), violating the boundedness assumption. It follows that the system \begin{equation} (Z^TQ^TZ)y=-Z^T(Qx_p+c) \end{equation} has solutions and so does the QP, with an optimal objective value of $f(x_p)$, where $x_p$ is any solution to $Ax=b$.

Going back to the initial problem with the non-negativity constraint, we see that the previous reasoning does not readily apply because by letting $\alpha\to\infty$ or $\alpha\to-\infty$, the resulting vector $x=x_p+\alpha Zy$ might violate the non-negativity constraint. There is thus a little more work to be done, but I believe this is the right path...