Quadratic equality constraints are non-convex: x^2 destroys the convexity

Ongoing

Hussein Sharadga

November 24, 2022 04:49 Edited

• 
• 
• 

Hi!

I tried to solve a problem with the following objective function:

\[\min\  x^2-0.6x+M|x^2-x|\]

\[0<=x<=1\]

M=10
import gurobipy as gp
m=gp.Model()
x=m.addVar(vtype='C',lb=0,ub=1)

aux=m.addVar(vtype='C',lb=-1,ub=0)  # x^2-x
aux2=m.addVar(vtype='C',lb=0,ub=1)  # |x^2-x|
m.addConstr(aux==x**2-x)
m.addConstr(aux2==gp.abs_(aux))

m.setObjective(x**2-0.6*x+M*aux2)
m.optimize()

I am curious why x^2 destroys the convexity. This is how to fix the previous code using addGenConstrPow to replace x^2:

 

M=10
import gurobipy as gp
m=gp.Model()
x=m.addVar(vtype='C',lb=0,ub=1)

aux0=m.addVar(vtype='C',lb=0,ub=1)  # x^2
aux=m.addVar(vtype='C',lb=-1,ub=0)  # x^2-x
aux2=m.addVar(vtype='C',lb=0,ub=1)  # |x^2-x|

m.addGenConstrPow(x,aux0,2)
m.addConstr(aux==aux0-x)
m.addConstr(aux2==gp.abs_(aux))

m.setObjective(x**2-0.6*x+M*aux2)
m.optimize()

Related to

• Python

0

• 

  Jaromił Najman

  • Gurobi Staff

  November 24, 2022 11:06

  Hello,

  Your model is nonconvex because of the equality constraint \(aux = x^2 - x\). Nonlinear equality constraints are always nonconvex. Since \(x^2-x\) is \(\geq 0\) for all \(x \in [0,1]\), you could reformulate your model as

  M=10
  import gurobipy as gp
  m=gp.Model()
  x=m.addVar(vtype='C',lb=0,ub=1)
  
  m.setObjective(x**2-0.6*x+M*(-x**2 + x))
  m.optimize()

  Alternatively, you can just set the NonConvex parameter to 2 and let Gurobi solve the nonconvex model. In your case, it does not make any difference, because the model is (luckily) very small and simple.

  m.setParam("NonConvex",2)

  Best regards, 
  Jaromił

  1
• 

  Hussein Sharadga

  November 24, 2022 18:51 Edited

  • 
  • 
  • 

  Thank you so much! Jaromił Najman 

  I am working on a large-scale problem.

  I created this small example.

  But the objective function will be concave here. Gurobipy can find the minimum for a concave function if the problem is simple, as you mentioned in this post: https://support.gurobi.com/hc/en-us/community/posts/10860412140049-Maximizing-convex-function

  m.setObjective(x**2-0.6*x+M*(-x**2 + x))

   

  0

Please sign in to leave a comment.