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

[Brian Borchers]

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.
> 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
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/20170915/3c0963e6/attachment-0001.html>