<div dir="ltr">Thank you so much Brian for the help! Yes, column scaling does work! And I'll pay more attention to the unrestricted variables in the future :)<br></div><div class="gmail_extra"><br><br><div class="gmail_quote">
On Tue, Jan 28, 2014 at 12:00 AM, Brian Borchers <span dir="ltr"><<a href="mailto:borchers@nmt.edu" target="_blank">borchers@nmt.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote"><div class="im">On Mon, Jan 27, 2014 at 4:25 PM, Feng Nan <span dir="ltr"><<a href="mailto:fnan@bu.edu" target="_blank">fnan@bu.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr"><div><div><div>Hi Brian,<br></div>Thanks for the quick response. I actually generated the problem file in a C code using CSDP routine write_prob().<br></div>When I called SDPT3 from MATLAB to solve this test problem I got <br>
gap := trace(XZ) = 3.08e-07<br> relative gap = 6.86e-11<br> actual relative gap = 4.47e-11<br><br></div><div>You are right that Sedumi seems to run into numerical problem too. But the returned value agrees with the optimal solution given by SDPT3 so I consider it solved successfully.<br>
</div></div></blockquote><div><br></div></div><div>This is a mistake- because of the various weird ways in which the primal-dual method can fail you should never trust the solution of an SDP unless all six of the DIMACS error measures are reasonably small. </div>
<div><br></div><div>For some problems there's a dramatic difference between the difference in the primal and dual objective values and the complentarity gap (which is what the algorithms actually minimize.) These should be equal for "feasible" solutions, but some problems the objective value gap is extremely sensitive to any infeasibility in the primal or dual solutions. This problem seems to show this. </div>
<div><br></div><div>A common problem formulation technique that can cause the solvers difficulty is modeling unrestricted LP variables as the difference of two nonnegative variables. Your problem has 35 such pairs. The difficulty here is that the set of optimal solutions is unbounded, and during the algorithm, these pairs of nonnegative variables tend to increase without bound. Both SDPT3 and CSDP have strategies for dealing with this issue, but SDPT3 seems to be doing a better job on this problem. If you look at CSDP's solution, you'll see that x(1) and x(36) are large compared to their difference. </div>
<div><br></div><div>In general, it is much safer to formulate such a problem with bounded variables. If you do use the "difference of nonnegative variables" trick, then also add an upper bound on the absolute value of the free variable (or equivalently on the sum of the two nonnegative variables.) </div>
<div><br></div><div>A third common issue is scaling. Neither SDPT3 nor CSDP scale the problem data by default (it's hard to come up with a good scaling scheme that works well on all problems.) In your problem, the coefficients for variables x(1) through x(70) are somewhat large relative to the coefficients in the rest of the A matrix. A simple column scaling (in which we divide each LP variable column and the corresponding entry in C by its norm) helps dramatically. </div>
<div><br></div><div>>> [At,b,c,K]=readsdpa('SDPprob');</div><div>>> A=At';</div><div><div>>> for i=1:671, s=norm(A(:,i)); A(:,i)=A(:,i)/s; c(i)=c(i)/s; end</div><div>>> writesdpa('SDPprobscaled.dat-s',A,b,c,K);</div>
</div><div><br></div><div>I've attached the rescaled version of the problem. </div><div><br></div><div>Here's the output from CSDP:</div><div><br></div><div>...</div><div><div>Iter: 24 Ap: 1.00e+00 Pobj: -2.2395040e+03 Ad: 9.83e-01 Dobj: -2.2395036e+03 </div>
<div>Iter: 25 Ap: 9.58e-01 Pobj: -2.2395037e+03 Ad: 9.59e-01 Dobj: -2.2395040e+03 </div><div>Success: SDP solved</div><div>Primal objective value: -2.2395037e+03 </div><div>Dual objective value: -2.2395040e+03 </div><div>
Relative primal infeasibility: 1.06e-10 </div><div>Relative dual infeasibility: 6.09e-09 </div><div>Real Relative Gap: -6.31e-08 </div><div>XZ Relative Gap: 7.76e-09 </div><div>DIMACS error measures: 1.81e-09 0.00e+00 8.74e-08 0.00e+00 -6.31e-08 7.76e-09</div>
</div><div><br></div><div>Note that if you use this problem scaling you'll need to rescale the solution to get the correct answer. </div><div><br></div></div><div class="im">-- <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/~borchers/" target="_blank">http://www.nmt.edu/~borchers/</a><br>New Mexico Tech Phone: (575) 322-2592<br>Socorro, NM 87801 FAX: (575) 835-5366
</div></div></div>
</blockquote></div><br></div>