[Csdp] Scaling the problem to mitigate the solver "giving up"

Fri Sep 15 22:08:21 EDT 2017

As my SeDuMi output shows one get a little more accuracy out of SeDuMi than prim infeasible 1e-2,
one gets 2e-5.

DIMACS error measures
  PInf     PConInf     DInf    DConInf    RelGap    RelComp
2.48E-05  0.00E+00  0.00E+00  0.00E+00  2.80E-04  1.81E-02

> On Sep 15, 2017, at 4:57 PM, Brian Borchers <borchers at nmt.edu> wrote:
> 
> After solving this problem with SeDuMi, SDPA, and CSDP, it appears that the problem is borderline feasible at best (SeDuMi returns a solution with relative primal infeasibility of about 1.0e-2, SDPA gives up after four iterations with a solution that has a relative dual infeasibility of about 1.0e4, and CSDP gets the primal and dual infeasibilities and XZ duality gap down to around 1.0e-6.)  
> 
> This problem has the particular kind of ill conditioning in which a pair of primal and dual feasible solutions (with say relative infeasibilities of less than 1.0e-6) can have a very small XZ duality gap and a very large gap between the primal and dual objective values (e.g. the XZ relative gap might be 1.0e-6 while the primal-dual objective relative gap might be 1.0e-2.)  Since the algorithm minimizes the XZ gap rather than the difference of primal and dual objective function values, this may make the solution worse than it actually is.   
> Looking at the problem data, the coefficients have a huge range of absolute values, from 1.7e-93 to 2.0e+04.  With conventional double precision floating point arithmetic, you don't want to have to deal with this much dynamic range.  Using extended precision floating point arithmetic (with e.g. 100 digits of precision) might help, but the computations would be very slow.  
>  
> Looking at the row norms and right hand side values (mostly 0, with one entry that is 1), it doesn't appear that row scaling will particularly help.  The problem appears to be primarily in the 191 by 191 SDP block #17.  It might be possible to come up with some problem specific scaling of this block that deals with this, but I'd approach this by reconsidering the problem formulation from scratch.  
> 
> 
> On Thu, Sep 14, 2017 at 5:47 PM, Jedediah Fry <mfry90 at vt.edu <mailto:mfry90 at vt.edu>> wrote:
> Hi CSDP users,
> 
> I'm using CSDP to solve large semidefinite programs and have run into some difficulties with the solver.  Typically, the solver either "gives up" with a solution that satisfies my LMIs and has an objective with a somewhat large duality gap (-1e-01 relative real gap), or "gives up" with a solution that does not satisfy my LMIs.   In the latter case, I believe there exists a feasible solution, but the solver gives up with a solution outside the feasible set. In both cases, it typically reports "Stuck at edge of dual feasibility."
> 
> People have talked about similar issues in the CSDP archives, and Dr. Borchers states that scaling is often a good fix (https://list.coin-or.org/pipermail/csdp/2014-January/000125.html <https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_pipermail_csdp_2014-2DJanuary_000125.html&d=DwMFaQ&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=v6WE143jZEM_60H8_5y1Mg&m=WgNXQcfm9XM_RVwSFiTvTtqcQ62Frei51FVLrirWQkg&s=P7vzkzNy0BvejZEkdAPzE9MgHVK2jveBOt-f5BcjYPQ&e=>). I'm unfamiliar with this approach, is there a good reference that describes different ways to scale A and c, and how to unscale the solution obtained from solving the scaled problem?
> 
> Also, what is the criterion that determines the solver should "give up?" Can I change any solver parameters to prolong the effort (the routine always "gives up" before my specified maximum iterations, and I'd the solver to see if it can chug on the problem a little bit longer).
> 
> The parameters for this are hard coded.  You can try adjusting them if you want.  I tried this by turning off the "giving up" feature, and didn't get a better solution.  You're really up against the limits of double precision floating point with this problem. 
>  
> 
> For reference, I've attached a problem and CSDP cannot solve but I believe is solvable.
> 
> Thanks,
> Micah Fry
>  
>  fry_prob.dat-s <https://urldefense.proofpoint.com/v2/url?u=https-3A__drive.google.com_a_vt.edu_file_d_0B-2DbHmaZTGpTrX1QtOVFfZ2hsd1U_view-3Fusp-3Ddrive-5Fweb&d=DwMFaQ&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=v6WE143jZEM_60H8_5y1Mg&m=WgNXQcfm9XM_RVwSFiTvTtqcQ62Frei51FVLrirWQkg&s=aHMYBcuO09mdPNFDLe4Il6xpXRcqjt6VEVT0x_IY7kE&e=>
> 
> _______________________________________________
> Csdp mailing list
> Csdp at list.coin-or.org <mailto:Csdp at list.coin-or.org>
> https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_csdp&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=v6WE143jZEM_60H8_5y1Mg&m=WgNXQcfm9XM_RVwSFiTvTtqcQ62Frei51FVLrirWQkg&s=VWy8otSLFzhjZlig4jcSsq0hEcx7VWUPRz1bykIDVPw&e= <https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_csdp&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=v6WE143jZEM_60H8_5y1Mg&m=WgNXQcfm9XM_RVwSFiTvTtqcQ62Frei51FVLrirWQkg&s=VWy8otSLFzhjZlig4jcSsq0hEcx7VWUPRz1bykIDVPw&e=>
> 
> 
> 
> 
> -- 
> Brian Borchers                          borchers at nmt.edu <mailto:borchers at nmt.edu>
> Department of Mathematics      http://www.nmt.edu/~borchers/ <https://urldefense.proofpoint.com/v2/url?u=http-3A__www.nmt.edu_-7Eborchers_&d=DwMFaQ&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=kv9YjHgx2Q3T85jYlx6ozVwGCbdfroU5MhEqr2aByKQ&m=3AKAao-60tnrqxmEkL5iYr99emNDq7tVYaIeSdxRp5k&s=_0zsHOIGIo-5mVKPkKgJkG5b3CoCi8f8cwZgkDGgcGI&e=>
> New Mexico Tech                       Phone: (575) 322-2592
> Socorro, NM 87801                   FAX: (575) 835-5366
> _______________________________________________
> Csdp mailing list
> Csdp at list.coin-or.org <mailto:Csdp at list.coin-or.org>
> https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_csdp&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=kv9YjHgx2Q3T85jYlx6ozVwGCbdfroU5MhEqr2aByKQ&m=3AKAao-60tnrqxmEkL5iYr99emNDq7tVYaIeSdxRp5k&s=espaXzZ5lh4T_1E9bfY_pLu_P1VJS2c2k89B42VmVEs&e= <https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_csdp&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=kv9YjHgx2Q3T85jYlx6ozVwGCbdfroU5MhEqr2aByKQ&m=3AKAao-60tnrqxmEkL5iYr99emNDq7tVYaIeSdxRp5k&s=espaXzZ5lh4T_1E9bfY_pLu_P1VJS2c2k89B42VmVEs&e=>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/csdp/attachments/20170915/33156821/attachment-0001.html>