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

Sat Sep 16 09:00:18 EDT 2017

On Fri, Sep 15, 2017 at 10:08 PM, Hans Mittelmann <mittelma at asu.edu> wrote:

> 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
>
>
Yes- I'd remembered the XZ relative gap rather than the primal
feasibility.  The point remains that all of the double precision codes are
struggling to achieve primal and dual feasibility.

>
> 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> 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
>> https://urldefense.proofpoint.com/v2/url?u=https-3A__list.co
>> in-2Dor.org_mailman_listinfo_csdp&d=DwICAg&c=Ngd-ta5yRYsqeU
>> sEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=v6WE143jZEM_60H8_5y1Mg&m=
>> WgNXQcfm9XM_RVwSFiTvTtqcQ62Frei51FVLrirWQkg&s=VWy8otSLFzhjZl
>> ig4jcSsq0hEcx7VWUPRz1bykIDVPw&e=
>>
>>
>
>
> --
> Brian Borchers                          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
> https://urldefense.proofpoint.com/v2/url?u=https-3A__list.
> coin-2Dor.org_mailman_listinfo_csdp&d=DwICAg&c=Ngd-
> ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=kv9YjHgx2Q3T85jYlx6ozVwGCbdfro
> U5MhEqr2aByKQ&m=3AKAao-60tnrqxmEkL5iYr99emNDq7tVYaIeS
> dxRp5k&s=espaXzZ5lh4T_1E9bfY_pLu_P1VJS2c2k89B42VmVEs&e=
>
>
>

-- 
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/20170916/bd4abaa7/attachment.html>