# Minimize $\mathrm{Tr}((G^TG)^{-1})$

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?

• 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$. – Rajat Dec 1 '15 at 20:06
• First of all, thank you for the reply :) – Perplexabot Dec 1 '15 at 20:23
• 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? – Perplexabot Dec 1 '15 at 20:32

## 1 Answer

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.

• 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. – Michael Grant Dec 1 '15 at 23:52
• 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. – Perplexabot Dec 2 '15 at 0:27
• 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. – Perplexabot Dec 2 '15 at 0:29
• 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? – Perplexabot Dec 2 '15 at 1:32
• 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 – Johan Löfberg Dec 2 '15 at 19:40