[Csdp] Sparse Formulation and Solver
Brian Borchers
borchers at nmt.edu
Sat May 14 22:38:54 EDT 2011
On Sat, May 14, 2011 at 7:12 PM, Duro, Joao <j.a.duro at cranfield.ac.uk>wrote:
> Hi,
>
> I am currently formulating a SDP problem using for that the C library from
> CSDP. My problem is described as follows.
> I have 9 variables 7 constraints I would like to maximize the trace of C*X
> and X must be psd.
>
> Objective function coefficients (C in CSDP)
> C=[ 2/3 -1/3 -1/3 -1/3 2/3 -1/3 -1/3 -1/3 2/3 ];
>
> Constraint coefficients (Ax in CSDP where x=1..7)
> At=[
> 1 1 1 1 1 1 1 1 1;
> 1 -1 0 -1 1 0 0 0 0;
> 1 0 -1 0 0 0 -1 0 1;
> 0 0 0 0 1 -1 0 -1 1;
> 1 -1 0 -1 1 0 0 0 0;
> 0 0 0 0 1 -1 0 -1 1;
> 1 0 -1 0 0 0 -1 0 1;
> ];
>
> Constraint equalities (b in CSDP)
> b=[0.000000 0.130967 0.231414 0.139552 0.130967 0.139552 0.231414];
>
> Using a solver called Sedumi in Matlab I do:
> K.s=[3]; [X]=sedumi(At,b,C,K);
> The coefficient matrix is not full row rank, numerical problems may occur.
> SeDuMi 1.3 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
> Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta =
> 0.500
> eqs m = 7, order n = 4, dim = 10, blocks = 2
> nnz(A) = 24 + 0, nnz(ADA) = 49, nnz(L) = 28
> it : b*y gap delta rate t/tP* t/tD* feas cg cg prec
> 0 : 1.67E+01 0.000
> 1 : -1.36E-02 3.19E+00 0.000 0.1905 0.9000 0.9000 1.25 1 1 2.0E+00
> 2 : 1.41E-01 5.91E-01 0.000 0.1856 0.9000 0.9000 2.11 1 1 2.6E-01
> 3 : 1.67E-01 1.53E-02 0.000 0.0259 0.9900 0.9900 1.39 1 1 5.3E-03
> 4 : 1.67E-01 3.59E-07 0.000 0.0000 1.0000 1.0000 1.01 1 1 1.2E-07
> 5 : 1.67E-01 3.85E-14 0.000 0.0000 1.0000 1.0000 1.00 1 4 1.3E-14
>
> iter seconds digits c*x b*y
> 5 0.1 13.7 1.6731100000e-01 1.6731100000e-01
> |Ax-b| = 6.1e-15, [Ay-c]_+ = 0.0E+00, |x|= 1.3e-01, |y|= 6.1e-01
>
> Detailed timing (sec)
> Pre IPM Post
> 3.289E-02 1.722E-01 3.330E-02
> Max-norms: ||b||=2.314140e-01, ||c|| = 6.666667e-01,
> Cholesky |add|=0, |skip| = 3, ||L.L|| = 2.04072.
>
> The obtained learnt matrix is:
> mat(X)
>
> 0.0650 -0.0158 -0.0493
> -0.0158 0.0344 -0.0186
> -0.0493 -0.0186 0.0679
>
>
I used the MATLAB interface to CSDP and got the same solution, using the
script:
A=[...
1 1 1 1 1 1 1 1 1; ...
1 -1 0 -1 1 0 0 0 0; ...
1 0 -1 0 0 0 -1 0 1; ...
0 0 0 0 1 -1 0 -1 1; ...
1 -1 0 -1 1 0 0 0 0; ...
0 0 0 0 1 -1 0 -1 1; ...
1 0 -1 0 0 0 -1 0 1];
c=[ 2/3 -1/3 -1/3 -1/3 2/3 -1/3 -1/3 -1/3 2/3 ];
b=[0.000000 0.130967 0.231414 0.139552 0.130967 0.139552 0.231414];
K.s=3;
[x,y,z]=csdp(A,b,c,K);
obj=c*x
reshape(x,3,3)
the output was:
>> script
Number of constraints: 7
Number of SDP blocks: 1
Number of LP vars: 0
Iter: 0 Ap: 0.00e+00 Pobj: -2.4628280e+01 Ad: 0.00e+00 Dobj: 0.0000000e+00
Iter: 1 Ap: 9.00e-01 Pobj: -2.6134079e+00 Ad: 1.00e+00 Dobj: 3.6539405e+00
Iter: 2 Ap: 9.00e-01 Pobj: -4.1192069e-01 Ad: 1.00e+00 Dobj: 3.2730877e+00
Iter: 3 Ap: 1.00e+00 Pobj: -1.6731100e-01 Ad: 1.00e+00 Dobj: 1.5205153e+00
Iter: 4 Ap: 9.00e-01 Pobj: -1.6731100e-01 Ad: 9.00e-01 Dobj: 1.4715074e-03
Iter: 5 Ap: 1.00e+00 Pobj: -1.6731100e-01 Ad: 9.00e-01 Dobj: -1.5043287e-01
Iter: 6 Ap: 8.10e-01 Pobj: -1.6731100e-01 Ad: 9.00e-01 Dobj: -1.6562331e-01
Iter: 7 Ap: 1.00e+00 Pobj: -1.6731100e-01 Ad: 9.00e-01 Dobj: -1.6714235e-01
Iter: 8 Ap: 1.00e+00 Pobj: -1.6731100e-01 Ad: 9.00e-01 Dobj: -1.6729426e-01
Iter: 9 Ap: 1.68e-01 Pobj: -1.6731100e-01 Ad: 1.00e+00 Dobj: -1.6731001e-01
Iter: 10 Ap: 1.00e+00 Pobj: -1.6731100e-01 Ad: 1.00e+00 Dobj: -1.6731093e-01
Iter: 11 Ap: 9.00e-01 Pobj: -1.6731100e-01 Ad: 9.00e-01 Dobj: -1.6731099e-01
Success: SDP solved
Primal objective value: -1.6731100e-01
Dual objective value: -1.6731099e-01
Relative primal infeasibility: 7.60e-11
Relative dual infeasibility: 1.39e-09
Real Relative Gap: 5.38e-09
XZ Relative Gap: 8.04e-09
DIMACS error measures: 8.80e-11 0.00e+00 2.01e-09 0.00e+00 5.38e-09 8.04e-09
obj =
0.1673
ans =
0.0650 -0.0158 -0.0493
-0.0158 0.0344 -0.0186
-0.0493 -0.0186 0.0679
Note that the optimal objective function value has the opposite sign from
SeDuMi's optimal objective value- this is a consequence of the difference
between SeDuMi's max and CSDP's min formulation of the primal. In the
matlab interface, this is correctly accounted for, and the sign change is
fixed by the time the solution is returned to MATLAB and the returned x
matches the result obtained by SeDuMi.
Thus I can solve your problem with my copy of CSDP using CSDP's MATLAB
interface.
This means that your problem must relate to how exactly you're using CSDP.
Reading further in your message, I see:
>
> The C code for this example is available in the following link
> http://pastebin.com/sYgbtyHx.
> The generated file with the problem in SDPA sparse format can be found in
> the following link http://pastebin.com/X4ykk2Sh .. I wonder if there is
> any mistake considering the values given above.
>
>
Thus it is apparent that you're using a C main program to setup your
program and then writing a .dat-s file out. This is a good way to debug
such a program. Unfortunately, there's something very wrong with your
.dat-s file....
I can write out a correct .dat-s file using the writesdpa() function in the
MATLAB interface to CSDP. The result is:
7
1
3
0.000000000000000000e+00 1.309670000000000001e-01
2.314140000000000086e-01 1.395520000000000094e-01
1.309670000000000001e-01 1.395520000000000094e-01
2.314140000000000086e-01
0 1 1 1 -6.666666666666666297e-01
0 1 1 2 3.333333333333333148e-01
0 1 2 2 -6.666666666666666297e-01
0 1 1 3 3.333333333333333148e-01
0 1 2 3 3.333333333333333148e-01
0 1 3 3 -6.666666666666666297e-01
1 1 1 1 1.000000000000000000e+00
1 1 1 1 1.000000000000000000e+00
1 1 1 2 1.000000000000000000e+00
1 1 2 2 1.000000000000000000e+00
1 1 1 3 1.000000000000000000e+00
1 1 2 3 1.000000000000000000e+00
1 1 3 3 1.000000000000000000e+00
2 1 1 1 1.000000000000000000e+00
2 1 1 2 -1.000000000000000000e+00
2 1 2 2 1.000000000000000000e+00
3 1 1 1 1.000000000000000000e+00
3 1 1 3 -1.000000000000000000e+00
3 1 3 3 1.000000000000000000e+00
4 1 2 2 1.000000000000000000e+00
4 1 2 3 -1.000000000000000000e+00
4 1 3 3 1.000000000000000000e+00
5 1 1 1 1.000000000000000000e+00
5 1 1 2 -1.000000000000000000e+00
5 1 2 2 1.000000000000000000e+00
6 1 2 2 1.000000000000000000e+00
6 1 2 3 -1.000000000000000000e+00
6 1 3 3 1.000000000000000000e+00
7 1 1 1 1.000000000000000000e+00
7 1 1 3 -1.000000000000000000e+00
7 1 3 3 1.000000000000000000e+00
Your problem data file looks nothing like this. Thus it's not particularly
surprising that CSDP failed to solve the problem you gave it.
Looking at your C code, it appears that you've tried to modify the example C
program included with MATLAB. That example program sets up a problem
involving block diagonal matrices with 3 blocks, while your problem has only
one block. Your .dat-s file has the same 3 block structure, with a 2x2 PSD
matrix, a 3x3 PSD matrix, and a 2 element nonnegative vector of linear
programming variables. Thus you seem to have really fundamentally
misunderstood the C subroutine interface to CSDP.
At this point, I'd have to suggest that you step back and reconsider your
options. There are (in rough order of difficulty) three options for
interfacing to CSDP:
1. Use MATLAB and call the csdp() function. If your main program is written
in MATLAB, this is definitely the way to go. You seem to already be
familiar with the use of SeDuMi, so you should have very little difficulty
using the MATLAB interface to CSDP, which uses the SeDuMi MATLAB input
format.
2. You can write a program that outputs a sparse SDPA format ".dat-s" file,
and then use the csdp stand along solver to solve that problem. You can
read back in the ".sol" file produced by CSDP to get at the actual
solution.
or
3. You can use the C subroutine interface. This requires understanding the
data structures used by CSDP and would require considerable effort on your
part.
Unless you really need to use option 3 for some reason, I'd strongly
encourage you to go with option 1 or 2. If there's a reason why it's really
important for you to go with option 3, I'd like to hear about it before
spending the time to teach you how to use this interface.
--
Brian Borchers borchers at nmt.edu
Department of Mathematics http://www.nmt.edu/~borchers/
New Mexico Tech Phone: (575) 322-2592
Socorro, NM 87801 FAX: (575) 835-5366
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/csdp/attachments/20110514/fae57372/attachment.html
More information about the Csdp
mailing list