next up previous contents
Next: A Lovász function Up: Examples Previous: A problem with

A diagonally constrained problem

This section illustrates the use of diagcstr.m and dsdp.m to generate and solve diagonally constrained problems.

>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> % A diagonally constrained problem
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> 
>> n = 50;        % n = m = 50
>> diagcstr       % random C and b, but A_k = e_k e_k^T
>> dsetpars       % set useXZ = 1, tau = .99
>> scalefac = 1;  % X0 = Z0 = I fine for random problems
>> dinitvars
>> dsdp           % since useXZ = 1, special-purpose XZ code used

dsdp: 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   4.135e+00   5.768e+01   5.000e+01   3.281e+00   0.000e+00
  1   1.337e-02   1.000e+00   4.080e+00   0.000e+00   1.686e+03  -1.597e+03  -1.606e+03
  2   7.917e-01   9.188e-01   8.497e-01   3.158e-14   3.500e+02  -1.077e+03  -1.075e+03
  3   7.632e-01   1.000e+00   2.012e-01   3.408e-14   1.894e+02  -9.608e+02  -1.059e+03
  4   7.614e-01   1.000e+00   4.801e-02   2.010e-14   5.199e+01  -1.028e+03  -1.058e+03
  5   1.000e+00   7.896e-01   1.464e-14   3.256e-14   1.472e+01  -1.041e+03  -1.056e+03
  6   7.997e-01   1.000e+00   1.042e-14   0.000e+00   3.150e+00  -1.053e+03  -1.056e+03
  7   1.000e+00   5.721e-01   2.092e-13   2.010e-14   1.213e+00  -1.055e+03  -1.056e+03
  8   7.319e-01   1.000e+00   8.455e-14   1.421e-14   3.547e-01  -1.056e+03  -1.056e+03
  9   1.000e+00   5.730e-01   2.643e-13   0.000e+00   1.381e-01  -1.056e+03  -1.056e+03
 10   9.643e-01   1.000e+00   1.827e-12   1.421e-14   3.300e-02  -1.056e+03  -1.056e+03
 11   9.812e-01   1.000e+00   1.197e-13   3.553e-15   1.627e-03  -1.056e+03  -1.056e+03
 12   9.440e-01   1.000e+00   2.579e-13   1.465e-14   9.273e-05  -1.056e+03  -1.056e+03
 13   9.164e-01   1.000e+00   3.404e-12   1.421e-14   8.667e-06  -1.056e+03  -1.056e+03
 14   1.000e+00   1.000e+00   1.344e-11   3.553e-15   2.334e-07  -1.056e+03  -1.056e+03
 15   5.189e-01   3.699e-01   1.046e-10   0.000e+00   1.206e-07  -1.056e+03  -1.056e+03
 16   1.554e-07   1.434e-05   1.039e-10   1.465e-14   1.202e-07  -1.056e+03  -1.056e+03
fdsdp: stop since steps are too short

dsdp: elapsed time               =   3.32932 seconds
dsdp: elapsed cpu time           =   3.19000 seconds
dsdp: flops                      =   7.31872e+07
dsdp: Number of iterations       =   16
dsdp: final value of X.Z         =   1.202e-07
dsdp: final primal infeasibility =   1.039e-10
dsdp: final dual infeasibility   =   1.465e-14
dsdp: primal objective value     =  -1.0559774619074481e+03
dsdp: dual objective value       =  -1.0559774620433770e+03

>> setpars        % sets useXZ = 0, tau = .999
>> scalefac = 1;  % X0 = Z0 = I fine for random problems
>> dinitvars
>> dsdp           % since useXZ = 0, general-purpose XZ+ZX code used

dsdp: 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   4.135e+00   5.768e+01   5.000e+01   3.281e+00   0.000e+00
  1   1.349e-02   1.000e+00   4.079e+00   0.000e+00   1.671e+03  -1.611e+03  -1.606e+03
  2   6.448e-01   1.000e+00   1.449e+00   3.843e-14   5.957e+02  -1.109e+03  -1.122e+03
  3   8.000e-01   9.591e-01   2.898e-01   1.628e-14   1.410e+02  -1.040e+03  -1.059e+03
  4   8.515e-01   8.056e-01   4.305e-02   2.010e-14   7.150e+01  -1.004e+03  -1.056e+03
  5   1.000e+00   1.000e+00   1.696e-12   2.842e-14   2.556e+01  -1.031e+03  -1.056e+03
  6   9.985e-01   1.000e+00   2.903e-15   1.421e-14   3.886e-02  -1.056e+03  -1.056e+03
  7   9.990e-01   9.990e-01   3.981e-15   1.465e-14   3.886e-05  -1.056e+03  -1.056e+03
  8   9.990e-01   9.990e-01   7.745e-16   3.553e-15   3.886e-08  -1.056e+03  -1.056e+03
  9   9.989e-01   9.990e-01   7.946e-16   3.553e-15   4.200e-11  -1.056e+03  -1.056e+03
fsdp: stop since limiting accuracy reached (smallest eigenvalue of Z =  -5.453e-14)

dsdp: elapsed time               =  22.59205 seconds
dsdp: elapsed cpu time           =  13.13000 seconds
dsdp: flops                      =   5.35133e+08
dsdp: Number of iterations       =    9
dsdp: final value of X.Z         =   4.200e-11
dsdp: final primal infeasibility =   7.946e-16
dsdp: final dual infeasibility   =   3.553e-15
dsdp: primal objective value     =  -1.0559774620403921e+03
dsdp: dual objective value       =  -1.0559774620404330e+03
>> 
>> % notice that specialized XZ method is faster but less 
>> % accurate than XZ+ZX method



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