<div dir="ltr">Two strategies for scaling SDP's. <div> </div><div>1. Row scaling. Write the constraints in the form A*vec(X)=b. Then divide each of these equations by the largest (in absolute value) entry in that row of A. This is a very standard way to scale a linear system of equations. </div><div> </div><div>2. Column scaling of LP variables. If xj is an LP variable, then pick a scaling factor sj equal to the largest entry in column j of A and create a scaled variable uj with </div><div> </div><div>uj=sj*xj</div><div> </div><div>Then divide column j of A by sj. This is a standard way of scaling a linear system of equations. </div><div> </div><div>3. Scaling an SDP block is more complicated, because you have to maintain the positive definite and symmetric properties of the block. If X is an SDP block in your problem, then let </div><div> </div><div>U=S*X*S'</div><div> </div><div>X=inv(S)*U*inv(S')</div><div> </div><div>The invertibility of S insures that X is psd iff U is psd. </div><div> </div><div>Write a constraint </div><div> </div><div>tr(A*X)=b</div><div><br></div><div>as </div><div> </div><div>tr(A*inv(S)*U*inv(S'))=b</div><div> </div><div>or (by cyclic property of trace of a product)</div><div> </div><div>tr((inv(S')*A*inv(S))*U)=b</div><div><br></div><div>In the past, I've used diagonal scaling matrices S with S(i,i)=sqrt(A(i,i)) to make the diagonal of the scaled matrix equal to the identity matrix. </div><div><br></div><div>Note that all of these scalings will affect the error measures that you use- the algorithms for SDP all use norms of vectors as error measures, and the scaling will effectively reweight the importance of errors in different constraints or variables. </div><div><br></div><div> </div></div><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>