<div dir="ltr">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. <div> </div><div>CSDP will declare a problem infeasible if it </div><div>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. </div><div> </div><div>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. </div><div><br></div><div>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. </div><div><br></div><div>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. </div><div><br></div><div>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. </div><div><br></div><div>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. <br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Sep 14, 2017 at 5:47 PM, Jedediah Fry <span dir="ltr"><<a href="mailto:mfry90@vt.edu" target="_blank">mfry90@vt.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi CSDP users,<div><br></div><div>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."</div><div><br></div><div>People have talked about similar issues in the CSDP archives, and Dr. Borchers states that scaling is often a good fix (<a href="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=" target="_blank">https://list.coin-or.org/<wbr>pipermail/csdp/2014-January/<wbr>000125.html</a>). 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?</div><div><br></div><div>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).</div><div><br></div><div>For reference, I've attached a problem and CSDP cannot solve but I believe is solvable.</div><div><br></div><div>Thanks,</div><div>Micah Fry</div><div> <div class="gmail_chip gmail_drive_chip" style="width:396px;height:18px;max-height:18px;background-color:rgb(245,245,245);padding:5px;color:rgb(34,34,34);font-family:arial;font-style:normal;font-weight:bold;font-size:13px;border:1px solid rgb(221,221,221);line-height:1"><a href="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=" style="display:inline-block;max-width:366px;overflow:hidden;text-overflow:ellipsis;white-space:nowrap;text-decoration:none;padding:1px 0;border:none" target="_blank"><img style="vertical-align:bottom;border:none" src="https://ssl.gstatic.com/docs/doclist/images/icon_10_generic_list.png"> <span dir="ltr" style="color:rgb(17,85,204);text-decoration:none;vertical-align:bottom">fry_prob.dat-s</span></a><img src="" style="opacity:0.55;float:right;display:none"></div></div></div>
<br>______________________________<wbr>_________________<br>
Csdp mailing list<br>
<a href="mailto:Csdp@list.coin-or.org">Csdp@list.coin-or.org</a><br>
<a href="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=" rel="noreferrer" target="_blank">https://urldefense.proofpoint.<wbr>com/v2/url?u=https-3A__list.<wbr>coin-2Dor.org_mailman_<wbr>listinfo_csdp&d=DwICAg&c=Ngd-<wbr>ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLx<wbr>WPA_2Wlc4&r=v6WE143jZEM_60H8_<wbr>5y1Mg&m=WgNXQcfm9XM_<wbr>RVwSFiTvTtqcQ62Frei51FVLrirWQk<wbr>g&s=<wbr>VWy8otSLFzhjZlig4jcSsq0hEcx7VW<wbr>UPRz1bykIDVPw&e=</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature">Brian Borchers <a href="mailto:borchers@nmt.edu" target="_blank">borchers@nmt.edu</a><br>Department of Mathematics <a href="http://www.nmt.edu/~borchers/" target="_blank">http://www.nmt.edu/~borchers/</a><br>New Mexico Tech Phone: (575) 322-2592<br>Socorro, NM 87801 FAX: (575) 835-5366</div>
</div></div></div>