2
$\begingroup$

I have been trying to minimize $\mathrm{Tr}((G^TG)^{-1})$ using CVX. I have formulated it in the following SDP structure, using Schur Complement. Here is the formulation: $$\mathbf{minimise} \ \ t \\\mathbf{subject\ \ to}$$ $$\begin{bmatrix} I & G \\G^T & -X \end{bmatrix} \succeq 0 \qquad \begin{bmatrix} Z & I \\ I & X \end{bmatrix} \succeq 0 \qquad \mathop{\textrm{Tr}}(Z)\leq t$$

For the first matrix (the matrix with $G$ in it), the inequality inferred by Schur complement is $X \preceq -G^TG$ (this requires $I$ to be positive definite, which it is by definition)

For the other matrix, the inequality inferred by Schur complement is $Z \succeq X^{-1}$ (this requires $Z$ to be positive definite)

So, I did plug this in CVX but the result does not seem legitimate. Can someone please tell me if my formulation is correct?

$\endgroup$
  • $\begingroup$ But if there are no more constraints then it must be $0$ because $G^TG$ is PSD as well as its inverse. So, the minimum of sum of the eigenvalues is $0$. $\endgroup$ – Rajat Dec 1 '15 at 20:06
  • $\begingroup$ First of all, thank you for the reply :) $\endgroup$ – Perplexabot Dec 1 '15 at 20:23
  • $\begingroup$ Interesting... Is it true that the inverse of a PSD is also a PSD? PSDs can have eigenvalues of zero tho, thus making the inverse not possible (singular), am I wrong to think that? When plugging this into CVX, and setting a fixed $G$ (just to see if CVX can handle it), I get an optimal value of infinity and find that $Z \neq (G^TG)^{-1}$, but this is not correct, $Z$ must equal $(G^TG)^{-1}$ Would it help to post my code? EDIT: Would you say my formulation is correct tho? $\endgroup$ – Perplexabot Dec 1 '15 at 20:32
1
$\begingroup$

Your model is wrong, which sort of is hinted by the obvious problem that the first constraint forces $X$ to be negative semidefinite, while the seconds forces it to be positive semidefinite

You have $Z \geq (G^TG)^{-1}$, and you then introduce a new variable $X$ to model $G^TG$. However, I don't see why you introduce the constraint $X \preceq -G^TG$. What you must have is $Z \succeq X^{-1} \succeq (G^TG)^{-1}$, which means $X \preceq G^TG$, a non-convex set which cannot be written as a linear semidefinite constraint.

A simple way to realize that this cannot be cast as a linear semidefinite program is the fact that the function basically is $1/x^2$ in the scalar case, easily seen to be non-convex.

$\endgroup$
  • $\begingroup$ Grr, I can't believe I missed the easy test. I think because it resembled other LMI-compatible functions I didn't think to look for it. $\endgroup$ – Michael Grant Dec 1 '15 at 23:52
  • $\begingroup$ I see what you mean about $X$ having opposing semidefiniteness constraints. I did not notice that for this formulation. If you haven't noticed, I have learned this technique from an old reply you posted to this link: scicomp.stackexchange.com/questions/5503/… I have been trying to understand how you choose bounds for $X$ and $Z$. You say that I should have: $Z \succeq X^{-1} \succeq (G^TG)^{-1}$. How did you conclude that? I know my objective function cannot be formulated as such (thanks to your help) but I am just curious. $\endgroup$ – Perplexabot Dec 2 '15 at 0:27
  • $\begingroup$ Also, if I may add, how does one proceed with such an objective function? Or what path should I travel now? I still want to see if this is optimizable... I will be reading on nonconvex optimization I guess. $\endgroup$ – Perplexabot Dec 2 '15 at 0:29
  • $\begingroup$ Hmmm. I wonder if restricting the domain (what $G$ can be) will turn this problem into a convex problem. The reason I say this is because, looking at that scalar case you provided, if we restrict $x$ to be positive then, our function is convex... right? $\endgroup$ – Perplexabot Dec 2 '15 at 1:32
  • 1
    $\begingroup$ Yes, the scalar problem is convex on the restricted domain, but that will not help you as you will not be able to Schur-complement your way out of this model, as far as I can see $\endgroup$ – Johan Löfberg Dec 2 '15 at 19:40

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.