next up previous contents
Next: A sample truss Up: Examples Previous: A diagonally constrained

A Lovász function problem

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



Madhu Nayakkankuppam
Fri Mar 28 00:48:56 EST 1997