[Csdp] Inequalities in CSDP 6.1.1

[Brian Borchers]

On Tue, May 17, 2011 at 6:32 AM, Sebastian Berckey <
sebastian.berckey at tu-dortmund.de> wrote:

> We want to use CSDP in a branch & bound program for calculating bounds
> for integer quadratic
> programs using SDP-relaxation. In this context we want to use
> inequality constraints.
>
> We can't find any hint how to use inequalities with csdp 6.1.1, though
> it seems that older
> versions of csdp provided that feature. So is it still possible to use
> inequality constraints with csdp 6.1.1? We thought about introducing
> slack variables ourselves, but don't know how to ensure the
> nonnegativity of them in csdp.
>
>
As you've noted, early versions of CSDP had direct support for inequality
constraints, because slack variables would have needed to be included in a
single large matrix block.  Once support for block structured problems was
in the code there really wasn't any advantage to including direct support
for inequality constraints, since slack variables can easily be put into a
diagonal block.  That's why this feature was removed from CSDP.

The way to do this is by introducing slack variables.  The slack variables
are stored in a separate block of the block diagonal matrix, and that block
should be a "diagonal block" rather than a normal matrix block.  If you're
familiar with SeDuMi, this means putting the slacks into K.l.

For example, suppose that X is a two by two matrix variable and your problem
is:

    max X(1,1)+2*X(2,2)
    s.t.   X(1,1)+X(2,2) <= 5
           X(1,1)+X(1,2)+X(2,1)+X(2,2) <= 10
           X is positive semidefinite.

Introduce slack variables X(3,3) and X(4,4) and write this as:

       max X(1,1)+2*X(2,2)
       s.t.   X(1,1)+X(2,2)  + X(3,3) = 5
               X(1,1)+X(1,2)+X(2,1)+X(2,2) + X(4,4) = 10
               X is positive semidefinite.

The constraint that X is PSD ensures that X(3,3)>=0 and X(4,4)>=0.  (The
diagonal elements of a PSD matrix are always nonnegative.)

You could simply set this problem up as a problem involving a 4 by 4 PSD
matrix X.  For this tiny example, that would work well, but for a very large
problem with thousands of inequality constraints, that would be very
inefficient.

You can improve this formulation by treating X as a block diagonal matrix
consisting of a 2x2 positive semidefinite block and a 2 element diagonal
block.  That is:

  X=[X11 X12   0      0;
        X21 X22  0      0;
            0      0  X33  0;
            0      0      0   X44];

This block diagonal formulation saves storage, and also saves CPU time in
solving the problem.

If you aren't already familiar with it, please read the description of the
SDPA sparse problem format at

   http://euler.nmt.edu/~brian/sdplib/FORMAT

The above example can be formulated in SDPA sparse format (with comments
added) as

2                                                           # 2 constraints
2                                                           # 2 blocks
2 -2                                                       # a 2x2 block and
2 nonnegative variables.
5.0  10.0                                               # the right hand
side, b.
0 1 1 1 1.0                                            # C(1,1)=1.0
0 1 2 2 2.0                                            # C(2,2)=2.0
1 1 1 1 1.0                                            # A1(1,1)=1.0
1 1 2 2 1.0                                            # A1(2,2)=1.0
1 2 1 1 1.0                                            # A1(3,3)=1.0  this
is the (1,1) element of block 2.
2 1 1 1 1.0                                            # A2(1,1)=1.0
2 1 1 2 1.0                                           # A2(1,2)=1.0   it's
implied that A2(2,1)=1.0.
2 1 2 2 1.0                                            # A2(2,2)=1.0
2 2 2 2 1.0                                            # A2(4,4)=1.0 this is
the 2,2 element of block 2.

The solution is:

2.000000000000005773e+00 5.434131996250952711e-09        # y=[2 0]
1 1 1 1 1.000000007247586531e+00                                           #
Z(1,1)=1.0
1 1 1 2 5.434131996250952711e-09
# Z(1,2)=0.0
1 1 2 2 7.247586593901009102e-09
# Z(2,2)=0.0
1 2 1 1 2.000000001813454720e+00                                           #
Z(3,3)=2.0
1 2 2 2 7.247580806281872776e-09
# Z(4,4)=0.0
2 1 1 1 3.623790669100295336e-08
# X(1,1)=0.0
2 1 1 2 -2.759429726476486466e-08
# X(1,2)=0.0
2 1 2 2 4.999999945643135213e+00                                           #
X(2,2)=5.0
2 2 1 1 1.811895773879953503e-08
# X(3,3)=0.0
2 2 2 2 5.000000073307552917e+00                                           #
X(4,4)=5.0

I hope this example has been helpful to you.  Please let me know if you have
any questions about the example.

I assume that you're going to be using the C subroutine interface to CSDP to
solve your problems.  I would strongly encourage you to use the latest trunk
version of CSDP from the subversion repository, because it has improved
error checking that will help you to find any problems with the data
structures that you pass into 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/csdp/attachments/20110517/2e708d0b/attachment.html