>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% >> % 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