How to formulate the SOC constraint ‖A x + b‖₂ ≤ t as a convex quadcon in MATLAB?
回答済み
I’m using Gurobi from MATLAB, which only exposes linear constraints and quadratic constraints (`model.quadcon`) with the requirement that the quadratic form be convex (Q ⪰ 0). I need to model the second‑order cone constraint
‖A_i x + b_i‖₂ ≤ t
where x ∈ ℝⁿ and t ≥ 0 is a scalar decision variable.
The natural quadratic form is
(A_i x + b_i)'(A_i x + b_i) − t² ≤ 0
but its Hessian is
[ A_i' A_i 0
0 −1 ]
which is indefinite. As expected, Gurobi flags the model as non‑convex and switches to the nonconvex QCP/MIP machinery.
My question is:
**Is there any convex reformulation of the SOC epigraph ‖A x + b‖₂ ≤ t that fits into MATLAB’s quadcon interface (i.e., using only PSD Q matrices)?**
Besides that, squaring a cone to formulate a quadcon seems like a bad idea numerically.
-
-
Gurobi Staff
Hi Zohar,
I'm not sure there is a way of using PSD matrices here, but if you were to define an auxiliary variable y_i, and the following
y_i == A_i x + b_i y_i**2 <= t**2 t >= 0then Gurobi should recognize the SOC. I'm not sure why it is not already recognizing it, but I would be very surprised if there was an issue after simplifying it. I don't think squaring the cone in this instance is an issue - there is no loss of precision in the coefficients.
- Riley
0 -
-
I tried:
Set parameter FeasibilityTol to value 1e-09 Set parameter OptimalityTol to value 1e-07 Set parameter BarHomogeneous to value 1 Set parameter Presolve to value 0 Warning for adding variables: zero or small (< 1e-13) coefficients, ignored Gurobi Optimizer version 13.0.0 build v13.0.0rc1 (win64 - Windows 11.0 (22631.2)) CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2] Thread count: 6 physical cores, 6 logical processors, using up to 6 threads Non-default parameters: FeasibilityTol 1e-09 OptimalityTol 1e-07 BarHomogeneous 1 Presolve 0 Optimize a model with 448 rows, 521 columns and 1288 nonzeros (Min) Model fingerprint: 0xef312dcf Model has 1 linear objective coefficients Model has 98 quadratic constraints Coefficient statistics: Matrix range [3e-01, 1e+01] QMatrix range [1e+00, 1e+00] Objective range [1e+00, 1e+00] Bounds range [0e+00, 0e+00] RHS range [4e-16, 1e+00] QRHS range [1e+00, 1e+00] Presolve time: 0.01s Presolved: 461 rows, 618 columns, 1314 nonzeros Presolved model has 98 second-order cone constraints Ordering time: 0.00s Barrier statistics: Free vars : 72 AA' NZ : 3.202e+03 Factor NZ : 1.535e+04 (roughly 1 MB of memory) Factor Ops : 6.525e+05 (less than 1 second per iteration) Threads : 1 Objective Residual Iter Primal Dual Primal Dual Compl Time 0 2.66637266e+01 -2.19845000e+01 5.35e+01 1.00e-01 1.12e+00 0s 1 2.66637266e+01 -2.19845000e+01 5.35e+01 1.00e-01 1.13e+00 0s 2 1.10325251e+03 -2.19845000e+05 2.21e+03 1.00e+03 4.57e+05 0s 3 1.10325251e+03 -2.19845000e+05 2.21e+03 1.00e+03 4.56e+05 0s 4 1.10325251e+03 -2.19845000e+05 2.21e+03 1.00e+03 4.56e+05 0s 5 1.10325251e+03 -2.19845000e+05 2.21e+03 1.00e+03 4.56e+05 0s Barrier performed 5 iterations in 0.06 seconds (0.01 work units) Numerical trouble encounteredPresolve detected SOCs. However, there are numerical issues, which Mosek doesn't have.
0 -
-
Hi Zohar,
If sharing the model is a possibility, then let me know and I can create a ticket through our Help Center to investigate further.
- Riley
0 -
-
-
Hi Zohar,
Thanks for sharing the code, I have extracted the model file and deleted your message with the link.
I will create a ticket to make it easier to involve the development team. You will receive an email shortly in this regard.
- Riley
1 -
サインインしてコメントを残してください。
コメント
4件のコメント