Issues with fromsdpa.m handling of badly formed .dat-s files

[brianborchers]

I've uncovered a complicated situation involving the SDPA sparse format for semidefinite programming problems and SeDuMi. The issue arises when (most likely due to a problem formulation error), the same entry appears twice in a constraint matrix.

In this toy example the (1,2) entry in constraint 3 is first set to 1.0 and then set to 0.5 in the next line.

3
1
2
1000 900 5
0 1 1 2 3.0
1 1 1 1 1.0
2 1 2 2 1.0
3 1 1 2 1.0
3 1 1 2 0.5

test.txt

Different software packages handle this in different ways:

1. SDPA replaces the 1.0 coefficient with 0.5. The solution has X(1,2)=X(2,1)=5.0.

2. CSDP 6.1 adds the 1.0 and 0.5 to make the entry 1.5. The solution has X(1,2)=X(2,1)=1.6667.

3. SeDuMi's fromsdpa.m function adds 1.0 to 0.5 to make the entry 1.5. The solution has X(1,2)=X(2,1)=1.6667.

4. CSDP's MATLAB function readsdpa.m replaces the 1.0 coefficient with 0.5. The solution has X(1,2)=X(2,1)=5.0.

You can also fiddle with this by changing the indices from (1,2) to (2,1) in either or both of the entries- none of the results change. I expect that the behavior of duplicate entries in 0th constraint (the objective function matrix) would be similar.

There isn't any clear documentation of how this file should be interpreted and in most cases, the repeated entries are due to user error, so I think it would be best to issue a warning and proceed as SDPA does in this case. An alternative would be to treat it as an error and give up on reading the file.

The fromsdpa.m function uses the sparse function in MATLAB to put the entries into A. The help for sparse notes that "Any elements of s that have duplicate values of i and j are added together." It would
be necessary to identify duplicate entries before calling the sparse function. I don't have any suggestions for how to do that quickly.

[johanlofberg]

The user has specified an infeasible problem, so isn't that what should be generated? If too messy to allow for that case, I agree that a warning or error should be generated.

[brianborchers]

This isn't quite the same as having one constraint that says X12=5 and another that says X12=2.5. That would make the problem infeasible, and all of the solvers can deal with that. The repeated entry in the SDPA file here specifies a particular entry in one row of the constraint matrix twice.

[johanlofberg]

Ah, I see.

[jonathancurrie]

The ideal situation is that an error/warning is reported - one entry cannot have two values. The second best (which is fairly standard I believe) is the last value read is the one used. I definitely do not think they should add together, and if they do, then a warning must be presented. I cannot see a reason where this sort of behaviour would be expected...

…

On Sat, Jul 1, 2017 at 4:28 AM, brianborchers ***@***.***> wrote: This isn't quite the same as having one constraint that says X12=5 and another that says X12=2.5. That would make the problem infeasible, and all of the solvers can deal with that. The repeated entry in the SDPA file here specifies a particular entry in *one row* of the constraint matrix twice. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#27 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AD3RqRH7AvLauWhZu9nf2c3nAU-KPCzAks5sJSIjgaJpZM4OJ9Uy> .

[brianborchers]

For what it's worth, the current working version of CSDP stops with an error when it encounters this situation.

[brianborchers]

For what it's worth, SDPT3 read_sdpa() does the same thing as SeDuMi- it adds the two entries.