# Quadratic programming for degenerate case

$$\min xQx^T$$ If $Q$ is a positive semi-definite but not a positive definite matrix i.e $Q$ is degenerate. Then how to solve this quadratic programming on the linear constrains which is bounded closed area.

I think the optimal value should be exist. Is it in the boundary of the constrain area? It's very strange that, when we discuss the SDP problem, we include the case $Q$ is degenerate, but I never see the information of solution of the degenerate case.

• Why $xQx^T$ and not $x^TQ\,x$? – Rodrigo de Azevedo Jul 17 '17 at 12:15

As to how you would solve the problem, you would solve it the same way you would if $Q$ were not degenerate. Yes, an optimal solution must exist: the objective function is continuous on a closed and bounded feasible region. I'm assuming the number of dimensions is finite, making the feasible region compact.
Degeneracy of $Q$ opens the door to the possibility of multiple optimal solutions. Let $x^*$ be an optimum in the relative interior of the feasible region, let $v$ be an eigenvector of $Q$ with eigenvalue $0$, and let $x_\epsilon=x^*+\epsilon v$. Then $x_{\epsilon}Qx_{\epsilon}^{\top}=xQx^\top$, so if $x_\epsilon$ is feasible, it is another optimum.
If the feasible region is full-dimension (and bounded), then by starting $\epsilon$ at 0 and increasing it gradually, you will eventually find an optimal $x_\epsilon$ on the boundary of the feasible region. On the other hand, when the feasible region is less than full dimension there is no guarantee of a boundary optimum.
Suppose we are in three dimensions with $$Q=\left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 0 \end{array}\right]$$and with constraints $-1\le x_1 \le 1$, $-1\le x_2 \le 1$, $x_3 = 0$. $Q$ is p.s.d. and degenerate, but the eigenvector with eigenvalue 0 is $(0,0,1)$, which is orthogonal to the feasible region. So $x=(0,0,0)$ is the unique optimum. Change the feasible region to $[-1, 1]^3$, which is full dimension, and now there are boundary optima at $(0,0,1)$ and $(0,0,-1)$.
• The optimum may be multiple, but the optimal value of $xQx^T$ should be unique right? And all the multiple optimum are generated by $x = x^* +\sum\epsilon_i v_i?$ – A.Oreo Jul 17 '17 at 1:53
• Yes, the optimal value is unique, and yes, all optima can be obtained as a linear combination of one particular optimum and a basis of the null space of $Q$. – prubin Jul 17 '17 at 14:05