Quadratic equality constraints are non-convex: x^2 destroys the convexity
OngoingHi!
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()
-
Official comment
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
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()Best regards,
Jaromił1 -
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
Post is closed for comments.
Comments
3 comments