Why the second-order cone constraint is classified as a non-convex model?
回答済み
When 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
-
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
サインインしてコメントを残してください。
コメント
2件のコメント