Solving linear object function with quadratic constraints

116 views
Skip to first unread message

Debjyoti Bhattacharjee

unread,
May 27, 2016, 7:56:20 PM5/27/16
to CVXOPT
Hi,

I am a beginner to optimization tools. I have an optimization function like the following one:-

  Minimize y
  such that
  y - x1.p1 - x2.p2 >= 0,
  x1,x2 are binary variables.
  p1 > 2
  p2 > 2

Can I use cvxopt for solving this? I do not think that the constraint would fall in the category of second order cone programming.

Martin

unread,
May 29, 2016, 10:41:24 AM5/29/16
to CVXOPT
It is not quite clear to me which of the symbols are variables, but in any case the presence of binary variables makes this a nonconvex problem. CVXOPT is for convex optimization.

Martin

Rms Danaraj

unread,
Jun 1, 2016, 1:11:08 PM6/1/16
to CVXOPT

I think SDP can be useful .


Convert the bunary variables as continuous variables by imposing an quadratic equality constraint


p1^2-p1=0

p2^2-p2=0



min

c'*x

subject to


x'*Qi*x+q'*x<=0: i=1,2,,,,m


can be formulated as SDP.


If Qi is positive semidefinite cvxopt will solve the problem.




Yifan Sun

unread,
Jun 1, 2016, 1:18:00 PM6/1/16
to cvx...@googlegroups.com
I think in general, equality constraints involving quadratic forms is not allowed (because it is not convex). However, you can try a linear relaxation (0 <= x <= 1) or an SDP relaxation (X >= x*x.T, diag(X) = 1) and hope that the solution is binary. (If it is, then your solution is optimal.) Otherwise, I think it may be better to try a MIP (mixed integer program) solver like COIN-OR, which uses branch and bound. 

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

RMS Danaraj

unread,
Jun 1, 2016, 1:29:21 PM6/1/16
to cvx...@googlegroups.com


Yes This is the general way.Thank you..


--
You received this message because you are subscribed to a topic in the Google Groups "CVXOPT" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/cvxopt/48smTlwYTPI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to cvxopt+un...@googlegroups.com.

Debjyoti Bhattacharjee

unread,
Jun 3, 2016, 12:13:56 AM6/3/16
to CVXOPT
Thank you all for the suggestions.
Reply all
Reply to author
Forward
0 new messages