[Csdp] Problems with large SDP problems

[Marcus P S]

Thanks, Brian. That was an embarassing mistake. It was also the cause
of segmentation faults I was getting SDPA (so SDPA does not detect
this potential problem either).

I was adding 1 to the number of constraints, so it was an easy fix.

However, CSDP still does not work for N=5, although the error now is
different but the general behaviour is the same (larger and larger
objective functions):

Too many line search failures, giving up.
Failure: return code is 9
Primal objective value: -2.7424893e+06
Dual objective value: 2.4569780e+05
Relative primal infeasibility: 1.01e+02
Relative dual infeasibility: 3.67e-01
Real Relative Gap: 1.00e+00
XZ Relative Gap: 2.12e+01
DIMACS error measures: 1.01e+02 0.00e+00 2.53e+00 0.00e+00 1.00e+00 2.12e+01
Elements time: 10.930059
Factor time: 2.871265
Other time: 150.734595
Total time: 164.535919

SDPA is able to reach a final answer which is correct up to the
accuracy I expect, so I don't think it is a problem with the matrices
I pass on.

Any suggestions?
Marcus

On Tue, Oct 18, 2011 at 8:06 PM, Brian Borchers <borchers at nmt.edu> wrote:
> Unfortunately, all of your SDPA files are incorrect.  Although CSDP would
> ideally be able to detect this, it doesn't do so, and then the solution
> process fails.  Anyway, here's an explanation of what's wrong with the file
> for N=1.  The other files all appear to have the same defect:
>
> Here's the file:
>
> 5
> 2
> 4 4
> 1 0 0 0
> 0 1 2 2 -1.000000e-02
> 0 1 1 2 -5.027783e-01
> 0 1 3 3 -1.000000e-02
> 0 1 1 3 4.534177e-01
> 0 1 4 4 -1.000000e-02
> 0 1 1 4 7.358455e-01
> 0 2 1 1 -5.000000e-01
> 0 2 2 2 -5.000000e-01
> 0 2 3 3 -5.000000e-01
> 0 2 4 4 -5.000000e-01
> 1 1 1 1 1
> 2 1 1 2 -1
> 2 2 1 2 5.000000e-01
> 2 2 3 4 5.000000e-01
> 3 1 1 3 -1
> 3 2 2 3 5.000000e-01
> 3 2 1 4 -5.000000e-01
> 4 1 1 4 -1
> 4 2 1 1 5.000000e-01
> 4 2 2 2 -5.000000e-01
> 4 2 3 3 5.000000e-01
> 4 2 4 4 -5.000000e-01
>
> In the first line of the file, you say that the problem has five constraints
> matrices (A1, A2, A3, A4, and A5), plus an objective matrix C.  In line 2,
> you say that there are two SDP blocks in each matrix, of sizes 4x4 and 4x4
> (line 3.)  In line 4, you provide the right hand sides for four
> constraints.  This is incorrect, since you said that there were five
> constraints.  In the following lines you give the entries for C and the
> constraint matrices A1, A2, A3, and A4, but not A5.
>
> From what you've said, this problem should actually have five constraints
> rather than four constraints.  To fix this, you'll have to supply the right
> hand side of the 5th constraint in line 4, and you'll have to give the
> entries in the A5 constraint matrix.
>
>
> On Tue, Oct 18, 2011 at 11:43 AM, Marcus P S <marcus.ps at gmail.com> wrote:
>>
>> Hello all,
>>
>>  I am using SDP to perform maximum likelihood estimation of data for
>> some physical problems, but I am running into some strange behaviour
>> when the SDP problem becomes larger.
>>
>>  Given an integer parameter N, the SD matrix has 2 blocks, one of
>> size 4^N and the other 2^(N+1), while there are 4^N+1 constraints. The
>> problem runs fine for randomly generated instance of size N=1,2,3,4.
>> However, when I run random instances for N=5, I always end up with the
>> dual objective function "running away" (quickly running up to >1E14),
>> finally giving up with the message
>>
>> Stuck at edge of dual feasibility, giving up.
>> Failure: return code is 6
>> Primal objective value: -1.0208180e+14
>> Dual objective value: 4.1157109e+14
>> Relative primal infeasibility: 4.99e-01
>> Relative dual infeasibility: 8.87e-07
>> Real Relative Gap: 1.00e+00
>> XZ Relative Gap: 2.00e-01
>> DIMACS error measures: 4.99e-01 0.00e+00 6.46e-06 0.00e+00 1.00e+00
>> 2.00e-01
>> Elements time: 15.671315
>> Factor time: 3.575801
>> Other time: 275.737643
>> Total time: 294.984759
>>
>> and the resulting answer being very far from the correct solution.  I
>> assume that this is an issue that can be addressed by tweaking the
>> parameters of the numerical algorithm, but I am not sure how to do it.
>> I tried changing "minstepfrac" and "maxstepfrac" but if anything that
>> only made things worse.
>>
>> If anyone has run into similar problem or has some useful pointers, I
>> would greatly appreciate it.
>>
>> Below you can find instances of the SDP problems I have been running.
>>
>> https://gist.github.com/1295649 (N=1)
>> https://gist.github.com/1295650 (N=2)
>> https://gist.github.com/1295782 (N=3)
>> https://gist.github.com/2957fede27de2f8d08ee (N=4)
>> https://gist.github.com/1296077 (N=5)
>>
>> (The last file was too large for gist, so I gzipped and then uuencoded)
>>
>> Best,
>> Marcus
>> _______________________________________________
>> Csdp mailing list
>> Csdp at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/csdp
>>
>
>
>
> --
> 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
>