QCQP problems with CVXOPT?

[maksimilian musik]

Hi all,

Total beginner in the optimization world here. I am trying to use CVXOPT to find the optimal solution for the following QCQP problem:

Where beta is the variable I am trying to optimize for, G_i is a positive semi-definite matrix, and r_i = tr(G_i) for all i.

Does anybody have any resources or tips as to how to convert this problem into something that can be solved by CVXOPT? It is my understanding that CVXOPT cannot deal with QCQP problems directly. Any suggestions to get the ball rolling?

Max

[Dima Pasechnik]

isn't such a problem NP-hard, in general?

You can perhaps try solving a semidefnite programming relaxation, replacing $\beta\beta^T$ with a positive semidefinite matrix B...

 

Max

[maksimilian musik]

@Dima, I am not sure about the complexity of the problem in general. I know of the SDP formulations of the problem, but it was my impression tha solving a QCQP formulation would be more efficient. Is there a way to express a quadratic constraint in CVXOPT that you know of? Also the fact that this problem is optimizing over both beta and t is throwing me off a little bit.

[Joachim Dahl]

This section in the Mosek manual explains how to convert a convex QCQP to conic form:

http://docs.mosek.com/modeling-cookbook/cqo.html#conic-quadratic-optimization-examples

--
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.

[maksimilian musik]

@Joachim

Ok, so this means that is actually not possible to optimize a problem in the QCQP form within CVXOPT?

On Wednesday, April 26, 2017 at 3:43:00 PM UTC+2, Joachim Dahl wrote:

This section in the Mosek manual explains how to convert a convex QCQP to conic form:

http://docs.mosek.com/modeling-cookbook/cqo.html#conic-quadratic-optimization-examples

On Wed, Apr 26, 2017 at 3:17 PM, maksimilian musik <maksimil...@gmail.com> wrote:

@Dima, I am not sure about the complexity of the problem in general. I know of the SDP formulations of the problem, but it was my impression tha solving a QCQP formulation would be more efficient. Is there a way to express a quadratic constraint in CVXOPT that you know of? Also the fact that this problem is optimizing over both beta and t is throwing me off a little bit.

On Tuesday, April 25, 2017 at 11:24:42 PM UTC+2, Dima Pasechnik wrote:

On Tuesday, April 25, 2017 at 2:31:48 PM UTC+1, maksimilian musik wrote:

Hi all,

Total beginner in the optimization world here. I am trying to use CVXOPT to find the optimal solution for the following QCQP problem:

Where beta is the variable I am trying to optimize for, G_i is a positive semi-definite matrix, and r_i = tr(G_i) for all i.

Does anybody have any resources or tips as to how to convert this problem into something that can be solved by CVXOPT? It is my understanding that CVXOPT cannot deal with QCQP problems directly. Any suggestions to get the ball rolling?

isn't such a problem NP-hard, in general?

You can perhaps try solving a semidefnite programming relaxation, replacing $\beta\beta^T$ with a positive semidefinite matrix B...

 

Max

--
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]

No, it's not possible to solve QCQPs directly.  You must reformulate them on conic form.

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

[maksimilian musik]

Ok, I understand. But after I reformulate according to the resource you linked, I would then be using something like the coneqp solver within CVXOPT?

Also in the following formulation, I would not need to explicitly program the last constraint right?:

[Joachim Dahl]

There is a minor step of programming let before you can feed it to CVXOPT. The constraint "(ti, 1, Fi*x) in Qr" needs to be rewritten to something like

ui = ti

vi = 1

zi = Fi*x

and then "(ui, vi, zi) in Qr" is a pure conic constraint that you don't program - but you need to setup the conic variables in the right way.  If you, after chewing on this for awhile, think this is too difficult to implement,  then you can use a modeling layer on top of CVXOPT, like PICOS or PYCVX.