<br><br><div class="gmail_quote">On Sat, May 14, 2011 at 7:12 PM, Duro, Joao <span dir="ltr"><<a href="mailto:j.a.duro@cranfield.ac.uk">j.a.duro@cranfield.ac.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hi,<br>
<br>
I am currently formulating a SDP problem using for that the C library from CSDP. My problem is described as follows.<br>
I have 9 variables 7 constraints I would like to maximize the trace of C*X and X must be psd.<br>
<br>
Objective function coefficients (C in CSDP)<br>
C=[ 2/3 -1/3 -1/3 -1/3 2/3 -1/3 -1/3 -1/3 2/3 ];<br>
<br>
Constraint coefficients (Ax in CSDP where x=1..7)<br>
At=[<br>
1 1 1 1 1 1 1 1 1;<br>
1 -1 0 -1 1 0 0 0 0;<br>
1 0 -1 0 0 0 -1 0 1;<br>
0 0 0 0 1 -1 0 -1 1;<br>
1 -1 0 -1 1 0 0 0 0;<br>
0 0 0 0 1 -1 0 -1 1;<br>
1 0 -1 0 0 0 -1 0 1;<br>
];<br>
<br>
Constraint equalities (b in CSDP)<br>
b=[0.000000 0.130967 0.231414 0.139552 0.130967 0.139552 0.231414];<br>
<br>
Using a solver called Sedumi in Matlab I do:<br>
K.s=[3]; [X]=sedumi(At,b,C,K);<br>
The coefficient matrix is not full row rank, numerical problems may occur.<br>
SeDuMi 1.3 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.<br>
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500<br>
eqs m = 7, order n = 4, dim = 10, blocks = 2<br>
nnz(A) = 24 + 0, nnz(ADA) = 49, nnz(L) = 28<br>
it : b*y gap delta rate t/tP* t/tD* feas cg cg prec<br>
0 : 1.67E+01 0.000<br>
1 : -1.36E-02 3.19E+00 0.000 0.1905 0.9000 0.9000 1.25 1 1 2.0E+00<br>
2 : 1.41E-01 5.91E-01 0.000 0.1856 0.9000 0.9000 2.11 1 1 2.6E-01<br>
3 : 1.67E-01 1.53E-02 0.000 0.0259 0.9900 0.9900 1.39 1 1 5.3E-03<br>
4 : 1.67E-01 3.59E-07 0.000 0.0000 1.0000 1.0000 1.01 1 1 1.2E-07<br>
5 : 1.67E-01 3.85E-14 0.000 0.0000 1.0000 1.0000 1.00 1 4 1.3E-14<br>
<br>
iter seconds digits c*x b*y<br>
5 0.1 13.7 1.6731100000e-01 1.6731100000e-01<br>
|Ax-b| = 6.1e-15, [Ay-c]_+ = 0.0E+00, |x|= 1.3e-01, |y|= 6.1e-01<br>
<br>
Detailed timing (sec)<br>
Pre IPM Post<br>
3.289E-02 1.722E-01 3.330E-02<br>
Max-norms: ||b||=2.314140e-01, ||c|| = 6.666667e-01,<br>
Cholesky |add|=0, |skip| = 3, ||L.L|| = 2.04072.<br>
<br>
The obtained learnt matrix is:<br>
mat(X)<br>
<br>
0.0650 -0.0158 -0.0493<br>
-0.0158 0.0344 -0.0186<br>
-0.0493 -0.0186 0.0679<br>
<br></blockquote><div><br>I used the MATLAB interface to CSDP and got the same solution, using the script:<br> <br>A=[...<br>1 1 1 1 1 1 1 1 1; ...<br>1 -1 0 -1 1 0 0 0 0; ...<br>1 0 -1 0 0 0 -1 0 1; ...<br>0 0 0 0 1 -1 0 -1 1; ...<br>
1 -1 0 -1 1 0 0 0 0; ...<br>0 0 0 0 1 -1 0 -1 1; ...<br>1 0 -1 0 0 0 -1 0 1];<br><br>c=[ 2/3 -1/3 -1/3 -1/3 2/3 -1/3 -1/3 -1/3 2/3 ];<br><br>b=[0.000000 0.130967 0.231414 0.139552 0.130967 0.139552 0.231414];<br><br>K.s=3;<br>
[x,y,z]=csdp(A,b,c,K);<br>obj=c*x<br>reshape(x,3,3)<br><br>the output was:<br><br>>> script<br>Number of constraints: 7 <br>Number of SDP blocks: 1 <br>Number of LP vars: 0 <br>Iter: 0 Ap: 0.00e+00 Pobj: -2.4628280e+01 Ad: 0.00e+00 Dobj: 0.0000000e+00 <br>
Iter: 1 Ap: 9.00e-01 Pobj: -2.6134079e+00 Ad: 1.00e+00 Dobj: 3.6539405e+00 <br>Iter: 2 Ap: 9.00e-01 Pobj: -4.1192069e-01 Ad: 1.00e+00 Dobj: 3.2730877e+00 <br>Iter: 3 Ap: 1.00e+00 Pobj: -1.6731100e-01 Ad: 1.00e+00 Dobj: 1.5205153e+00 <br>
Iter: 4 Ap: 9.00e-01 Pobj: -1.6731100e-01 Ad: 9.00e-01 Dobj: 1.4715074e-03 <br>Iter: 5 Ap: 1.00e+00 Pobj: -1.6731100e-01 Ad: 9.00e-01 Dobj: -1.5043287e-01 <br>Iter: 6 Ap: 8.10e-01 Pobj: -1.6731100e-01 Ad: 9.00e-01 Dobj: -1.6562331e-01 <br>
Iter: 7 Ap: 1.00e+00 Pobj: -1.6731100e-01 Ad: 9.00e-01 Dobj: -1.6714235e-01 <br>Iter: 8 Ap: 1.00e+00 Pobj: -1.6731100e-01 Ad: 9.00e-01 Dobj: -1.6729426e-01 <br>Iter: 9 Ap: 1.68e-01 Pobj: -1.6731100e-01 Ad: 1.00e+00 Dobj: -1.6731001e-01 <br>
Iter: 10 Ap: 1.00e+00 Pobj: -1.6731100e-01 Ad: 1.00e+00 Dobj: -1.6731093e-01 <br>Iter: 11 Ap: 9.00e-01 Pobj: -1.6731100e-01 Ad: 9.00e-01 Dobj: -1.6731099e-01 <br>Success: SDP solved<br>Primal objective value: -1.6731100e-01 <br>
Dual objective value: -1.6731099e-01 <br>Relative primal infeasibility: 7.60e-11 <br>Relative dual infeasibility: 1.39e-09 <br>Real Relative Gap: 5.38e-09 <br>XZ Relative Gap: 8.04e-09 <br>DIMACS error measures: 8.80e-11 0.00e+00 2.01e-09 0.00e+00 5.38e-09 8.04e-09<br>
<br>obj =<br><br> 0.1673<br><br><br>ans =<br><br> 0.0650 -0.0158 -0.0493<br> -0.0158 0.0344 -0.0186<br> -0.0493 -0.0186 0.0679<br><br><br>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. <br>
<br>Thus I can solve your problem with my copy of CSDP using CSDP's MATLAB interface. <br> <br>This means that your problem must relate to how exactly you're using CSDP. Reading further in your message, I see:<br>
</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
The C code for this example is available in the following link <a href="http://pastebin.com/sYgbtyHx" target="_blank">http://pastebin.com/sYgbtyHx</a>.<br>
The generated file with the problem in SDPA sparse format can be found in the following link <a href="http://pastebin.com/X4ykk2Sh" target="_blank">http://pastebin.com/X4ykk2Sh</a> .. I wonder if there is any mistake considering the values given above.<br>
<br>
</blockquote><div><br>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....<br>
<br>I can write out a correct .dat-s file using the writesdpa() function in the MATLAB interface to CSDP. The result is:<br><br>7 <br>1 <br>3 <br>0.000000000000000000e+00 1.309670000000000001e-01 2.314140000000000086e-01 1.395520000000000094e-01 1.309670000000000001e-01 1.395520000000000094e-01 2.314140000000000086e-01 <br>
0 1 1 1 -6.666666666666666297e-01<br>0 1 1 2 3.333333333333333148e-01<br>0 1 2 2 -6.666666666666666297e-01<br>0 1 1 3 3.333333333333333148e-01<br>0 1 2 3 3.333333333333333148e-01<br>0 1 3 3 -6.666666666666666297e-01<br>1 1 1 1 1.000000000000000000e+00<br>
1 1 1 1 1.000000000000000000e+00<br>1 1 1 2 1.000000000000000000e+00<br>1 1 2 2 1.000000000000000000e+00<br>1 1 1 3 1.000000000000000000e+00<br>1 1 2 3 1.000000000000000000e+00<br>1 1 3 3 1.000000000000000000e+00<br>2 1 1 1 1.000000000000000000e+00<br>
2 1 1 2 -1.000000000000000000e+00<br>2 1 2 2 1.000000000000000000e+00<br>3 1 1 1 1.000000000000000000e+00<br>3 1 1 3 -1.000000000000000000e+00<br>3 1 3 3 1.000000000000000000e+00<br>4 1 2 2 1.000000000000000000e+00<br>4 1 2 3 -1.000000000000000000e+00<br>
4 1 3 3 1.000000000000000000e+00<br>5 1 1 1 1.000000000000000000e+00<br>5 1 1 2 -1.000000000000000000e+00<br>5 1 2 2 1.000000000000000000e+00<br>6 1 2 2 1.000000000000000000e+00<br>6 1 2 3 -1.000000000000000000e+00<br>6 1 3 3 1.000000000000000000e+00<br>
7 1 1 1 1.000000000000000000e+00<br>7 1 1 3 -1.000000000000000000e+00<br>7 1 3 3 1.000000000000000000e+00<br><br>Your problem data file looks nothing like this. Thus it's not particularly surprising that CSDP failed to solve the problem you gave it. <br>
<br>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. <br>
<br>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:<br> <br>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. <br>
<br>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. <br>
<br>or <br><br>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. <br> <br>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. <br>
</div></div><br>-- <br>Brian Borchers <a href="mailto:borchers@nmt.edu" target="_blank">borchers@nmt.edu</a><br>Department of Mathematics <a href="http://www.nmt.edu/%7Eborchers/" target="_blank">http://www.nmt.edu/~borchers/</a><br>
New Mexico Tech Phone: (575) 322-2592<br>Socorro, NM 87801 FAX: (575) 835-5366<br>