Why the second-order cone constraint is classified as a non-convex model?
AnsweredWhen modeling an optimization problem that includes second-order cone constraints, I found that the model was classified as non-convex due to the second-order cone formulation. The code, .lp file, and solver log for the equivalent simplified model of the second-order cone constraint are provided below. I am looking to understand why this constraint was identified as non-convex.
model = Model()
model.setParam('Presolve',0)
x = model.addMVar((3,1),vtype = GRB.CONTINUOUS)
A,B = np.identity(3),np.ones((1,3))
lhs = B @ x #left hand side
model.addConstr(lhs >= 0)
model.addConstr(x.T @ A @ x >= 0)
model.addConstr(2*(x.T @ A @ x) <= lhs * lhs)
model.setObjective(x.sum(),GRB.MINIMIZE)
model.write('test.lp')
model.optimize()
Optimize a model with 1 rows, 3 columns and 3 nonzeros
Model fingerprint: 0x0c1b8af7
Model has 2 quadratic constraints
Coefficient statistics:
Matrix range [1e+00, 1e+00]
QMatrix range [1e+00, 2e+00]
Objective range [1e+00, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [0e+00, 0e+00]
Continuous model is non-convex -- solving as a MIP
Found heuristic solution: objective 0.0000000
Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 1 (of 32 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
C0 + C1 + C2
Subject To
R0: C0 + C1 + C2 >= 0
qc0: [ C0 ^2 + C1 ^2 + C2 ^2 ] >= 0
qc1: [ C0 ^2 - 2 C0 * C1 - 2 C0 * C2 + C1 ^2 - 2 C1 * C2 + C2 ^2 ] <= 0
Bounds
End
-
Official comment
-
Gurobi Staff
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.
-
-
-
Hi Jie,
While not exactly the same I think there are some similarities to this post:
https://support.gurobi.com/hc/en-us/community/posts/26748511582481/comments/26865244208529Because this constraint represents a squared SOC constraint, it is not a valid SOC in isolation - only while the constraint lhs >= 0 holds. In your implementation, this is enforced with the constraint B@x >= 0. For this reason it is better to make lhs a variable and enforce this relationship through bounds, i.e. replace
lhs = B @ x model.addConstr(lhs >= 0)with
lhs = model.addVar() # default lb of 0
model.addConstr(lhs == B @ x)The only other complicating factor seems to be this constraint:
model.addConstr(x.T @ A @ x >= 0)
If you make the lhs a variable, as above, then
- removing this constraint results in the model no longer declared as non-convex, or
- if presolve is left on, then this constraint will be removed (since it is redundant) and the model is no longer declared non-convex.Clearly the region defined by ||x|| >= r is convex when r = 0 but for r > 0 this is not true. My guess is that if we have a constraint of this form survive the presolve stage then the declaration of non-convexity is automatically triggered.
- Riley
0 -
-
After making lhs a variable and enforcing this relationship through bounds, the model is no longer classified as non-convex. Thank you very much for your answer!
0 -
Post is closed for comments.
Comments
3 comments