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

[Brian Borchers]

I've followed up on Jedediah's challenging problem and come to the
conclusion that it is numerically dual infeasible, at least in double
precision arithmetic.

CSDP will declare a problem infeasible if it
can find a positive definite matrix U such that A(U) is essentially 0 while
trace(CU) is safely nonzero.  If the problem is primal feasible, then we
could add a very large multiple of U to a feasible solution X. The result,
X+alpha*U would be primal feasible and the primal objective value would be
unbounded.   This implies that the problem is primal unbounded and dual
infeasible.

In checking for this situation, it often helps to replace the original
right-hand side with a vector of 0's.  This changes the dual objective but
not the dual constraints.

The attached script solves this feasibility version of the problem and
obtains a certificate of dual infeasibility.  On the primal side, there is
difficulty in finding a primal feasible solution, but we can get reasonably
close.

A strategy that can sometimes help in finding a solution to a nearly
infeasible problem is to add a small multiple of A(I) to the right-hand
side b in the primal problem, or to add a small multiple of I to the
objective C in the dual problem.  This should make it possible to find
primal or dual solutions with eigenvalues shifted away from 0.

The script tries this trick and finds that a small perturbation of C makes
the problem dual feasible.  I also tried the trick on the primal but didn't
get any better solution than with the original right-hand side b.

It's possible that using extended precision we might obtain an optimal
solution to this problem, but the script shows that the problem is at least
very close to being dual infeasible.

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).
>
> 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/20170918/a5b21f12/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fryscript.m
Type: text/x-objcsrc
Size: 1007 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/csdp/attachments/20170918/a5b21f12/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fryscript.out
Type: application/octet-stream
Size: 16254 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/csdp/attachments/20170918/a5b21f12/attachment-0001.obj>