Just so you guys know, I was able to use CVX for the third case in my last post. Now I need to make sure my method and the answer from CVX is the correct one!
Apparently the G that minimizes \mathop{\textrm{Tr}}((G^TG)^{-1}) is a zero sparse matrix 
which makes no sense⊠If that is the case, then the inverse of (G^TG) does not exist since G is singular! I still need to double check my stuff.
Well, this obviously canât be right. So if you did faithfully render the transformation I offered above correctly within CVX, it must mean that formulation is not correct.
So I tried running all the cases (including the one you offered above) again, but this time I set X, Z and G to be symmetric variables (I didnât have that set earlier) and this gave a G that was not a zero matrix!
Here is where it gets interesting, if I donât set G to be symmetric (but leave Z and X to be symmetric), I still get G to be zero. This is weird. According to the structure (or transformation) you provided, there is no restriction that says G has to be symmetric, I understand X and Z do have to be symmetric but why G? I wonder if it has anything to do with precision in CVX⊠I will play around.
mcg, I am wondering if you read post #20⊠I extracted the Schur compliment inequalities (from which those matrices are based on) and found some interesting results. I think the transformation you provided needs to be modified. Of course, I am not certain of that. That is why I said âI thinkâ and that is why I am asking you.
Thank you for your reply and help.
EDIT1:
I was able to remove the âsymmetric restrictionâ from G and get a non zero matrix. Here is how I defined my variables:
variable G(realizCnt,GColSize)
variable t
variable X(GColSize,GColSize) symmetric
variable Z(GColSize,GColSize) nonnegative semidefinite
This worked (for both cases shown above).
EDIT2:
Using the above way to initialize cvx variables achieved a G,
I am afraid I cannot help further; paid work must take priority. Of course others are welcome to⊠Good luck!
No problem! You have helped a lot already!
Thank you for everything!
Hey again : / Sorry to be back here but I have one more question.
Assume the formulation provided above works (which it does! just not sure if i am using the correct transformation). Now say I wanted a certain structure of G. For example, for the first row of G, I want the first element to be the product of the second and third element (of the same row). How can I achieve this? I currently have the following (only part of my code):
cvx_begin sdp
variable G(realizCnt, GColSize)
minimize t;
subject to
%constraints provided earlier in this thread go here
G(1,1) == G(1,2)*G(1,3);
cvx_end
This gives the following error (regarding the constraint):
Disciplined convex programming error:
Invalid quadratic form(s): not a square
So this error makes some sense to me. I know that, according to the DCP ruleset, the right hand and left hand side of the equality constraint must be affine, My right hand side is not affine. Now the question remains, how does one make this affine? Is that even possible? Log function maybe?
Any help will be appreciated. Either way thank you for reading!
PS: I played around with âexpressionâ by defining G as an expression (rather than a variable). This actually gives me no errors BUT ends with a status of âFailedâ 
This also seems to make sense, since, if I am not mistaken, expression does not define the variable as a variable to be minimized.
I will of course be working on this in the mean time.
EDIT1: Iâm wondering if I should create a new topic for this question? I can just delete this post and copy it into a new thread. Sorry if I did wrong.
EDIT2: Changed the error I got, for some weird reason I messed up previously
Iâm afraid youâve definitely moved into nonconvex territory.
Hi again!
May I know how you were able to conclude that the formulation in my previous post is not convex?
I do not know how to proceed to prove nonconvexity?
Is this as simple as proving the hessian of x*y is not PSD?
Regards,
Perplexabot
Simpler than that: nonlinear equality constraints are always nonconvex. There are exceptions but they are incredibly rare. I have never seen someone create one that was not contrived. And it would be moot to do so, since no (convex) solver handles them.
Thank you for taking time to answer my questions : )
Can anyone please provide feedback regarding post #21?
I got case1 to work but not case2 or case3 : ( I have a powerful feeling my formulation is incorrect.
Any suggestions would be greatly appreciatedâŠ
EDIT: I know where my problem lies but I donât know how to remedy it⊠The problem is, my formulation (case 3 of post #21) achieves two inequalities that are both lower bounds of X! I need a lower bound and an upper bound tho, I need a formulation that can do that. I will be experimenting. If anyone has advice, please share : )
Hello again : )
So I think I have found the formulation that does achieve what I need. BUT, it seems cvx is having a hard time with it.
First, here is my new and approved forumulation:
$$\begin{bmatrix} X & G^T \G & I \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 important inequality is X \geq G^TG
for the other matrix, the important inequality is Z \leq X^{-1}
Second, here is my full code:
clc;
clear;
realizCnt = 6;
GColSize = 6;
G = randn(realizCnt);
cvx_begin sdp
variable t;
variable X(GColSize,GColSize) symmetric;
variable Z(GColSize,GColSize) symmetric;
minimize t;
subject to
trace(Z) <= t;
%using the formulation provided above, requires (-Z) to be positive
%definite. That is why the constraint "Z < 0" is included.
Z < 0;
[X G.'; G eye(realizCnt,realizCnt)] >= 0;
[-Z eye(GColSize,GColSize); eye(GColSize,GColSize) -X] >= 0;
cvx_end
Third, here is the cvx output:
Warning: The use of strict inequalities in CVX is strongly discouraged,
because solvers treat them as non-strict inequalities. Please
consider using "<=" instead.
> In < (line 21)
In working_setG (line 28)
Calling SDPT3 4.0: 177 variables, 42 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------
num. of constraints = 42
dim. of sdp var = 30, num. of sdp blk = 3
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version predcorr gam expon scale_data
HKM 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime
-------------------------------------------------------------------
0|0.000|0.000|1.8e+01|4.3e+00|6.5e+03| 1.440000e+02 0.000000e+00| 0:0:00| chol 1 1
1|0.895|0.636|1.9e+00|1.6e+00|2.0e+03|-3.386504e+02 5.185922e+01| 0:0:00| chol 1 1
2|0.176|0.063|1.6e+00|1.5e+00|2.3e+03|-6.373663e+03 9.409851e+01| 0:0:00| chol 1 1
3|0.026|0.051|1.6e+00|1.4e+00|2.6e+03|-4.351414e+04 2.249812e+02| 0:0:00| chol 1 1
4|0.002|0.012|1.6e+00|1.4e+00|4.0e+03|-3.617469e+05 9.311497e+02| 0:0:00| chol 1 1
5|0.000|0.004|1.6e+00|1.4e+00|1.2e+04|-3.340687e+06 9.710465e+03| 0:0:00| chol 1 2
6|0.000|0.000|1.6e+00|1.4e+00|2.1e+05|-2.992927e+07 2.159851e+05| 0:0:00| chol 1 2
7|0.000|0.000|1.6e+00|1.4e+00|4.9e+05|-2.689464e+08 4.946348e+05| 0:0:00| chol 2 3
8|0.000|0.000|1.6e+00|1.4e+00|6.2e+05|-1.456108e+09 5.133266e+05| 0:0:00| chol 2 3
9|0.000|0.000|1.6e+00|1.4e+00|1.7e+06|-1.154572e+10 6.379971e+05| 0:0:00| chol 2 2
10|0.000|0.000|1.6e+00|1.4e+00|2.3e+07|-1.042922e+11 1.634229e+07| 0:0:00| chol * 6 4
11|0.000|0.000|1.6e+00|1.4e+00|1.3e+08|-9.290948e+11 8.798847e+07| 0:0:00| chol * 7 5
12|0.000|0.000|1.6e+00|1.4e+00|6.7e+08|-8.378961e+12 3.443491e+08| 0:0:00| chol 16 24
13|0.000|0.000|1.6e+00|1.4e+00|3.4e+09|-7.475826e+13 4.541517e+08| 0:0:00| chol
linsysolve: Schur complement matrix not positive definite
switch to LU factor. lu 12 ^30
14|0.000|0.000|7.5e+00|1.4e+00|2.7e+10|-6.694427e+14 4.784014e+08| 0:0:00| lu 30 30
15|0.000|0.000|8.8e+01|1.4e+00|3.9e+10|-9.652753e+14 4.794818e+08| 0:0:00| lu 12 ^19
16|0.000|0.000|8.8e+01|1.4e+00|9.7e+10|-2.437440e+15 5.162110e+08| 0:0:00| lu 18 30
17|0.000|0.000|9.7e+01|1.4e+00|1.1e+11|-2.643172e+15 5.175818e+08| 0:0:00| lu 12 30
18|0.000|0.000|3.9e+02|1.4e+00|6.7e+11|-1.684342e+16 5.279503e+08| 0:0:00| lu 16 30
19|0.000|0.000|2.4e+03|1.4e+00|9.1e+11|-2.290545e+16 5.303933e+08| 0:0:00| lu 18 30
20|0.000|0.000|1.0e+03|1.4e+00|1.0e+12|-2.588398e+16 5.356804e+08| 0:0:00| lu 30 30
21|0.000|0.000|3.0e+03|1.4e+00|1.0e+12|-2.593847e+16 5.356922e+08| 0:0:00| lu 30 ^27
22|0.000|0.000|4.4e+03|1.4e+00|1.2e+12|-3.011167e+16 5.378849e+08| 0:0:00| lu 30 30
23|0.000|0.000|2.5e+03|1.4e+00|1.5e+12|-3.895537e+16 5.390667e+08| 0:0:00| lu 30 ^ 8
24|0.000|0.000|4.1e+03|1.4e+00|1.6e+12|-3.925793e+16 5.405627e+08| 0:0:00| lu 18 30
25|0.000|0.000|4.0e+03|1.4e+00|3.0e+12|-7.580696e+16 6.665801e+08| 0:0:01| lu 30 ^19
26|0.000|0.000|3.7e+03|1.4e+00|6.0e+12|-1.523793e+17 7.510272e+08| 0:0:01| lu 18 ^27
27|0.000|0.000|3.7e+03|1.4e+00|6.2e+12|-1.562586e+17 9.708123e+08| 0:0:01| lu 30 30
stop: X not positive definite
28|0.000|0.000|3.7e+03|1.4e+00|6.2e+12|-1.562586e+17 9.708123e+08| 0:0:01|
prim_inf,dual_inf,relgap = 3.67e+03, 1.39e+00, 3.97e-05
prim_inf,dual_inf,relgap = 3.67e+03, 1.39e+00, 3.97e-05
sqlp stop: dual problem is suspected of being infeasible
-------------------------------------------------------------------
number of iterations = 28
residual of dual infeasibility
certificate X = 1.51e-09
reldist to infeas. <= 1.08e-09
Total CPU time (secs) = 0.60
CPU time per iteration = 0.02
termination code = 2
DIMACS: 4.4e-02 0.0e+00 5.7e+00 0.0e+00 -1.0e+00 2.0e-04
-------------------------------------------------------------------
------------------------------------------------------------
Status: Infeasible
Optimal value (cvx_optval): +Inf
Please, any help is appreciated! I will be playing with cvx in the mean time. Either way, thanks for reading! : )
EDIT1: I have tried using sedumi as a solver, but only to get the same error. Sedumi actually crashes quicker than the default solver (SDPT3 it is called, I believe).
EDIT2: Apparently I got different results on a different computer! I will update the output above!!!
EDIT3: Wow, I think this formulation is not correct either! I think I now have the upper and lower bounds of X but have now lost the lower bound on Z. WOW! What an adventure. I will push onward.
Well, it looks like Johan Löfberg gave you a rather simple refutation of convexity on Math.SE. I think heâs right after all.
Yes sir! Thank you for all of this and your creation of CVX. I of course was (am) going to refer to the conclusions for future aid for other readers. Here is the link concluding the initial topic: http://math.stackexchange.com/questions/1555273/minimize-mathrmtrgtg-1/1555438#1555438
Now to see how to handle this non convex function⊠Any suggestions? : P Maybe slack variables? I will push forward, as always⊠no where else to push anyway.