4
$\begingroup$

I have the quadratic programming problem in $x$

$$\text{Minimize}\;\; x^T\Sigma x$$ $$\hspace{15mm}\text{Subject to}\;\; p^Tx = \frac{1}{n}p^T\boldsymbol{1}$$ $$\hspace{25mm}\boldsymbol{1}^Tx=1$$

where $\Sigma$ is positive semidefinite. I can convert this to an epigraph problem

$$\text{Minimize}\;\; t$$ $$\hspace{16mm}\text{Subject to}\;\; x^T\Sigma x \leq t$$ $$\hspace{43mm} p^Tx = \frac{1}{n}p^T\boldsymbol{1}$$ $$\hspace{32mm}\boldsymbol{1}^Tx=1$$

where one of the constraints is now quadratic. I would like to use the Schur complement in order to convert the first constraint to the requirement that the following matrix is positive semidefinite

\begin{bmatrix} \Sigma^{-1} & x\\ x^T & t \end{bmatrix}

Unfortunately, $\Sigma$ is only positive semidefinite, and not strictly positive definite, and thus I cannot invert it. Is there a way to circumvent this?

$\endgroup$
5
$\begingroup$

One option here is to use the pseudoinverse of $\Sigma$ rather than the actual inverse. Appendix A of Boyd and Vandenberghe discusses a version of the Schur complement that includes this case.

Another alternative is to find a factorization of $\Sigma$ as

$\Sigma=M^{T}M$ (e.g. by eigenvalue decomposition), and then use the Schur theorem on

$\left[ \begin{array}{cc} I & Mx \\ x^{T}M^{T} & t \end{array} \right]. $

$\endgroup$
  • $\begingroup$ Does the pseudo-inverse result in a loss in accuracy? Or is there a specific case of Schur's theorem for the pseudo-inverse? Also, is this factorization done via Cholesky decomp? Or are you saying to split its eigen-decomp $M^TDM=(M^T\sqrt{D})(\sqrt{D}M)$? And if so either runs in O(n^3) correct? so it would become prohibitively expensive for matrices with millions of rows? $\endgroup$ – Thoth Jan 21 '15 at 4:48
  • $\begingroup$ There is a specific case of Schur's theorem using the pseudoinverse- see the reference that I gave. You can't compute a Cholesky factorization of $\Sigma$ since it is not positive definite, but you can certainly compute an eigenvalue decomposition in $O(n^{3})$ time. As a practical matter you certainly don't want to use SDP to solve this problem at all- the original formulation as a linearly constrained convex QP is much better solved directly by codes for that problem. $\endgroup$ – Brian Borchers Jan 21 '15 at 4:48
  • $\begingroup$ I guess the problem was that it's not possible to tell the default solver (Convex.jl in Julia) that $\Sigma$ is positive semidefinite, and so it regarded it as not DCP compliant. Thank you for the detailed responses, this makes a lot more sense now. $\endgroup$ – Thoth Jan 21 '15 at 4:51
  • $\begingroup$ Be aware that some QP codes will work only on problems where the objective is strictly convex. As a practical matter, you can't really tell numerically whether a matrix is positive semidefinite or indefinite- you may be better off modifying $\Sigma$ just enough to make it obviously PD. $\endgroup$ – Brian Borchers Jan 21 '15 at 5:02
  • $\begingroup$ It should be mentioned that using the pseudo-inverse form of the Schur complement doesn't work in this case, since the requirement that $(\text{I} - \Sigma\Sigma^{\dagger})x=0$ is only satisfied when $\Sigma$ is strictly positive definite (invertible). $\endgroup$ – Thoth Jan 29 '15 at 5:49

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.