This appendix illustrates the use of the main routines in SDPpack by
a sample Matlab session. In the examples below, >> denotes the
Matlab prompt. Matlab was invoked from the
sdppack directory.
>> warning off % eliminate ill conditioning warnings
>>
>> setpath % set the path
>>
>> format short e
>>
>> clear all
>>
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> % Examples of setting up a problem using makeA
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>>
>> blk.s = [3 3]; % two semidefinite blocks of size 3 each
>> m = 2; % two primal constraints
>> Amat{1} = speye(6); % sparse identity matrix
>> Amat{2}(1:3,1:3) = sparse([1 2 3; 2 4 5; 3 5 6]);
>> Amat{2}(4:6,4:6) = sparse([1 0 0; 0 2 2; 0 2 3]);
>> A.s = makeA(Amat, blk.s); % make the 2 x 12 matrix A.s
>> C.s(1:3,1:3) = sparse(ones(3,3));
>> C.s(4:6,4:6) = sparse(zeros(3,3));
>> b = [1 2]';
>> setopt; % set the options
>> init;
>> sql;
tau = 0.9990, scalefac = 100
iter p_step d_step p_infeas d_infeas X . Z pobj dobj
0 0.000e+00 0.000e+00 1.801e+03 2.437e+02 6.000e+04 3.000e+02 0.000e+00
1 1.000e+00 1.000e+00 7.183e-02 2.220e-16 1.020e+02 3.349e-01 -9.934e+01
2 1.000e+00 9.916e-01 1.337e-15 2.320e-14 8.935e-01 3.155e-01 -5.781e-01
3 6.685e-01 1.000e+00 2.701e-15 3.928e-16 2.178e-01 1.279e-02 -2.050e-01
4 9.699e-01 9.827e-01 3.140e-16 2.629e-16 4.009e-03 7.435e-05 -3.935e-03
5 1.000e+00 9.992e-01 1.554e-15 1.734e-16 6.112e-06 3.387e-07 -5.773e-06
6 9.990e-01 9.990e-01 8.882e-16 2.923e-16 6.112e-09 3.387e-10 -5.773e-09
7 9.990e-01 9.990e-01 2.220e-16 3.351e-16 6.112e-12 3.386e-13 -5.773e-12
fsql: stop since error reduced to desired value
sql: elapsed time = 0.971 seconds
sql: elapsed cpu time = 0.300 seconds
sql: number of iterations = 7
sql: final value of X . Z = 6.112e-12
sql: final primal infeasibility = 2.220e-16
sql: final dual infeasibility = 3.351e-16
sql: primal objective value = 3.3864577808628837e-13
sql: dual objective value = -5.7731216096433383e-12
>> full(X.s) % display solution as full matrix
ans =
9.7585e-02 -5.2413e-02 -4.5172e-02 0 0 0
-5.2413e-02 1.1485e-01 -6.2439e-02 0 0 0
-4.5172e-02 -6.2439e-02 1.0761e-01 0 0 0
0 0 0 1.5025e-01 0 0
0 0 0 0 2.3968e-01 1.0069e-01
0 0 0 0 1.0069e-01 2.9002e-01
>> full(Z.s) % display solution as full matrix
ans =
1.0000e+00 1.0000e+00 1.0000e+00 0 0 0
1.0000e+00 1.0000e+00 1.0000e+00 0 0 0
1.0000e+00 1.0000e+00 1.0000e+00 0 0 0
0 0 0 4.6022e-12 0 0
0 0 0 0 5.7731e-12 2.3418e-12
0 0 0 0 2.3418e-12 6.9440e-12
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> % Add a quadratic block to this problem
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> blk.q = 3;
>> A.q = [1 2 3; 4 5 6];
>> C.q = [1 -1 -1]';
>> init;
>> sql;
tau = 0.9990, scalefac = 100
iter p_step d_step p_infeas d_infeas X . Z pobj dobj
0 0.000e+00 0.000e+00 2.211e+03 3.427e+02 7.000e+04 4.000e+02 0.000e+00
1 1.000e+00 5.838e-01 1.271e-13 1.426e+02 2.041e+04 4.047e+02 -1.802e+01
2 1.000e+00 9.527e-01 2.970e-11 6.746e+00 1.296e+03 3.857e+02 -1.707e+00
3 1.000e+00 1.000e+00 1.748e-09 7.581e-16 2.743e+02 2.734e+02 -9.276e-01
4 9.953e-01 1.000e+00 8.258e-12 2.544e-16 1.279e+00 3.522e-01 -9.264e-01
5 1.000e+00 9.029e-01 1.512e-15 9.572e-16 2.875e-01 6.095e-02 -2.266e-01
6 1.000e+00 6.339e-01 2.614e-14 2.435e-16 6.941e-02 -5.025e-02 -1.197e-01
7 4.536e-01 4.488e-01 3.991e-13 4.347e-16 5.265e-02 -1.841e-02 -7.106e-02
8 9.470e-01 1.000e+00 2.162e-14 3.220e-16 2.873e-03 -6.976e-02 -7.264e-02
9 9.990e-01 9.988e-01 1.510e-15 4.280e-16 3.227e-06 -7.053e-02 -7.053e-02
10 9.990e-01 9.990e-01 9.155e-16 2.922e-16 3.227e-09 -7.053e-02 -7.053e-02
11 9.990e-01 9.990e-01 8.006e-16 3.907e-16 3.228e-12 -7.053e-02 -7.053e-02
fsql: stop since error reduced to desired value
sql: elapsed time = 0.679 seconds
sql: elapsed cpu time = 0.390 seconds
sql: number of iterations = 11
sql: final value of X . Z = 3.228e-12
sql: final primal infeasibility = 8.006e-16
sql: final dual infeasibility = 3.907e-16
sql: primal objective value = -7.0528980380840739e-02
sql: dual objective value = -7.0528980384069004e-02
>> [X.q Z.q] % quadratic part of solution
ans =
1.7078e-01 1.1404e+00
1.2339e-01 -8.2400e-01
1.1806e-01 -7.8841e-01
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> % Example of a randomly generated problem
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>>
>> blk.s = [50 5 5 5 5 20]; % semidefinite blocks
>> blk.q = [50 100 150]; % quadratic blocks
>> blk.l = 100; % linear block
>> m = 100;
>> sqlrnd % generate random feasible problem
>> setopt % set default options
>> init % initialize variables (infeasible)
>> sql % solve problem
tau = 0.9990, scalefac = 100
iter p_step d_step p_infeas d_infeas X . Z pobj dobj
0 0.000e+00 0.000e+00 5.044e+04 2.099e+03 1.930e+06 3.963e+04 0.000e+00
1 1.000e+00 6.436e-01 3.510e-11 7.481e+02 5.628e+05 1.025e+04 -1.348e+03
2 1.000e+00 9.355e-01 3.058e-09 4.822e+01 4.299e+04 8.355e+03 2.328e+01
3 1.000e+00 9.410e-01 1.069e-08 2.844e+00 7.400e+03 5.799e+03 1.156e+02
4 7.786e-01 4.205e-01 2.382e-09 1.648e+00 1.956e+03 1.719e+03 1.190e+02
5 1.000e+00 1.000e+00 3.818e-08 1.221e-13 3.625e+02 4.880e+02 1.256e+02
6 7.567e-01 1.000e+00 9.289e-09 1.289e-13 8.980e+01 2.174e+02 1.276e+02
7 7.252e-01 7.134e-01 2.553e-09 1.205e-13 4.403e+01 1.849e+02 1.409e+02
8 8.715e-01 9.749e-01 3.308e-10 1.288e-13 1.853e+01 1.635e+02 1.449e+02
9 9.287e-01 9.833e-01 2.486e-11 1.252e-13 3.447e+00 1.491e+02 1.457e+02
10 9.789e-01 9.678e-01 2.278e-11 1.237e-13 4.773e-01 1.464e+02 1.459e+02
11 1.000e+00 1.000e+00 1.116e-11 1.248e-13 8.423e-02 1.460e+02 1.459e+02
12 9.474e-01 9.573e-01 3.018e-12 1.213e-13 4.430e-03 1.459e+02 1.459e+02
13 1.000e+00 1.000e+00 1.210e-10 1.288e-13 4.988e-04 1.459e+02 1.459e+02
14 9.980e-01 9.980e-01 1.016e-11 1.289e-13 1.021e-06 1.459e+02 1.459e+02
15 9.990e-01 9.990e-01 2.651e-11 1.292e-13 1.021e-09 1.459e+02 1.459e+02
16 9.989e-01 9.989e-01 3.060e-11 1.315e-13 1.118e-12 1.459e+02 1.459e+02
fsql: stop since error reduced to desired value
sql: elapsed time = 147.092 seconds
sql: elapsed cpu time = 113.480 seconds
sql: number of iterations = 16
sql: final value of X . Z = 1.118e-12
sql: final primal infeasibility = 3.060e-11
sql: final dual infeasibility = 1.315e-13
sql: primal objective value = 1.4592215412906933e+02
sql: dual objective value = 1.4592215412906256e+02
>>
>> % note the successive reductions of X . Z by factors
>> % of 1000 in final iterations (this is because tau = 0.999)
>>
>> pcond(A,blk,X,1.0e-06); % confirms that primal nondegenerate
primal condition number = 3.8717e+00
>> % (as expected since randomly generated)
>>
>> dcond(A,blk,Z,1.0e-06); % confirms that dual nondegenerate
dual condition number = 5.693e+00
>> % (as expected since randomly generated)
>>
>>
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> % Example from AHO paper where no strictly
>> % complementary solution exists
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>>
>> clear blk
>> C.s = [0 0 0; 0 0 0; 0 0 1];
>> AA{1} = [1 0 0; 0 0 0; 0 0 0];
>> AA{2} = [0 0 1; 0 1 0; 1 0 0];
>> AA{3} = [0 1 0; 1 0 0; 0 0 1];
>> b = [1 0 0]';
>> blk.s = 3;
>> m = 3;
>> A.s = makeA(AA,blk.s);
>>
>> init
>> sql
tau = 0.9990, scalefac = 100
iter p_step d_step p_infeas d_infeas X . Z pobj dobj
0 0.000e+00 0.000e+00 1.726e+02 1.726e+02 3.000e+04 1.000e+02 0.000e+00
1 8.615e-01 1.000e+00 2.392e+01 0.000e+00 2.842e+03 5.815e+01 -1.201e+02
2 9.837e-01 1.000e+00 3.887e-01 0.000e+00 1.521e+02 3.536e+00 -1.090e+02
3 1.000e+00 1.000e+00 4.965e-16 4.885e-15 9.861e+00 2.574e+00 -7.288e+00
4 1.000e+00 7.694e-01 1.295e-15 1.249e-15 2.285e+00 1.946e+00 -3.382e-01
5 8.536e-01 1.000e+00 8.311e-14 9.714e-17 3.873e-01 5.488e-02 -3.324e-01
6 2.734e-01 9.545e-01 6.046e-14 5.551e-17 5.702e-02 4.038e-02 -1.664e-02
7 1.000e+00 1.000e+00 1.117e-14 4.510e-17 9.225e-03 4.605e-03 -4.620e-03
8 9.296e-01 9.296e-01 9.447e-16 1.003e-16 1.538e-03 7.681e-04 -7.700e-04
9 1.000e+00 1.000e+00 1.221e-13 2.730e-17 1.144e-03 5.718e-04 -5.719e-04
10 9.439e-01 9.439e-01 6.217e-15 1.730e-18 6.536e-05 3.268e-05 -3.268e-05
11 1.000e+00 1.000e+00 1.999e-15 6.325e-17 3.232e-05 1.616e-05 -1.616e-05
12 9.271e-01 9.271e-01 1.735e-18 1.038e-16 2.431e-06 1.216e-06 -1.216e-06
13 1.000e+00 1.000e+00 2.221e-15 1.563e-17 1.350e-06 6.748e-07 -6.748e-07
14 9.327e-01 9.327e-01 4.441e-16 2.036e-18 9.324e-08 4.662e-08 -4.662e-08
15 1.000e+00 1.000e+00 1.110e-15 3.456e-18 5.000e-08 2.500e-08 -2.500e-08
fsql: stop since new point is substantially worse than current iterate
X . Z = 3.541e-09
pri_infeas = 4.441e-16
dual_infeas = 9.704e-17
sql: elapsed time = 0.272 seconds
sql: elapsed cpu time = 0.270 seconds
sql: number of iterations = 15
sql: final value of X . Z = 5.000e-08
sql: final primal infeasibility = 1.110e-15
sql: final dual infeasibility = 3.456e-18
sql: primal objective value = 2.5001652697068844e-08
sql: dual objective value = -2.5001652697556712e-08
>>
>> [blkeig(X.s,blk.s,-1) blkeig(Z.s,blk.s,1)]
ans =
1.0000e+00 1.5014e-08
1.9987e-04 9.9936e-05
1.5014e-08 1.0000e+00
>>
>> % note that convergence is much slower than usual,
>> % and that solution is much less accurate than usual.
>>
>> % confirm that solution is primal NONdegenerate
>> % (large tolerance since not strictly complementary)
>> pcond(A,blk,X,1.0e-3);
primal condition number = 1.0001e+00
>> % confirm that solution is dual NONdegenerate
>> dcond(A,blk,Z,1.0e-3);
dual condition number = 1.414e+00
>> % condition number is infinite, since SC failed
>> sqlcond(A,b,C,blk,X,y,Z);
sqlcond: comp = 5.000e-08
sqlcond: primal infeasibility = 1.110e-15
sqlcond: dual infeasibility = 3.456e-18
sqlcond: cond estimate of 3x3 block matrix = 4.124e+04
>>
>>
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> % Examples of degenerate problems
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>>
>> clear blk
>> blk.s = 10;
>> m = 50; % m chosen to ensure primal degeneracy
>> rx.s = 2; % choose primal solution rank and
>> rz.s = 7; % dual solution rank in advance
>> makesql % generated so solution is primal degenerate
makesql: strict complementarity violated for the SD part
>>
>> init
>> opt.prtlevel = 0;
>> sql
tau = 0.9990, scalefac = 100
sql: elapsed time = 0.460 seconds
sql: elapsed cpu time = 0.460 seconds
sql: number of iterations = 6
sql: final value of X . Z = 2.723e-10
sql: final primal infeasibility = 1.853e-12
sql: final dual infeasibility = 2.084e-13
sql: primal objective value = 2.8543802322637415e+00
sql: dual objective value = 2.8543802321029546e+00
>>
>> [blkeig(X.s,blk.s,-1) blkeig(Z.s,blk.s,1)] % sorted eigenvalues
ans =
1.0687e+00 4.8157e-11
6.4574e-01 1.3909e-10
2.8679e-13 7.6364e+01
2.0865e-13 8.0091e+01
1.7295e-13 8.4225e+01
1.5601e-13 9.1698e+01
1.0169e-13 1.0549e+02
9.2401e-14 1.1717e+02
6.1256e-14 1.2753e+02
4.5897e-14 1.8355e+02
>>
>> % note that convergence took place to a strictly complementary solution
>>
>> pcond(A,blk,X,1.0e-06); % confirms that solution is primal degenerate
primal condition number = Inf
>>
>> dcond(A,blk,Z,1.0e-06); % check if dual degenerate
dual condition number = 1.374e+00
>>
>> sqlcond(A,b,C,blk,X,y,Z); % confirms that SQL condition number is infinite,
sqlcond: comp = 2.723e-10
sqlcond: primal infeasibility = 1.853e-12
sqlcond: dual infeasibility = 2.084e-13
sqlcond: cond estimate of 3x3 block matrix = 1.017e+19
>> % since SQLP is degenerate
>>
>> clear blk
>> blk.s = [5 5 7]; % a bigger problem chosen so that strict
>> blk.q = [10 20 30]; % complementarity does not hold
>> blk.l = 30;
>> rx.s = [2 3 4];
>> rx.q = [0 1 2];
>> rx.l = 20;
>> rz.s = [2 2 3];
>> rz.q = [1 1 0];
>> rz.l = 5;
>> m = 100;
>> makesql;
makesql: strict complementarity violated for the SD part
makesql: strict complementarity violated for the QC part
makesql: strict complementarity violated for the LP part
>> init;
>> sql;
tau = 0.9990, scalefac = 100
sql: elapsed time = 12.593 seconds
sql: elapsed cpu time = 7.940 seconds
sql: number of iterations = 18
sql: final value of X . Z = 1.575e-06
sql: final primal infeasibility = 5.345e-10
sql: final dual infeasibility = 3.706e-14
sql: primal objective value = 5.8737338167855953e+01
sql: dual objective value = 5.8737336592772962e+01
>> % even the solution of the linear part is not strictly
>> [X.l Z.l] % complementary
ans =
1.1058e+00 2.8480e-08
1.0227e+00 3.0825e-08
1.9006e+00 1.6573e-08
1.5969e+00 1.9720e-08
1.8186e+00 1.7318e-08
1.6924e+00 1.8608e-08
1.0905e+00 2.8872e-08
1.4904e+00 2.1140e-08
1.8018e+00 1.7481e-08
1.5935e+00 1.9767e-08
1.1138e+00 2.8249e-08
1.4436e+00 2.1809e-08
1.9663e+00 1.6016e-08
1.4636e+00 2.1523e-08
1.4495e+00 2.1735e-08
1.8269e+00 1.7240e-08
1.2986e+00 2.4245e-08
1.7099e+00 1.8415e-08
1.6780e+00 1.8766e-08
1.2583e+00 2.5036e-08
4.3929e-04 1.0943e-04
4.7011e-04 1.0190e-04
4.2388e-04 1.1309e-04
2.3974e-04 1.9792e-04
3.1820e-04 1.5071e-04
2.7166e-08 1.1595e+00
1.7050e-08 1.8479e+00
1.9730e-08 1.5970e+00
1.6520e-08 1.9068e+00
1.9520e-08 1.6144e+00
>>
>>
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> % A diagonally constrained SDP
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>>
>> n = 50; % n = m = 50
>> drnd % random C and b, but A_k = e_k e_k^T
>> dsetopt % set useXZ = 1, tau = .99
>> scalefac = 1; % X0 = Z0 = I fine for random problems
>> dinit
>> 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.313e+00 2.964e+01 5.000e+01 4.187e+00 0.000e+00
1 5.346e-02 1.000e+00 4.083e+00 6.880e-15 7.776e+02 -4.254e+01 -3.767e+02
2 9.345e-01 8.959e-01 2.672e-01 7.692e-15 1.110e+02 -7.191e+01 -1.632e+02
3 4.907e-01 1.000e+00 1.361e-01 4.615e-15 5.926e+01 -1.020e+02 -1.519e+02
4 9.152e-01 1.000e+00 1.154e-02 4.529e-15 9.287e+00 -1.363e+02 -1.448e+02
5 9.631e-01 9.604e-01 4.264e-04 2.220e-15 4.821e-01 -1.427e+02 -1.431e+02
6 9.646e-01 9.555e-01 1.507e-05 1.884e-15 3.960e-02 -1.430e+02 -1.431e+02
7 9.151e-01 1.000e+00 1.279e-06 1.601e-15 3.484e-03 -1.431e+02 -1.431e+02
8 8.620e-01 1.000e+00 1.766e-07 2.738e-15 7.022e-04 -1.431e+02 -1.431e+02
9 9.724e-01 1.000e+00 4.884e-09 2.391e-15 3.878e-05 -1.431e+02 -1.431e+02
10 9.501e-01 9.894e-01 6.289e-10 1.332e-15 2.054e-06 -1.431e+02 -1.431e+02
Stop since new point is substantially worse than current iterate
X . Z = 2.569e-07
pri_infeas = 2.708e-08
dual_infeas = 2.878e-15
dsdp: elapsed time = 5.556 seconds
dsdp: elapsed cpu time = 3.080 seconds
dsdp: number of iterations = 10
dsdp: final value of X . Z = 2.054e-06
dsdp: final primal infeasibility = 6.289e-10
dsdp: final dual infeasibility = 1.332e-15
dsdp: primal objective value = -1.4306128549766009e+02
dsdp: dual objective value = -1.4306128752873551e+02
>>
>> setopt % sets useXZ = 0, tau = .999
>> dinit
>> dsdp % since useXZ = 0, general-purpose XZ+ZX code used
dsdp: using XZ+ZX method...
tau = 0.9990, scalefac = 100
iter p_step d_step p_infeas d_infeas X . Z pobj dobj
0 0.000e+00 0.000e+00 7.040e+02 7.071e+02 5.000e+05 4.187e+02 0.000e+00
1 9.981e-01 1.000e+00 1.307e+00 0.000e+00 3.115e+03 -8.649e+00 -2.207e+03
2 9.933e-01 9.944e-01 8.804e-03 3.231e-14 1.965e+02 -1.401e+01 -2.093e+02
3 4.877e-01 1.000e+00 4.511e-03 1.025e-14 1.101e+02 -7.106e+01 -1.806e+02
4 9.685e-01 1.000e+00 1.423e-04 1.502e-14 3.892e+01 -1.258e+02 -1.647e+02
5 7.764e-01 8.993e-01 3.181e-05 1.693e-14 6.357e+00 -1.379e+02 -1.443e+02
6 1.000e+00 1.000e+00 1.265e-14 3.716e-15 1.619e+00 -1.416e+02 -1.432e+02
7 9.110e-01 9.678e-01 2.576e-15 2.083e-15 1.482e-01 -1.429e+02 -1.431e+02
8 1.000e+00 1.000e+00 2.718e-13 3.233e-15 5.226e-02 -1.430e+02 -1.431e+02
9 9.987e-01 9.987e-01 3.088e-15 3.580e-15 6.569e-05 -1.431e+02 -1.431e+02
10 9.990e-01 9.990e-01 1.170e-14 1.831e-15 6.569e-08 -1.431e+02 -1.431e+02
11 9.990e-01 9.990e-01 1.175e-14 2.512e-15 6.612e-11 -1.431e+02 -1.431e+02
fsql: stop since error reduced to desired value
dsdp: elapsed time = 16.932 seconds
dsdp: elapsed cpu time = 15.000 seconds
dsdp: number of iterations = 11
dsdp: final value of X . Z = 6.612e-11
dsdp: final primal infeasibility = 1.175e-14
dsdp: final dual infeasibility = 2.512e-15
dsdp: primal objective value = -1.4306128745773665e+02
dsdp: dual objective value = -1.4306128745780248e+02
>>
>> % notice that specialized XZ method is faster but less
>> % accurate than XZ+ZX method
>>
>>
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> % A Lovasz problem
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> %
>> n = 30; % number of vertices
>> dsty = 0.2; % edge density is 20%
>> lrnd % random graph with random weights
>>
>> lsetopt % set useXZ = 1, tau = .99
>> scalefac = 1; % X0 = Z0 = I fine for random problems
>> opt.validate = 1; % check connectivity
>> linit
>> 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.617e+01 3.000e+01 -1.424e+01 0.000e+00
1 5.544e-02 7.601e-02 2.739e+01 1.494e+01 3.420e+01 -9.122e+01 -5.246e-01
2 2.382e-02 1.000e+00 2.674e+01 8.168e-15 2.980e+02 -8.604e+01 -1.384e+01
3 9.867e-01 1.000e+00 3.548e-01 2.516e-15 1.276e+01 -5.056e+00 -1.315e+01
4 9.788e-01 8.449e-01 7.535e-03 4.503e-15 1.862e+00 -4.861e+00 -6.673e+00
5 2.080e-01 6.145e-01 5.968e-03 2.924e-15 1.565e+00 -4.994e+00 -6.521e+00
6 4.847e-02 7.077e-01 5.678e-03 1.201e-15 1.434e+00 -5.024e+00 -6.421e+00
7 5.645e-02 3.238e-01 5.358e-03 3.013e-15 1.337e+00 -5.044e+00 -6.347e+00
8 1.674e-02 7.984e-02 5.268e-03 1.868e-15 1.293e+00 -5.041e+00 -6.302e+00
9 6.391e-02 5.669e-01 4.932e-03 1.996e-15 1.237e+00 -5.073e+00 -6.279e+00
10 9.836e-03 6.618e-02 4.883e-03 2.670e-15 1.198e+00 -5.070e+00 -6.238e+00
11 4.878e-02 8.159e-01 4.645e-03 2.802e-15 1.224e+00 -5.094e+00 -6.289e+00
12 1.757e-02 2.141e-01 4.563e-03 2.521e-15 1.159e+00 -5.095e+00 -6.225e+00
13 2.718e-01 1.000e+00 3.323e-03 2.609e-15 1.034e+00 -5.245e+00 -6.258e+00
14 1.000e+00 1.000e+00 4.589e-16 2.286e-15 3.246e-01 -5.835e+00 -6.160e+00
15 9.318e-01 7.887e-01 4.712e-16 2.619e-15 3.868e-02 -6.053e+00 -6.091e+00
16 7.006e-01 1.000e+00 5.176e-15 2.532e-15 1.423e-02 -6.078e+00 -6.092e+00
17 9.823e-01 9.886e-01 3.423e-16 2.084e-15 3.803e-04 -6.089e+00 -6.089e+00
18 9.881e-01 9.920e-01 1.443e-15 3.047e-15 4.407e-06 -6.089e+00 -6.089e+00
Stop since new point is substantially worse than current iterate
X . Z = 8.274e-08
pri_infeas = 4.519e-14
dual_infeas = 2.341e-15
lsdp: elapsed time = 14.388 seconds
lsdp: elapsed cpu time = 7.270 seconds
lsdp: number of iterations = 18
lsdp: final value of X . Z = 4.407e-06
lsdp: final primal infeasibility = 1.443e-15
lsdp: final dual infeasibility = 3.047e-15
lsdp: primal objective value = -6.0894182157068650e+00
lsdp: dual objective value = -6.0894226229375326e+00
lsdp: Lovasz theta function value = 6.0894204193221988e+00
>>
>> setopt % sets useXZ = 0, tau = .999
>> linit
>> lsdp % since useXZ = 0, general-purpose code XZ+ZX used
lsdp: using XZ+ZX method...
tau = 0.9990, scalefac = 100
iter p_step d_step p_infeas d_infeas X . Z pobj dobj
0 0.000e+00 0.000e+00 2.999e+03 5.505e+02 3.000e+05 -1.424e+03 0.000e+00
1 9.976e-01 1.000e+00 7.055e+00 4.041e-16 7.914e+02 -1.781e+01 -1.005e+02
2 1.000e+00 1.000e+00 1.003e-15 8.658e-16 7.540e+01 -2.330e+00 -7.773e+01
3 1.000e+00 9.348e-01 2.322e-16 2.228e-14 4.923e+00 -2.646e+00 -7.568e+00
4 7.859e-01 9.626e-01 6.440e-16 4.593e-15 1.175e+00 -5.323e+00 -6.499e+00
5 1.000e+00 1.000e+00 5.525e-15 3.058e-15 3.543e-01 -5.832e+00 -6.187e+00
6 8.798e-01 8.434e-01 8.686e-16 3.681e-15 5.603e-02 -6.036e+00 -6.092e+00
7 1.000e+00 1.000e+00 6.409e-15 3.610e-15 5.198e-03 -6.084e+00 -6.090e+00
8 9.980e-01 9.984e-01 8.893e-16 3.470e-15 1.023e-05 -6.089e+00 -6.089e+00
9 9.990e-01 9.990e-01 1.905e-17 4.081e-15 1.023e-08 -6.089e+00 -6.089e+00
10 9.990e-01 9.990e-01 2.126e-17 3.592e-15 1.024e-11 -6.089e+00 -6.089e+00
fsql: stop since error reduced to desired value
lsdp: elapsed time = 8.923 seconds
lsdp: elapsed cpu time = 6.890 seconds
lsdp: number of iterations = 10
lsdp: final value of X . Z = 1.024e-11
lsdp: final primal infeasibility = 2.126e-17
lsdp: final dual infeasibility = 3.592e-15
lsdp: primal objective value = -6.0894223218290779e+00
lsdp: dual objective value = -6.0894223218393178e+00
lsdp: Lovasz theta function value = 6.0894223218341974e+00
>>
>> % notice that specialized XZ method is faster
>> % but less accurate than XZ+ZX method
>>
>> % since useXZ = 0, A.s was formed; so we can now call pcond
>> % and dcond
>>
>> % for random weights, usually Lovasz SDP is degenerate
>> %
>> rank(X.s,1.0e-06) % for random weights, usually rank(X.s) is 1
ans =
1
>> rank(Z.s,1.0e-06) % for random weights, usually rank(Z.s) is n-1
ans =
29
>> pcond(A,blk,X,1.0e-06); % usually primal degenerate
primal condition number = Inf
>> dcond(A,blk,Z,1.0e-06); % usually dual nondegenerate
dual condition number = 1.000e+00
>>
>> w = ones(size(w)); % change weights to all one
>> lsetopt % set useXZ = 1, tau = .99
>> opt.prtlevel = 0; % turn off detailed output
>> opt.validate = 1;
>> linit
>> lsdp % since useXZ = 1, special-purpose XZ code used
lsdp: using XZ method...
tau = 0.9900, scalefac = 100
lsdp: elapsed time = 7.271 seconds
lsdp: elapsed cpu time = 4.890 seconds
lsdp: number of iterations = 12
lsdp: final value of X . Z = 1.481e-06
lsdp: final primal infeasibility = 4.993e-09
lsdp: final dual infeasibility = 4.188e-15
lsdp: primal objective value = -1.2059530468726049e+01
lsdp: dual objective value = -1.2059532001323507e+01
lsdp: Lovasz theta function value = 1.2059531235024778e+01
>>
>> setopt % sets useXZ = 0, tau = .999
>> opt.prtlevel = 0;
>> linit
>> lsdp % since useXZ = 0, general-purpose XZ+ZX code used
lsdp: using XZ+ZX method...
tau = 0.9990, scalefac = 100
lsdp: elapsed time = 8.710 seconds
lsdp: elapsed cpu time = 7.740 seconds
lsdp: number of iterations = 12
lsdp: final value of X . Z = 6.871e-10
lsdp: final primal infeasibility = 9.010e-14
lsdp: final dual infeasibility = 6.881e-15
lsdp: primal objective value = -1.2059531781985829e+01
lsdp: dual objective value = -1.2059531782671732e+01
lsdp: Lovasz theta function value = 1.2059531782328779e+01
>>
>> % notice that specialized XZ method is faster but less
>> % accurate than XZ+ZX method
>>
>> % since useXZ = 0, the matrix A.s was formed, so we can now call
>> % pcond and dcond
>>
>> % for weights all one, usually Lovasz SDP is not degenerate
>>
>> rank(X.s,1.0e-06) % for weights all one, usually rank(X.s) > 1
ans =
9
>> rank(Z.s,1.0e-06) % for weights all one, usually rank(Z.s) < n-1
ans =
21
>> pcond(A,blk,X,1.0e-06); % sometimes primal nondegenerate
primal condition number = 1.4494e+01
>> dcond(A,blk,Z,1.0e-06); % sometimes dual degenerate
dual condition number = 4.092e+01
>>
>>
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> % Sample truss problem
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>>
>> load testdata/truss/truss1 % from Nemirovskii
>> setopt % sets scalefac = 100
>> init
>> sql
tau = 0.9990, scalefac = 100
iter p_step d_step p_infeas d_infeas X . Z pobj dobj
0 0.000e+00 0.000e+00 7.803e+02 3.603e+02 1.300e+05 1.000e+02 0.000e+00
1 1.000e+00 7.344e-01 6.356e-14 9.570e+01 1.391e+04 2.565e+02 -6.643e+01
2 1.000e+00 1.000e+00 7.105e-13 4.600e-16 2.470e+02 2.471e+02 1.014e-01
3 6.313e-01 1.000e+00 2.558e-13 7.850e-17 9.229e+01 9.189e+01 -4.013e-01
4 8.211e-01 1.000e+00 5.357e-14 6.206e-17 1.668e+01 1.745e+01 7.700e-01
5 5.064e-03 4.190e-01 5.353e-14 9.930e-16 1.004e+01 1.746e+01 7.424e+00
6 1.000e+00 9.086e-01 2.365e-13 1.662e-15 1.254e+00 1.006e+01 8.809e+00
7 9.886e-01 9.977e-01 7.944e-14 2.267e-15 1.919e-02 9.018e+00 8.999e+00
8 9.990e-01 9.990e-01 8.889e-14 8.951e-16 1.948e-05 9.000e+00 9.000e+00
9 9.990e-01 9.990e-01 2.337e-14 1.332e-15 1.948e-08 9.000e+00 9.000e+00
10 9.990e-01 9.990e-01 2.368e-14 1.986e-15 1.949e-11 9.000e+00 9.000e+00
fsql: stop since error reduced to desired value
sql: elapsed time = 0.994 seconds
sql: elapsed cpu time = 0.420 seconds
sql: number of iterations = 10
sql: final value of X . Z = 1.949e-11
sql: final primal infeasibility = 2.368e-14
sql: final dual infeasibility = 1.986e-15
sql: primal objective value = 8.9999963153049691e+00
sql: dual objective value = 8.9999963152853759e+00
>> pcond(A,blk,X,1.0e-06); % check if primal degenerate
primal condition number = Inf
>> dcond(A,blk,Z,1.0e-06); % check if dual degenerate
dual condition number = 8.920e+00
>>
>>
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> % Sample LMI problem
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>>
>> load testdata/lmi/hinf1 % from Gahinet
>> setopt % sets scalefac = 100
>> scalefac = 1000; % better choice for these
>> init
>> sql
tau = 0.9990, scalefac = 1000
iter p_step d_step p_infeas d_infeas X . Z pobj dobj
0 0.000e+00 0.000e+00 4.542e+03 3.742e+03 1.400e+07 0.000e+00 0.000e+00
1 8.700e-01 1.000e+00 5.906e+02 6.355e-14 1.458e+06 -2.306e+00 -1.431e+03
2 9.987e-01 1.000e+00 7.417e-01 4.032e-13 3.250e+03 -1.106e-02 -1.425e+03
3 9.159e-01 1.000e+00 6.241e-02 1.995e-13 3.426e+02 -1.203e-02 -2.534e+02
4 8.825e-01 9.935e-01 7.333e-03 3.108e-13 1.302e+01 -3.657e-02 -5.348e+00
5 9.912e-01 7.585e-01 6.439e-05 1.352e-13 1.309e+00 -1.132e+00 -2.373e+00
6 4.743e-01 1.000e+00 3.385e-05 5.754e-13 6.506e-01 -1.555e+00 -2.126e+00
7 9.626e-01 1.000e+00 1.265e-06 5.312e-13 2.088e-02 -2.020e+00 -2.038e+00
8 9.135e-01 9.854e-01 1.095e-07 5.714e-13 1.360e-03 -2.032e+00 -2.033e+00
9 6.290e-01 1.000e+00 5.246e-07 8.049e-13 1.131e-03 -2.032e+00 -2.033e+00
10 8.693e-01 9.966e-01 6.712e-08 1.668e-12 1.019e-04 -2.033e+00 -2.033e+00
11 9.975e-01 1.000e+00 2.433e-07 1.531e-12 5.992e-07 -2.033e+00 -2.033e+00
12 9.990e-01 9.990e-01 6.823e-08 1.073e-12 6.020e-10 -2.033e+00 -2.033e+00
fsql: stop since limiting accuracy reached
(smallest eigenvalue of Z.s = -1.741e-12)
sql: elapsed time = 1.003 seconds
sql: elapsed cpu time = 0.710 seconds
sql: number of iterations = 12
sql: final value of X . Z = 6.020e-10
sql: final primal infeasibility = 6.823e-08
sql: final dual infeasibility = 1.073e-12
sql: primal objective value = -2.0326845732912178e+00
sql: dual objective value = -2.0326421368134850e+00
>> pcond(A,blk,X,1.0e-06); % check if primal degenerate
primal condition number = 5.7041e+13
>> dcond(A,blk,Z,1.0e-06); % check if dual degenerate
dual condition number = 9.738e+00
>>
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> % A Steiner tree example (minimizing a sum of 2-norms)
>> % A special QCLP, written in SQLP format
>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>>
>> load testdata/steiner/ladder1 % Chung-Graham ladder
>> %
>> % Only blk.q is nonempty
>> blk
blk =
s: 0
l: 0
q: [49x1 double]
>> setopt
>> init
>> sql
tau = 0.9990, scalefac = 100
iter p_step d_step p_infeas d_infeas X . Z pobj dobj
0 0.000e+00 0.000e+00 6.930e+02 7.009e+02 4.900e+05 0.000e+00 0.000e+00
1 1.000e+00 1.000e+00 6.646e-15 1.079e-16 4.802e+03 -2.430e-01 -4.803e+03
2 1.000e+00 9.927e-01 9.293e-16 2.579e-15 3.487e+01 -4.910e-01 -3.536e+01
3 8.302e-01 9.503e-01 2.513e-15 2.369e-15 4.777e+00 -2.048e+01 -2.526e+01
4 9.119e-01 9.978e-01 4.454e-14 2.709e-15 5.564e-01 -2.318e+01 -2.373e+01
5 1.000e+00 1.000e+00 1.522e-13 4.469e-15 1.071e-01 -2.348e+01 -2.359e+01
6 8.876e-01 8.595e-01 4.918e-14 2.957e-15 1.467e-02 -2.353e+01 -2.354e+01
7 1.000e+00 1.000e+00 5.491e-12 3.257e-15 2.940e-03 -2.353e+01 -2.354e+01
8 9.953e-01 9.983e-01 9.722e-14 3.450e-15 9.223e-06 -2.353e+01 -2.353e+01
9 9.990e-01 9.990e-01 7.714e-13 2.302e-15 9.223e-09 -2.353e+01 -2.353e+01
10 9.990e-01 9.990e-01 6.046e-13 2.578e-15 9.247e-12 -2.353e+01 -2.353e+01
fsql: stop since error reduced to desired value
sql: elapsed time = 18.389 seconds
sql: elapsed cpu time = 12.580 seconds
sql: number of iterations = 10
sql: final value of X . Z = 9.247e-12
sql: final primal infeasibility = 6.046e-13
sql: final dual infeasibility = 2.578e-15
sql: primal objective value = -2.3534397500876146e+01
sql: dual objective value = -2.3534397500886332e+01
>> % verify that solution is strictly complementary
>> scomp(X,Z,blk,1e-5)
ans =
1
>>
>> load testdata/steiner/ladder2 % a different ladder
>> %
>> %
>> % Only blk.q is nonempty
>> blk
blk =
s: 0
l: 0
q: [49x1 double]
>> setopt
>> init
>> sql
tau = 0.9990, scalefac = 100
iter p_step d_step p_infeas d_infeas X . Z pobj dobj
0 0.000e+00 0.000e+00 6.930e+02 7.009e+02 4.900e+05 0.000e+00 0.000e+00
1 1.000e+00 1.000e+00 6.646e-15 9.310e-17 4.802e+03 -2.427e-01 -4.803e+03
2 1.000e+00 9.927e-01 8.237e-16 1.864e-15 3.490e+01 -4.902e-01 -3.539e+01
3 8.279e-01 9.385e-01 2.288e-15 3.655e-15 4.956e+00 -2.040e+01 -2.536e+01
4 9.305e-01 9.819e-01 1.014e-13 3.410e-15 4.794e-01 -2.320e+01 -2.368e+01
5 1.000e+00 1.000e+00 2.687e-13 4.627e-15 8.107e-02 -2.343e+01 -2.351e+01
6 8.911e-01 9.001e-01 7.657e-14 3.897e-15 8.711e-03 -2.346e+01 -2.347e+01
7 9.966e-01 9.955e-01 1.462e-12 3.440e-15 1.773e-03 -2.347e+01 -2.347e+01
8 1.000e+00 1.000e+00 1.543e-11 3.314e-15 4.066e-04 -2.347e+01 -2.347e+01
9 8.499e-01 8.496e-01 2.404e-12 4.447e-15 6.396e-05 -2.347e+01 -2.347e+01
10 1.000e+00 1.000e+00 4.716e-11 4.000e-15 1.527e-05 -2.347e+01 -2.347e+01
11 8.631e-01 8.630e-01 7.198e-12 3.821e-15 2.177e-06 -2.347e+01 -2.347e+01
fsql: stop since new point is substantially worse than current iterate
X . Z = 5.038e-07
pri_infeas = 2.882e-10
dual_infeas = 2.794e-15
sql: elapsed time = 19.491 seconds
sql: elapsed cpu time = 14.100 seconds
sql: number of iterations = 11
sql: final value of X . Z = 2.177e-06
sql: final primal infeasibility = 7.198e-12
sql: final dual infeasibility = 3.821e-15
sql: primal objective value = -2.3467622601298221e+01
sql: dual objective value = -2.3467624778208947e+01
>> % in this case, solution is NOT strictly complementary
>> [s,v] = scomp(X,Z,blk,1e-5)
s =
0
v =
s: []
q: [1x49 double]
l: []
>> [x0,z0] = qcfirst(X.q,Z.q,blk.q);
>> [distx,vx] = qcpos(X.q,blk.q);
>> [ z0 vx ] % for some indices, z=0 and x is on boundary
ans =
7.5904e-01 5.8516e-08
3.7407e-01 1.1873e-07
1.5181e-01 2.9256e-07
6.0723e-01 7.3145e-08
3.0362e-01 1.4629e-07
4.5542e-01 9.7526e-08
4.5542e-01 9.7527e-08
3.0362e-01 1.4628e-07
6.0723e-01 7.3146e-08
1.5181e-01 2.9254e-07
7.5904e-01 5.8517e-08
1.4145e-07 3.1433e-01
2.7576e-04 7.1523e-04
5.7725e-01 5.3462e-08
5.7725e-01 5.3463e-08
2.7421e-04 7.1246e-04
4.3819e-07 1.0158e-01
6.3623e-01 6.9813e-08
4.4721e-01 9.9313e-08
1.8901e-01 2.3500e-07
2.5820e-01 1.7203e-07
2.5820e-01 1.7201e-07
1.8901e-01 2.3497e-07
4.4721e-01 9.9318e-08
5.1640e-01 8.6011e-08
6.3623e-01 6.9810e-08
7.1836e-01 6.1830e-08
3.7407e-01 1.1874e-07
7.1836e-01 6.1829e-08
3.7407e-01 1.1874e-07
7.1836e-01 6.1829e-08
3.7407e-01 1.1874e-07
7.1836e-01 6.1829e-08
3.7407e-01 1.1874e-07
7.1836e-01 6.1830e-08
3.7407e-01 1.1873e-07
9.9986e-01 2.1123e-10
5.7718e-01 5.3475e-08
4.2292e-01 8.1495e-08
5.7718e-01 5.3475e-08
9.9986e-01 8.5694e-10
5.1640e-01 8.6011e-08
5.1640e-01 8.6009e-08
5.1640e-01 8.6011e-08
7.7460e-01 5.7339e-08
6.3623e-01 6.9811e-08
7.7460e-01 5.7341e-08
5.1640e-01 8.6011e-08
5.1640e-01 8.6009e-08
>> diary off