<br><br><div class="gmail_quote">On Tue, Jul 26, 2011 at 8:22 AM, anass <span dir="ltr"><<a href="mailto:anass.mouhsine@gmail.com">anass.mouhsine@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Greetings,<br><br>I am trying to solve a semidefinite relaxation for a sparse generalized eigenvalue problem using csdp via R ( package Rcsdp courtesy of Hector Corrada).<br><br>the program is the following, which is in the variables X and z (z in R+)<br>
<br>maximize Tr(AX)<br>subject to norm(X) - kz <= 0 where norm is 1-norm<br> Tr(X) - z =0<br> Tr(BX) = 1<br> X>=0<br><br></blockquote><div>
<br>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)? <br>
<br>The 1-norm of X is given by the maximum of the sums of the absolute values of the elements of the columns. <br> <br>norm(X,1)=max(sum(abs(X(i,j)),i=1..n) (max is over j=1..n) <br> <br>You could implement the 1-norm by introducing an auxilliary variable T(i,j) for each entry in the matrix, along with the constraints<br>
<br>T(i,j) >= X(i,j) i=1..n, j=1..n<br>T(i,j) >= -X(i,j) i=1..n, j=1..n<br><br>and auxilliary variables S(j), j=1..n, with <br> <br>S(j)=sum(X(i,j),i=1..n) j=1..n<br> <br>
and an auxilliary variable N, with constraints<br> <br>N>=S(j) j=1..n <br> <br>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. <br>
<br>This formulation would only be practical for very small X matrices, since it introduces 2n^2+2n additional constraints to the problem. <br> <br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
I would like to know how to formulate this program in the adequate csdp format in order to solve it.<br>
<br></blockquote><div> </div><div> I hope this answers your question. </div></div><br><br clear="all"><br>-- <br>Brian Borchers <a href="mailto:borchers@nmt.edu" target="_blank">borchers@nmt.edu</a><br>
Department of Mathematics <a href="http://www.nmt.edu/%7Eborchers/" target="_blank">http://www.nmt.edu/~borchers/</a><br>New Mexico Tech Phone: (575) 322-2592<br>Socorro, NM 87801 FAX: (575) 835-5366<br>