Quadratic programming for degenerate case

390 Views Asked by At

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

1

There are 1 best solutions below

2
On BEST ANSWER

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