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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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]. $

Improve this answer
$\endgroup$
5
  • $\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$ Commented Jan 21, 2015 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$ Commented Jan 21, 2015 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$ Commented Jan 21, 2015 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$ Commented Jan 21, 2015 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$ Commented Jan 29, 2015 at 5:49

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.