[Csdp] Scaling the problem to mitigate the solver "giving up"
Brian Borchers
borchers at nmt.edu
Mon Sep 18 11:48:09 EDT 2017
On Mon, Sep 18, 2017 at 10:31 AM, Jedediah Fry <mfry90 at vt.edu> wrote:
> 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)?
>
Yes, you have to do this in order to get the dual of the scaled primal
problem. In terms of the solver, you'll be passing in \tilde{A} and
\tilde{a} rather than A and a. CSDP and other solvers will solve the
primal-dual pair of problems associated with the scaled primal problem.
> 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-ta5yRYsqeUs
>>> EDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=kv9YjHgx2Q3T85jYlx6ozVwGCbdfr
>>> oU5MhEqr2aByKQ&m=3AKAao-60tnrqxmEkL5iYr99emNDq7tVYaIeSdxRp5k
>>> &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
>>
>
>
--
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/1262fed6/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/1262fed6/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/1262fed6/attachment-0003.png>
More information about the Csdp
mailing list