Logdet optimimzation problems

[ArjunM21]

Hi Johan,

I am trying to solve a -logdet problem. I have written the code and used sedumi to solve it. I also tried using sdpt3 for the same. The issue is that the plot that is being plotted doesn't plot the actual lower and upper bounds. Please find the plot attached.

The relaxed problem solution should start from -2.13 and should converge at -1.4, but instead starts at -3.02 and converges at -2.65. Can you give me an explanation as to why this could be happening? Are there some approximations being made when solving logdet?

[johanlofberg]

When you use sedumi, the logdet expression is replaced with geomean as sedumi doesn't support logdet. When sdpt3 is used, logdet should be used. Hence, when using sedumi and sdpt3 I would expect different numbers

[johanlofberg]

So what solution did you show above. Was it the solution bnb returned, or the one you manually derived.

The lower bound of 0.62 simply isn't possible, you are mixing up something or showing the wrong code. Even with removing your margin on the LMI the relaxation yields 1.1777 as the lowest possible value

[ArjunM21]

Sorry for all the confusion. There was a small issue with the code. Please find the correct code attached below. Kindly note that in the line 44, Sigma_g = C'*Q*C.
The relaxed solution of this code is 17,499. The SDPT3 solver did not find a feasible solution upon convergence.

Kindly use the new code for analysis. Do you have any suggestion or advice? Thank you.

clear all;
close all;

%% System Inputs
C = [1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    1	1	-1	-1	0	0	1	1	1	1	1	0	0	0	0	0	0
    0	0	-1	-1	0	0	1	1	1	1	1	0	0	0	0	0	0
    0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
    0	0	-1	-1	1	1	0	0	0	0	0	0	0	0	0	0	0
    -1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    1	0	-1	0	0	0	1	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
    0	-1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
    0	0	0	0	1	0	0	-1	0	0	0	1	1	1	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
    0	0	0	0	1	0	0	-1	-1	0	0	1	1	1	1	1	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
    0	0	0	0	-1	0	1	1	1	1	0	-1	-1	-1	-1	-1	0
    0	0	0	0	0	0	0	0	0	0	0	1	0	0	1	0	1
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
    0	0	0	0	0	1	0	0	0	0	0	-1	-1	0	-1	0	-1];

sigmasq = 0.025*[0.86 1.00 111.82 109.95 53.27 112.27 2.32 164.05 0.86 52.41 14.86 67.27 111.27 91.86 60.00 23.64 32.73 16.23 7.95 10.50 87.27 5.45 2.59 46.64 85.45 81.32 70.77 72.23];


%% System Details
dof = size(C,2); % degree of freedom
nv = size(C,1); % no of variables
for j = 1:nv
    invsigma(j) = 1/sigmasq(j);
end
SIG = diag(invsigma); % Precision matrix

Sigma_g = (C'*SIG*C);

%% Optimization Formulation
x = binvar(nv,1);
Q = diag(SIG*x);
Y = sdpvar(dof,dof);

Objective2 = 0.5*(trace(Y*Sigma_g) - log(det(Y)) - log(det(Sigma_g)) - dof); % FKL 

Constraints = [];
Constraints = [Constraints, sum(x)==dof]; 
Constraints = [Constraints, [Y eye(dof);eye(dof) C'*Q*C] >= 0.1*eye(2*dof)];

ops = sdpsettings;
ops.savesolveroutput=1;
ops.bnb.maxtime = 1080000;
ops.bnb.inttol = 1e-3;
ops.bnb.feastol = 1e-3;
ops.bnb.gaptol = 1e-3;
ops.bnb.prunetol = 1e-3;
ops.bnb.plot = 1;

out = optimize(Constraints, Objective2, ops);

%% Results

Obj_val = double(value(Objective2));
Opt_soln = double(value(x));

[johanlofberg]

So what is the relation to the previous claim about sub-optimal solutions, and optimal solution being 5.6? The solution you listed above yields 31.56, and you previously talked about an objective of 5.6 but that is impossible as the lower bound here is 17.5

[ArjunM21]

Yes I understand that. That was a mistake from my side. Sorry for the confusion. Please only consider the code given in my last reply. Considering this code, do you have any advice for me?

[johanlofberg]

It just seems like that model has some structure which causes most variables to be far from integer, meaning there won't be many close to integer feasible solutions along the way, and the heuristics performs bad. For instance, by using a much smaller margin for the definiteness, the problem appears much easier and is solved almost instantly