0
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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?$ $\endgroup$ – A.Oreo Jul 17 '17 at 1:53
  • $\begingroup$ 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$. $\endgroup$ – prubin Jul 17 '17 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.