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

[Brian Borchers]

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/20140127/296ddec9/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: SDPprobscaled.dat-s
Type: application/octet-stream
Size: 1630357 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/csdp/attachments/20140127/296ddec9/attachment-0001.obj>