[Csdp] Scaling the problem to mitigate the solver "giving up"
Jedediah Fry
mfry90 at vt.edu
Mon Sep 18 10:31:34 EDT 2017
Thank you for the tips.
Hans, I've been fiddling around more with SeDuMi, and it sometimes provides
feasible solutions, but it still fails with other closely related
problems. Also, because I have multiple cores, I can take advantage of
CSDP's parallel architecture to turn a solution around much quicker than
SeDuMi, which is particularly important for my research problem. I'll be
checking out your papers on different approaches you took to solving
ill-conditioned SDPs, as it appears to be the same problem I'm having
here.
Brian, with regards to scaling, I'm following method (3), but I wanted to
be sure I implement method (1) correctly as well. For notation, the primal
problem is:
[image: Inline image 1]
and the dual problem is:
[image: Inline image 2]
So, to implement row scaling, I rewrite A(X) = a as a linear equation,
Avec(X) = a. Then I divide each row of A and each entry of a accordingly,
obtaining an equivalent equation, \tilde{A}vec(X) = \tilde{a}. This
effectively scales the primal problem. My question is that whether it is
necessary, or helpful, or just a waste of time, to apply the same scaling
to my dual problem. In other words, my scaling of the primal problem
formulated \tilde{A}(X) = \tilde{a}, then in the dual problem is it
beneficial to minimize \tilde{a}^T y, and scale the equality constraint as
\tilde{A}^T (y) - C = Z (rather than leaving the dual problem untouched)?
Thanks again for the help,
Micah
On Sat, Sep 16, 2017 at 9:00 AM, Brian Borchers <borchers at nmt.edu> wrote:
>
>
> 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-ta5yRYsqeUs
>>> EDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=v6WE143jZEM_60H8_5y1Mg&m=WgNX
>>> Qcfm9XM_RVwSFiTvTtqcQ62Frei51FVLrirWQkg&s=VWy8otSLFzhjZlig4j
>>> cSsq0hEcx7VWUPRz1bykIDVPw&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.co
>> in-2Dor.org_mailman_listinfo_csdp&d=DwICAg&c=Ngd-ta5yRYsqeU
>> sEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=kv9YjHgx2Q3T85jYlx6ozVwGCbdf
>> roU5MhEqr2aByKQ&m=3AKAao-60tnrqxmEkL5iYr99emNDq7tVYaIeSdxRp5
>> k&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/20170918/ead85100/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 7052 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/csdp/attachments/20170918/ead85100/attachment-0002.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 8814 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/csdp/attachments/20170918/ead85100/attachment-0003.png>
More information about the Csdp
mailing list