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

[Brian Borchers]

Two strategies for scaling SDP's.

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.

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

uj=sj*xj

Then divide column j of A by sj.  This is a standard way of scaling a
linear system of equations.

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

U=S*X*S'

X=inv(S)*U*inv(S')

The invertibility of S insures that X is psd iff U is psd.

Write a constraint

tr(A*X)=b

as

tr(A*inv(S)*U*inv(S'))=b

or (by cyclic property of trace of a product)

tr((inv(S')*A*inv(S))*U)=b

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.

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.



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/20170915/5e5a64c8/attachment.html>