[Csdp] Sparse Formulation and Solver
Duro, Joao
j.a.duro at cranfield.ac.uk
Mon May 16 07:23:17 EDT 2011
Dear Dr. Brian,
I am so very thankful for your comments and clarifications.
1) I have really fundamentally misunderstood the C subroutine interface to CSDP. The sparse matrix formulation required for my problem is much simpler than what I though. As you have said for this problem I just need one 3x3 block matrix and to consider only non-zero elements from the matrix upper diagonal.
2) Considering option 3 (C subroutine interface) I have managed to generate the correct problem formulation shown by my .dat-s file (http://pastebin.com/g5mPuXMj). The C subroutine interface code can be found here (http://pastebin.com/HY7iTQvJ).
3) Considering option 2 (csdp stand along solver) and using the generated .dat-s file (by the C subroutine inferface) I have managed to obtained the correct X matrix.
4) I have also managed to do the same with the (C subroutine interface) but it required a consecutive call to write_prob (line 144) and read_prob (line 146) before calling initsoln (line 152) and easy_sdp (line 153). The obtained result is this (http://pastebin.com/032r09y4).
5) If I remove write_prob (line 144) and read_prob (line 146) from the code I get (http://pastebin.com/SNDqfnzc). I guess this is due to bad initialized variables (could be C, b or constraints). I have also looked into how readprob.c initializes the variables but I could not find a difference, but clearly there must be some.
Thanks once again for your help,
Joao
________________________________________
From: Brian Borchers [borchers at nmt.edu]
Sent: 15 May 2011 03:38
To: Duro, Joao
Cc: csdp at list.coin-or.org
Subject: Re: [Csdp] Sparse Formulation and Solver
On Sat, May 14, 2011 at 7:12 PM, Duro, Joao <j.a.duro at cranfield.ac.uk<mailto: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<mailto:borchers at nmt.edu>
Department of Mathematics http://www.nmt.edu/~borchers/<http://www.nmt.edu/%7Eborchers/>
New Mexico Tech Phone: (575) 322-2592
Socorro, NM 87801 FAX: (575) 835-5366
More information about the Csdp
mailing list