>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> % A Lovasz theta function problem
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> %
>> n = 30; % number of vertices
>> dsty = 0.2; % edge density is 20%
>> thetarnd % random graph with random weights
>>
>> lsetpars % set useXZ = 1, tau = .99
>> scalefac = 1; % X0 = Z0 = I fine for random problems
>> validate = 1; % check connectivity
>> linitvars
>> lsdp % since useXZ = 1, special-purpose XZ code used
lsdp: using XZ method...
tau = 0.9900, scalefac = 1
iter p_step d_step p_infeas d_infeas X.Z pobj dobj
0 0.000e+00 0.000e+00 2.900e+01 1.821e+01 3.000e+01 -1.640e+01 0.000e+00
1 4.392e-02 5.159e-02 2.773e+01 1.727e+01 3.436e+01 -1.150e+02 -4.542e-01
2 1.491e-02 1.000e+00 2.731e+01 1.159e-14 3.992e+02 -1.076e+02 -1.790e+01
3 1.000e+00 1.000e+00 4.775e-15 5.700e-15 1.240e+01 -4.591e+00 -1.699e+01
4 1.000e+00 8.510e-01 2.260e-16 6.862e-15 1.719e+00 -5.909e+00 -7.627e+00
5 6.299e-01 1.000e+00 3.197e-16 2.152e-15 6.784e-01 -6.752e+00 -7.431e+00
6 7.758e-01 9.734e-01 3.486e-16 2.583e-15 1.905e-01 -7.115e+00 -7.305e+00
7 7.659e-01 1.000e+00 1.108e-15 3.490e-15 8.253e-02 -7.221e+00 -7.304e+00
8 9.001e-01 1.000e+00 3.232e-15 1.899e-15 1.723e-02 -7.284e+00 -7.302e+00
9 9.767e-01 9.953e-01 6.683e-16 1.890e-15 5.154e-04 -7.300e+00 -7.300e+00
10 9.880e-01 1.000e+00 3.142e-14 2.346e-15 1.962e-05 -7.300e+00 -7.300e+00
11 9.558e-01 1.000e+00 2.754e-14 2.140e-15 1.776e-06 -7.300e+00 -7.300e+00
12 9.368e-01 1.000e+00 4.841e-13 2.329e-15 1.117e-07 -7.300e+00 -7.300e+00
13 1.000e+00 1.000e+00 4.403e-13 2.901e-15 1.215e-08 -7.300e+00 -7.300e+00
Stop since new point is substantially worse than current iterate
X.Z = 3.672e-10
pri_infeas = 4.895e-12
dual_infeas = 2.557e-15
lsdp: elapsed time = 7.77212 seconds
lsdp: elapsed cpu time = 7.58000 seconds
lsdp: flops = 1.96740e+07
lsdp: Number of iterations = 13
lsdp: final value of X.Z = 1.215e-08
lsdp: final primal infeasibility = 4.403e-13
lsdp: final dual infeasibility = 2.901e-15
lsdp: primal objective value = -7.3004453174538488e+00
lsdp: dual objective value = -7.3004453295989862e+00
lsdp: Lovasz theta function value = 7.3004453235264180e+00
>> setpars % sets useXZ = 0, tau = .999
>> scalefac = 1; % X0 = Z0 = I fine for random problems
>> validate = 1; % check connectivity
>> linitvars
>> lsdp % since useXZ = 0, general-purpose code XZ+ZX used
lsdp: using XZ+ZX method...
tau = 0.9990, scalefac = 1
iter p_step d_step p_infeas d_infeas X.Z pobj dobj
0 0.000e+00 0.000e+00 2.900e+01 1.821e+01 3.000e+01 -1.640e+01 0.000e+00
1 4.432e-02 5.205e-02 2.771e+01 1.726e+01 3.434e+01 -1.159e+02 -4.580e-01
2 6.103e-02 1.000e+00 2.602e+01 8.154e-15 3.015e+02 -8.796e+01 -1.441e+01
3 1.000e+00 1.000e+00 1.059e-14 5.238e-15 9.234e+00 -4.455e+00 -1.369e+01
4 1.000e+00 8.729e-01 3.455e-15 5.401e-15 1.129e+00 -6.274e+00 -7.403e+00
5 8.498e-01 7.268e-01 2.676e-15 4.130e-15 2.300e-01 -7.079e+00 -7.309e+00
6 1.000e+00 1.000e+00 9.434e-14 4.110e-15 1.352e-01 -7.180e+00 -7.315e+00
7 9.833e-01 9.939e-01 1.582e-15 5.173e-15 2.124e-03 -7.298e+00 -7.300e+00
8 9.990e-01 9.990e-01 6.664e-16 4.506e-15 2.142e-06 -7.300e+00 -7.300e+00
9 9.990e-01 9.990e-01 5.556e-16 3.820e-15 2.142e-09 -7.300e+00 -7.300e+00
10 9.990e-01 9.990e-01 2.234e-16 3.210e-15 2.169e-12 -7.300e+00 -7.300e+00
fsdp: stop since error reduced to desired value
lsdp: elapsed time = 9.36495 seconds
lsdp: elapsed cpu time = 9.14000 seconds
lsdp: flops = 2.09046e+08
lsdp: Number of iterations = 10
lsdp: final value of X.Z = 2.169e-12
lsdp: final primal infeasibility = 2.234e-16
lsdp: final dual infeasibility = 3.210e-15
lsdp: primal objective value = -7.3004453290700102e+00
lsdp: dual objective value = -7.3004453290721765e+00
lsdp: Lovasz theta function value = 7.3004453290710938e+00
>>
>> % notice that specialized XZ method is faster
>> % but less accurate than XZ+ZX method
>>
>> % since useXZ = 0, A was formed; so we can now call primalcond
>> % and dualcond
>>
>> % for random weights, usually Lovasz SDP is primal degenerate
>> %
>> rank(X,1.0e-06) % for random weights, usually rank(X) is 1
ans =
1
>> rank(Z,1.0e-06) % for random weights, usually rank(Z) is n-1
ans =
29
>> primalcond(A,blk,X,1.0e-06); % usually primal degenerate
primalcond = Inf
>> dualcond(A,blk,Z,1.0e-06); % usually dual nondegenerate
dualcond = 1.000e+00
>> w = ones(size(w)); % change weights to all one >> lsetpars % set useXZ = 1, tau = .99 >> scalefac = 1; % X0 = Z0 = I fine for random problems >> prtlevel = 0; % turn off detailed output >> validate = 1; >> linitvars >> lsdp % since useXZ = 1, special-purpose XZ code used lsdp: using XZ method... tau = 0.9900, scalefac = 1 lsdp: elapsed time = 8.22000 seconds lsdp: elapsed cpu time = 8.08000 seconds lsdp: flops = 2.10767e+07 lsdp: Number of iterations = 15 lsdp: final value of X.Z = 3.563e-09 lsdp: final primal infeasibility = 3.244e-10 lsdp: final dual infeasibility = 4.295e-15 lsdp: primal objective value = -1.1999999995647892e+01 lsdp: dual objective value = -1.2000000000398519e+01 lsdp: Lovasz theta function value = 1.1999999998023206e+01
>> setpars % sets useXZ = 0, tau = .999
>> prtlevel = 0;
>> scalefac = 1; % X0 = Z0 = I fine for random problems
>> validate = 1; % check connectivity
>> linitvars
>> lsdp % since useXZ = 0, general-purpose XZ+ZX code used
lsdp: using XZ+ZX method...
tau = 0.9990, scalefac = 1
lsdp: elapsed time = 9.36421 seconds
lsdp: elapsed cpu time = 9.10000 seconds
lsdp: flops = 2.08908e+08
lsdp: Number of iterations = 10
lsdp: final value of X.Z = 7.552e-12
lsdp: final primal infeasibility = 2.508e-16
lsdp: final dual infeasibility = 6.900e-15
lsdp: primal objective value = -1.1999999999993703e+01
lsdp: dual objective value = -1.2000000000001263e+01
lsdp: Lovasz theta function value = 1.1999999999997483e+01
>>
>> % notice that specialized XZ method is faster but less
>> % accurate than XZ+ZX method
>>
>> % since useXZ = 0, the matrix A was formed, so we can now call
>> % primalcond and dualcond
>>
>> rank(X,1.0e-06) % for weights all one, usually rank(X) > 1
ans =
3
>> rank(Z,1.0e-06) % for weights all one, usually rank(Z) < n-1
ans =
27
>> primalcond(A,blk,X,1.0e-06); % sometimes primal nondegenerate
primalcond = 4.249e+17
>> dualcond(A,blk,Z,1.0e-06); % sometimes dual degenerate
dualcond = 5.881e+10