[Csdp] Couldn't get feasible solution for a moderately large SDP problem

[Feng Nan]

Thank you so much Brian for the help! Yes, column scaling does work! And
I'll pay more attention to the unrestricted variables in the future :)


On Tue, Jan 28, 2014 at 12:00 AM, Brian Borchers <borchers at nmt.edu> wrote:

>
>
>
> On Mon, Jan 27, 2014 at 4:25 PM, Feng Nan <fnan at bu.edu> wrote:
>
>> Hi Brian,
>> Thanks for the quick response. I actually generated the problem file in a
>> C code using CSDP routine write_prob().
>> When I called SDPT3 from MATLAB to solve this test problem I got
>>  gap := trace(XZ)       = 3.08e-07
>>  relative gap           = 6.86e-11
>>  actual relative gap    = 4.47e-11
>>
>> You are right that Sedumi seems to run into numerical problem too. But
>> the returned value agrees with the optimal solution given by SDPT3 so I
>> consider it solved successfully.
>>
>
> This is a mistake- because of the various weird ways in which the
> primal-dual method can fail you should never trust the solution of an SDP
> unless all six of the DIMACS error measures are reasonably small.
>
> For some problems there's a dramatic difference between the difference in
> the primal and dual objective values and the complentarity gap (which is
> what the algorithms actually minimize.)  These should be equal for
> "feasible" solutions, but some problems the objective value gap is
> extremely sensitive to any infeasibility in the primal or dual solutions.
>  This problem seems to show this.
>
> A common problem formulation technique that can cause the solvers
> difficulty is modeling unrestricted LP variables as the difference of two
> nonnegative variables.  Your problem has 35 such pairs.  The difficulty
> here is that the set of optimal solutions is unbounded, and during the
> algorithm, these pairs of nonnegative variables tend to increase without
> bound.  Both SDPT3 and CSDP have strategies for dealing with this issue,
> but SDPT3 seems to be doing a better job on this problem.  If you look at
> CSDP's solution, you'll see that x(1) and x(36) are large compared to their
> difference.
>
> In general, it is much safer to formulate such a problem with bounded
> variables.  If you do use the "difference of nonnegative variables" trick,
> then also add an upper bound on the absolute value of the free variable (or
> equivalently on the sum of the two nonnegative variables.)
>
> A third common issue is scaling.  Neither SDPT3 nor CSDP scale the problem
> data by default (it's hard to come up with a good scaling scheme that works
> well on all problems.)  In your problem, the coefficients for variables
> x(1) through x(70) are somewhat large relative to the coefficients in the
> rest of the A matrix.  A simple column scaling (in which we divide each LP
> variable column and the corresponding entry in C by its norm)  helps
> dramatically.
>
> >> [At,b,c,K]=readsdpa('SDPprob');
> >> A=At';
> >> for i=1:671, s=norm(A(:,i)); A(:,i)=A(:,i)/s; c(i)=c(i)/s; end
> >> writesdpa('SDPprobscaled.dat-s',A,b,c,K);
>
> I've attached the rescaled version of the problem.
>
> Here's the output from CSDP:
>
> ...
> Iter: 24 Ap: 1.00e+00 Pobj: -2.2395040e+03 Ad: 9.83e-01 Dobj:
> -2.2395036e+03
> Iter: 25 Ap: 9.58e-01 Pobj: -2.2395037e+03 Ad: 9.59e-01 Dobj:
> -2.2395040e+03
> Success: SDP solved
> Primal objective value: -2.2395037e+03
> Dual objective value: -2.2395040e+03
> Relative primal infeasibility: 1.06e-10
> Relative dual infeasibility: 6.09e-09
> Real Relative Gap: -6.31e-08
> XZ Relative Gap: 7.76e-09
> DIMACS error measures: 1.81e-09 0.00e+00 8.74e-08 0.00e+00 -6.31e-08
> 7.76e-09
>
> Note that if you use this problem scaling you'll need to rescale the
> solution to get the correct answer.
>
> --
> 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/20140129/b9a0f341/attachment.html>