Turning SDP into vectorized form












1












$begingroup$


I have a graph with edge-set E and the following SDP (page 8 here)





I'm trying to use CVXOPT to solve this problem, which asks for SDP to be expressed in vectorized form as below:





How do I go about turning my SDP into this form?



Update
From suggestion of Joachim Dahl it's easier to figure out values from the dual form. We need to set $G_1,h_1$ and $c$ as follows



$$G_1=left(begin{array}{c}
text{vec}(I)\\
text{vec}(U_{e1})\\
text{vec}(U_{e2})\\
cdots\\
text{vec}(U_{em})
end{array}right)$$



here $I$ is $ntimes n$ identity matrix, $text{vec}(A)$ is matrix $A$ taken as vector in row-major vector form, $U_{ek}$ is a $0,1$-valued matrix where entry $i,j$ is 1 iff $i,j$ is in the edge $ek$.



$$c = (-1,0,0,0,0,ldots,0)$$



$$h_1=- left(begin{array}{ccc}
1&1&ldots\\
1&1&ldots\\
ldots&ldots&ldots
end{array}
right)$$



Note that for a graph with $n$ nodes and $m$ edges, $G_1$ is an $m+1times n^2$ matrix, $c$ is a vector of length $m+1$ and $h_1$ is an $ntimes n$ matrix. Matrix $X$ from original formulation is the $z_1$ parameter, an $n^2$ vector representing the matrix in row-major form






optimization math-software







share|cite|improve this question











$endgroup$

















    1












    $begingroup$


    I have a graph with edge-set E and the following SDP (page 8 here)





    I'm trying to use CVXOPT to solve this problem, which asks for SDP to be expressed in vectorized form as below:





    How do I go about turning my SDP into this form?



    Update
    From suggestion of Joachim Dahl it's easier to figure out values from the dual form. We need to set $G_1,h_1$ and $c$ as follows



    $$G_1=left(begin{array}{c}
    text{vec}(I)\\
    text{vec}(U_{e1})\\
    text{vec}(U_{e2})\\
    cdots\\
    text{vec}(U_{em})
    end{array}right)$$



    here $I$ is $ntimes n$ identity matrix, $text{vec}(A)$ is matrix $A$ taken as vector in row-major vector form, $U_{ek}$ is a $0,1$-valued matrix where entry $i,j$ is 1 iff $i,j$ is in the edge $ek$.



    $$c = (-1,0,0,0,0,ldots,0)$$



    $$h_1=- left(begin{array}{ccc}
    1&1&ldots\\
    1&1&ldots\\
    ldots&ldots&ldots
    end{array}
    right)$$



    Note that for a graph with $n$ nodes and $m$ edges, $G_1$ is an $m+1times n^2$ matrix, $c$ is a vector of length $m+1$ and $h_1$ is an $ntimes n$ matrix. Matrix $X$ from original formulation is the $z_1$ parameter, an $n^2$ vector representing the matrix in row-major form






    optimization math-software







    share|cite|improve this question











    $endgroup$















      1












      1








      1


      2



      $begingroup$


      I have a graph with edge-set E and the following SDP (page 8 here)





      I'm trying to use CVXOPT to solve this problem, which asks for SDP to be expressed in vectorized form as below:





      How do I go about turning my SDP into this form?



      Update
      From suggestion of Joachim Dahl it's easier to figure out values from the dual form. We need to set $G_1,h_1$ and $c$ as follows



      $$G_1=left(begin{array}{c}
      text{vec}(I)\\
      text{vec}(U_{e1})\\
      text{vec}(U_{e2})\\
      cdots\\
      text{vec}(U_{em})
      end{array}right)$$



      here $I$ is $ntimes n$ identity matrix, $text{vec}(A)$ is matrix $A$ taken as vector in row-major vector form, $U_{ek}$ is a $0,1$-valued matrix where entry $i,j$ is 1 iff $i,j$ is in the edge $ek$.



      $$c = (-1,0,0,0,0,ldots,0)$$



      $$h_1=- left(begin{array}{ccc}
      1&1&ldots\\
      1&1&ldots\\
      ldots&ldots&ldots
      end{array}
      right)$$



      Note that for a graph with $n$ nodes and $m$ edges, $G_1$ is an $m+1times n^2$ matrix, $c$ is a vector of length $m+1$ and $h_1$ is an $ntimes n$ matrix. Matrix $X$ from original formulation is the $z_1$ parameter, an $n^2$ vector representing the matrix in row-major form






      optimization math-software







      share|cite|improve this question











      $endgroup$




      I have a graph with edge-set E and the following SDP (page 8 here)





      I'm trying to use CVXOPT to solve this problem, which asks for SDP to be expressed in vectorized form as below:





      How do I go about turning my SDP into this form?



      Update
      From suggestion of Joachim Dahl it's easier to figure out values from the dual form. We need to set $G_1,h_1$ and $c$ as follows



      $$G_1=left(begin{array}{c}
      text{vec}(I)\\
      text{vec}(U_{e1})\\
      text{vec}(U_{e2})\\
      cdots\\
      text{vec}(U_{em})
      end{array}right)$$



      here $I$ is $ntimes n$ identity matrix, $text{vec}(A)$ is matrix $A$ taken as vector in row-major vector form, $U_{ek}$ is a $0,1$-valued matrix where entry $i,j$ is 1 iff $i,j$ is in the edge $ek$.



      $$c = (-1,0,0,0,0,ldots,0)$$



      $$h_1=- left(begin{array}{ccc}
      1&1&ldots\\
      1&1&ldots\\
      ldots&ldots&ldots
      end{array}
      right)$$



      Note that for a graph with $n$ nodes and $m$ edges, $G_1$ is an $m+1times n^2$ matrix, $c$ is a vector of length $m+1$ and $h_1$ is an $ntimes n$ matrix. Matrix $X$ from original formulation is the $z_1$ parameter, an $n^2$ vector representing the matrix in row-major form






      optimization math-software




      optimization math-software






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Dec 29 '18 at 0:08









      Glorfindel

      3,41581830




      3,41581830










      asked Mar 2 '11 at 3:59









      Yaroslav BulatovYaroslav Bulatov

      1,87411526




      1,87411526






















          2 Answers
          2






          active

          oldest

          votes


















          1












          $begingroup$

          $x$= vec_c(X)



          $c$= vec_c( $e e^T$ )



          vec_c(A) here is a column-major vectorization.



          Set of constraints can be expressed in the form Ax=b, where A is matrix $G_1$ in the question update, and vector b= (1, 0, ..., 0 ). First row takes care of trace constraint, and all the next take care of edge constraints.



          positive semi-definite constraint can be set via $G_1 x + s_1= h_1$, in particular $G_1$ is minus identity matrix of size $n^2 times n^2$, and $h_1=0$.



          It is computationally more efficient to implement it in a functional form. There is corresponding interface in python, I do not know about other implementations. You also need to take care of matrix representation, CVXOPT assumes it is symmetric, and access only lower triangular part of it, see manual you linked for details.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Actually you can put all of the constraints into G, I give the encoding I used under "Update". It seems to work in a sense that I got same result as exact integer QP solver on some small problems I tried
            $endgroup$
            – Yaroslav Bulatov
            Mar 4 '11 at 5:46










          • $begingroup$
            Let me know if you find any example where sdp relaxation and QP give different results.
            $endgroup$
            – mkatkov
            Mar 4 '11 at 6:05



















          2












          $begingroup$

          You can put $h_1 = 0$ and put $$ G_1 = -frac{1}{2} sum_{i leq j} (e_{ij}+e_{ji}) x_{ij}. $$ This way you have that $x_{ij}$ are the entries of a PSD. You can add your constraints using $Ax=b$. Finally, notice that your objective function is linear in the entries of the matrix.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            I don't understand, $mathbf{x}$ is unknown while $G_1$ should be fixed ahead of time
            $endgroup$
            – Yaroslav Bulatov
            Mar 2 '11 at 4:49












          • $begingroup$
            Yaroslav, look at the example there. $G_1$ is linear combination of symmetric matrices, the coefficients being the $x$'s.
            $endgroup$
            – Yuval Filmus
            Mar 2 '11 at 4:56











          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "69"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f24547%2fturning-sdp-into-vectorized-form%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          2 Answers
          2






          active

          oldest

          votes








          2 Answers
          2






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          1












          $begingroup$

          $x$= vec_c(X)



          $c$= vec_c( $e e^T$ )



          vec_c(A) here is a column-major vectorization.



          Set of constraints can be expressed in the form Ax=b, where A is matrix $G_1$ in the question update, and vector b= (1, 0, ..., 0 ). First row takes care of trace constraint, and all the next take care of edge constraints.



          positive semi-definite constraint can be set via $G_1 x + s_1= h_1$, in particular $G_1$ is minus identity matrix of size $n^2 times n^2$, and $h_1=0$.



          It is computationally more efficient to implement it in a functional form. There is corresponding interface in python, I do not know about other implementations. You also need to take care of matrix representation, CVXOPT assumes it is symmetric, and access only lower triangular part of it, see manual you linked for details.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Actually you can put all of the constraints into G, I give the encoding I used under "Update". It seems to work in a sense that I got same result as exact integer QP solver on some small problems I tried
            $endgroup$
            – Yaroslav Bulatov
            Mar 4 '11 at 5:46










          • $begingroup$
            Let me know if you find any example where sdp relaxation and QP give different results.
            $endgroup$
            – mkatkov
            Mar 4 '11 at 6:05
















          1












          $begingroup$

          $x$= vec_c(X)



          $c$= vec_c( $e e^T$ )



          vec_c(A) here is a column-major vectorization.



          Set of constraints can be expressed in the form Ax=b, where A is matrix $G_1$ in the question update, and vector b= (1, 0, ..., 0 ). First row takes care of trace constraint, and all the next take care of edge constraints.



          positive semi-definite constraint can be set via $G_1 x + s_1= h_1$, in particular $G_1$ is minus identity matrix of size $n^2 times n^2$, and $h_1=0$.



          It is computationally more efficient to implement it in a functional form. There is corresponding interface in python, I do not know about other implementations. You also need to take care of matrix representation, CVXOPT assumes it is symmetric, and access only lower triangular part of it, see manual you linked for details.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Actually you can put all of the constraints into G, I give the encoding I used under "Update". It seems to work in a sense that I got same result as exact integer QP solver on some small problems I tried
            $endgroup$
            – Yaroslav Bulatov
            Mar 4 '11 at 5:46










          • $begingroup$
            Let me know if you find any example where sdp relaxation and QP give different results.
            $endgroup$
            – mkatkov
            Mar 4 '11 at 6:05














          1












          1








          1





          $begingroup$

          $x$= vec_c(X)



          $c$= vec_c( $e e^T$ )



          vec_c(A) here is a column-major vectorization.



          Set of constraints can be expressed in the form Ax=b, where A is matrix $G_1$ in the question update, and vector b= (1, 0, ..., 0 ). First row takes care of trace constraint, and all the next take care of edge constraints.



          positive semi-definite constraint can be set via $G_1 x + s_1= h_1$, in particular $G_1$ is minus identity matrix of size $n^2 times n^2$, and $h_1=0$.



          It is computationally more efficient to implement it in a functional form. There is corresponding interface in python, I do not know about other implementations. You also need to take care of matrix representation, CVXOPT assumes it is symmetric, and access only lower triangular part of it, see manual you linked for details.






          share|cite|improve this answer









          $endgroup$



          $x$= vec_c(X)



          $c$= vec_c( $e e^T$ )



          vec_c(A) here is a column-major vectorization.



          Set of constraints can be expressed in the form Ax=b, where A is matrix $G_1$ in the question update, and vector b= (1, 0, ..., 0 ). First row takes care of trace constraint, and all the next take care of edge constraints.



          positive semi-definite constraint can be set via $G_1 x + s_1= h_1$, in particular $G_1$ is minus identity matrix of size $n^2 times n^2$, and $h_1=0$.



          It is computationally more efficient to implement it in a functional form. There is corresponding interface in python, I do not know about other implementations. You also need to take care of matrix representation, CVXOPT assumes it is symmetric, and access only lower triangular part of it, see manual you linked for details.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Mar 4 '11 at 5:22









          mkatkovmkatkov

          1263




          1263












          • $begingroup$
            Actually you can put all of the constraints into G, I give the encoding I used under "Update". It seems to work in a sense that I got same result as exact integer QP solver on some small problems I tried
            $endgroup$
            – Yaroslav Bulatov
            Mar 4 '11 at 5:46










          • $begingroup$
            Let me know if you find any example where sdp relaxation and QP give different results.
            $endgroup$
            – mkatkov
            Mar 4 '11 at 6:05


















          • $begingroup$
            Actually you can put all of the constraints into G, I give the encoding I used under "Update". It seems to work in a sense that I got same result as exact integer QP solver on some small problems I tried
            $endgroup$
            – Yaroslav Bulatov
            Mar 4 '11 at 5:46










          • $begingroup$
            Let me know if you find any example where sdp relaxation and QP give different results.
            $endgroup$
            – mkatkov
            Mar 4 '11 at 6:05
















          $begingroup$
          Actually you can put all of the constraints into G, I give the encoding I used under "Update". It seems to work in a sense that I got same result as exact integer QP solver on some small problems I tried
          $endgroup$
          – Yaroslav Bulatov
          Mar 4 '11 at 5:46




          $begingroup$
          Actually you can put all of the constraints into G, I give the encoding I used under "Update". It seems to work in a sense that I got same result as exact integer QP solver on some small problems I tried
          $endgroup$
          – Yaroslav Bulatov
          Mar 4 '11 at 5:46












          $begingroup$
          Let me know if you find any example where sdp relaxation and QP give different results.
          $endgroup$
          – mkatkov
          Mar 4 '11 at 6:05




          $begingroup$
          Let me know if you find any example where sdp relaxation and QP give different results.
          $endgroup$
          – mkatkov
          Mar 4 '11 at 6:05











          2












          $begingroup$

          You can put $h_1 = 0$ and put $$ G_1 = -frac{1}{2} sum_{i leq j} (e_{ij}+e_{ji}) x_{ij}. $$ This way you have that $x_{ij}$ are the entries of a PSD. You can add your constraints using $Ax=b$. Finally, notice that your objective function is linear in the entries of the matrix.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            I don't understand, $mathbf{x}$ is unknown while $G_1$ should be fixed ahead of time
            $endgroup$
            – Yaroslav Bulatov
            Mar 2 '11 at 4:49












          • $begingroup$
            Yaroslav, look at the example there. $G_1$ is linear combination of symmetric matrices, the coefficients being the $x$'s.
            $endgroup$
            – Yuval Filmus
            Mar 2 '11 at 4:56
















          2












          $begingroup$

          You can put $h_1 = 0$ and put $$ G_1 = -frac{1}{2} sum_{i leq j} (e_{ij}+e_{ji}) x_{ij}. $$ This way you have that $x_{ij}$ are the entries of a PSD. You can add your constraints using $Ax=b$. Finally, notice that your objective function is linear in the entries of the matrix.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            I don't understand, $mathbf{x}$ is unknown while $G_1$ should be fixed ahead of time
            $endgroup$
            – Yaroslav Bulatov
            Mar 2 '11 at 4:49












          • $begingroup$
            Yaroslav, look at the example there. $G_1$ is linear combination of symmetric matrices, the coefficients being the $x$'s.
            $endgroup$
            – Yuval Filmus
            Mar 2 '11 at 4:56














          2












          2








          2





          $begingroup$

          You can put $h_1 = 0$ and put $$ G_1 = -frac{1}{2} sum_{i leq j} (e_{ij}+e_{ji}) x_{ij}. $$ This way you have that $x_{ij}$ are the entries of a PSD. You can add your constraints using $Ax=b$. Finally, notice that your objective function is linear in the entries of the matrix.






          share|cite|improve this answer









          $endgroup$



          You can put $h_1 = 0$ and put $$ G_1 = -frac{1}{2} sum_{i leq j} (e_{ij}+e_{ji}) x_{ij}. $$ This way you have that $x_{ij}$ are the entries of a PSD. You can add your constraints using $Ax=b$. Finally, notice that your objective function is linear in the entries of the matrix.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Mar 2 '11 at 4:38









          Yuval FilmusYuval Filmus

          48.8k472146




          48.8k472146












          • $begingroup$
            I don't understand, $mathbf{x}$ is unknown while $G_1$ should be fixed ahead of time
            $endgroup$
            – Yaroslav Bulatov
            Mar 2 '11 at 4:49












          • $begingroup$
            Yaroslav, look at the example there. $G_1$ is linear combination of symmetric matrices, the coefficients being the $x$'s.
            $endgroup$
            – Yuval Filmus
            Mar 2 '11 at 4:56


















          • $begingroup$
            I don't understand, $mathbf{x}$ is unknown while $G_1$ should be fixed ahead of time
            $endgroup$
            – Yaroslav Bulatov
            Mar 2 '11 at 4:49












          • $begingroup$
            Yaroslav, look at the example there. $G_1$ is linear combination of symmetric matrices, the coefficients being the $x$'s.
            $endgroup$
            – Yuval Filmus
            Mar 2 '11 at 4:56
















          $begingroup$
          I don't understand, $mathbf{x}$ is unknown while $G_1$ should be fixed ahead of time
          $endgroup$
          – Yaroslav Bulatov
          Mar 2 '11 at 4:49






          $begingroup$
          I don't understand, $mathbf{x}$ is unknown while $G_1$ should be fixed ahead of time
          $endgroup$
          – Yaroslav Bulatov
          Mar 2 '11 at 4:49














          $begingroup$
          Yaroslav, look at the example there. $G_1$ is linear combination of symmetric matrices, the coefficients being the $x$'s.
          $endgroup$
          – Yuval Filmus
          Mar 2 '11 at 4:56




          $begingroup$
          Yaroslav, look at the example there. $G_1$ is linear combination of symmetric matrices, the coefficients being the $x$'s.
          $endgroup$
          – Yuval Filmus
          Mar 2 '11 at 4:56


















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Mathematics Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid …



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f24547%2fturning-sdp-into-vectorized-form%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          -

          Popular posts from this blog

          Index of /

          This page is only for reference, If you need detailed information, please check here
          Read more

          Tribalistas

          Image
            Nota: Para o álbum homônimo, veja Tribalistas (álbum de 2002). Para o segundo álbum homônimo, veja Tribalistas (álbum de 2017). Para o tipo de organização tribal, veja Tribalismo. Tribalistas Informação geral Origem Salvador e Rio de Janeiro País   Brasil Gênero(s) MPB Pop Samba Período em atividade 2002–2004 2017–atualmente Gravadora(s) EMI Phonomotor Records Universal Music Afiliação(ões) Dadi Pretinho da Serrinha Margareth Menezes Integrantes Arnaldo Antunes Carlinhos Brown Marisa Monte Página oficial www2.uol.com.br/tribalistas/ ...
          Read more

          Listed building

          Image
          Listed building (literalmente: prédio listado ) é toda estrutura protegida por lei pelo complexo sistema de tombamento do Reino Unido. Um listed building é qualquer estrutura oficialmente designada como tendo especial interesse arquitetônico, histórico ou cultural. É um estatuto amplamente usado, aplicado a centenas de milhares de estruturas. Estruturas tombadas não podem ser alteradas sem permissão especial, e desfrutam de isenções fiscais e outros benefícios. Cada um dos países do Reino Unido trata tombamento de forma diferente: Índice 1 Inglaterra 2 País de Gales 3 Irlanda do Norte 4 Escócia 5 Referências Inglaterra | O Palácio de Buckingham, Londres. As estruturas tombadas são listadas no Statutory List of Buildings of Special Architectural or Historic Interest , e incluem campos, sinais de trânsito, piers e áreas geográficas. A principal legislação pertinente é o Ancient Monuments and Archaeological Areas Act 1979 , [ 1 ] embora legisla...
          Read more