[Csdp] SDP formulation

[Brian Borchers]

On Tue, Jul 26, 2011 at 8:22 AM, anass <anass.mouhsine at gmail.com> wrote:

> Greetings,
>
> I am trying to solve a semidefinite relaxation for a sparse generalized
> eigenvalue problem using csdp via R ( package Rcsdp courtesy of Hector
> Corrada).
>
> the program is the following, which is in the variables X and z (z in R+)
>
> maximize      Tr(AX)
> subject to      norm(X) - kz <= 0           where norm is 1-norm
>                     Tr(X) - z =0
>                     Tr(BX) = 1
>                     X>=0
>
>
The constraint on the 1-norm of X is very unusual in semidefinite
programming.  Are you sure that you don't mean to use some other norm, such
as the nuclear norm (the nuclear norm is the one norm of the singular values
of X)?

The 1-norm of X is given by the maximum of the sums of the absolute values
of the elements of the columns.

norm(X,1)=max(sum(abs(X(i,j)),i=1..n)            (max is over j=1..n)

You could implement the 1-norm by introducing an auxilliary variable T(i,j)
for each entry in the matrix, along with the constraints

T(i,j) >= X(i,j)                 i=1..n, j=1..n
T(i,j) >= -X(i,j)                i=1..n, j=1..n

and auxilliary variables S(j), j=1..n, with

S(j)=sum(X(i,j),i=1..n)             j=1..n

and an auxilliary variable N, with constraints

N>=S(j)                           j=1..n

Note that T doesn't have to be a PSD matrix, so these variables can be
stored in a diagonal block.  It's convenient to require all of T, S, and N
to be nonnegative.

This formulation would only be practical for very small X matrices, since it
introduces 2n^2+2n additional constraints to the problem.


> I would like to know how to formulate this program in the adequate csdp
> format in order to solve it.
>
>
 I hope this answers your question.



-- 
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/20110726/f2359116/attachment.html