SDP with rank 1 constraints

[Dima Pasechnik]

Is there an efficient way to encode in CVXOPT an SDP with the psd matrix unknown X and

constraints of the form tr(A_i X)=b_i, with A_i of rank 1, i.e. A_i=v_i v_i^T for some vectors?

Of course one can explicitly store A_i as nxn matrices, but this looks like an inefficiency; 

I understand that also there are methods to exploit such low rank constraints.

Thanks,

Dima

[Martin]

The builtin CVXOPT solvers do not exploit this kind of structure, so you would need to implement your own KKT solver to exploit this. I believe that SDPT3 allows you to explicitly specify constraints with low-rank matrices, and DSDP automatically detects and exploits low-rank structure, but I am not sure if it is possible to explicitly pass low-rank matrices to DSDP.

Martin

[Joachim Dahl]

If you have interesting models you can share, I would be very interested.  It's something we might implement in the next version of MOSEK.

--
You received this message because you are subscribed to the Google Groups "CVXOPT" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+unsubscribe@googlegroups.com.
To post to this group, send email to cvx...@googlegroups.com.
Visit this group at https://groups.google.com/group/cvxopt.
For more options, visit https://groups.google.com/d/optout.

[Dima Pasechnik]

On Monday, December 12, 2016 at 11:00:33 AM UTC, Joachim Dahl wrote:

If you have interesting models you can share, I would be very interested.  It's something we might implement in the next version of MOSEK.

Computing sums of squares decompositions of nonnegative multivariate polynomials, and the related optimisation problems, is one application I know.

See Sect . IV and further ones in 

http://www.mit.edu/~parrilo/pubs/files/LofbergParrilo-FromCoefficientsToSamplesANewApproachToSOSOptimization.pdf

DIma

  

On Mon, Dec 12, 2016 at 11:47 AM, Martin <martin.skovg...@gmail.com> wrote:

The builtin CVXOPT solvers do not exploit this kind of structure, so you would need to implement your own KKT solver to exploit this. I believe that SDPT3 allows you to explicitly specify constraints with low-rank matrices, and DSDP automatically detects and exploits low-rank structure, but I am not sure if it is possible to explicitly pass low-rank matrices to DSDP.

Martin

On Sunday, December 11, 2016 at 10:03:30 PM UTC+1, Dima Pasechnik wrote:

Is there an efficient way to encode in CVXOPT an SDP with the psd matrix unknown X and

constraints of the form tr(A_i X)=b_i, with A_i of rank 1, i.e. A_i=v_i v_i^T for some vectors?

Of course one can explicitly store A_i as nxn matrices, but this looks like an inefficiency; 

I understand that also there are methods to exploit such low rank constraints.

Thanks,

Dima

--
You received this message because you are subscribed to the Google Groups "CVXOPT" group.

To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+un...@googlegroups.com.

[Joachim Dahl]

Thanks, that's a good application that MOSEK has had requests for earlier.

Would you be willing to input such problems using the native solver API?  I think Yalmip at one point supported low-rank structures, but has since removed support for it.

[Dima Pasechnik]

On Wednesday, December 14, 2016 at 10:22:55 AM UTC, Joachim Dahl wrote:

Thanks, that's a good application that MOSEK has had requests for earlier.

Would you be willing to input such problems using the native solver API?  I think Yalmip at one point supported low-rank structures, but has since removed support for it.

Yes, definitely, I do not want to have to supply a file to read.

[Joachim Dahl]

That issue I was thinking of is that those SOS relaxations can be tedious to build using a raw solver API, and you most likely would not be able to use Yalmip or CVX to exploit that structure.  MOSEK is not going to make such a conversion to rank-1 matrices internally; the user (or Yalmip/CVX) will be required to input the data in a factored low-rank form.

To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+unsubscribe@googlegroups.com.

[Dima Pasechnik]

On Wednesday, December 14, 2016 at 5:12:27 PM UTC, Joachim Dahl wrote:

That issue I was thinking of is that those SOS relaxations can be tedious to build using a raw solver API, and you most likely would not be able to use Yalmip or CVX to exploit that structure.  MOSEK is not going to make such a conversion to rank-1 matrices internally; the user (or Yalmip/CVX) will be required to input the data in a factored low-rank form.

I don't do Matlab anyway, but call solvers from Python.

(slowly working towards a Yalmip-like tool in Python (in Sagemath, to be precise - there polynomials are easy 

to deal with)

Dima