Second-Order Cone Programming (SOCP)

1966: NASA engineers spend weeks computing Apollo lunar module trajectories by hand. 2015: SpaceX uses SOCP to land Falcon 9 first stages in real time - the Acikmese-Ploen algorithm solves the fuel-optimal thrust control problem in 3-5 ms onboard. This became possible because constraints of the form ||thrust|| <= max_thrust are conic - they define an SOCP, not an arbitrary nonlinear program.

• **SpaceX rocket landing:** the thrust constraint ||T|| <= T_max is conic. The minimum-fuel landing problem is solved as SOCP in milliseconds onboard
• **5G antenna arrays:** beamforming with guaranteed per-user SNR is an SOCP with complex variables, solved in real time at base stations
• **Robust regression:** when data uncertainty lives in a ball of radius r, the worst-case objective is a norm - this gives SOCP

Definition and the second-order cone

1966: NASA engineers spend weeks manually computing fuel-optimal trajectories for the Apollo lunar module - a problem with thrust constraints that look like norm bounds. Fifty years later the same problem is formulated as SOCP and solved in milliseconds. SpaceX uses this to land Falcon 9 first stages in real time, running the Acikmese-Ploen SOCP algorithm onboard in 3-5 ms per guidance cycle.

The second-order cone (SOC) in $\mathbb{R}^{n+1}$ is the set of points $(x, t)$ satisfying $\|x\|_2 \leq t$. In 3D this is the ice cream cone with vertex at the origin. LP works with halfspaces (flat faces). SOCP adds curved conic constraints - and still keeps polynomial complexity. The key insight is that many physical constraints (bounded thrust, limited antenna power, uncertainty balls) are naturally conic.

**Standard SOCP:** $\min_{x} c^\top x$ $\text{s.t.} \; \|A_i x + b_i\|_2 \leq c_i^\top x + d_i, \quad i = 1, \ldots, m$ $\quad\quad Fx = g$ The constraint $\|A_i x + b_i\|_2 \leq c_i^\top x + d_i$ requires the vector $A_i x + b_i$ to lie inside the cone: its norm is bounded by a linear function. **Hierarchy of conic programs:** ``` LP subset QP subset QCQP subset SOCP subset SDP ``` Each class is strictly richer than the previous, and all are solvable in polynomial time via interior point methods.

Key SOCP formulations

The power of SOCP is that many applied problems with norm constraints reduce to it automatically. Three canonical examples: robust optimization with ball uncertainty sets, minimum-time orbit transfer, and antenna beamforming with per-user SNR guarantees.

**Problem 1 - Antenna beamforming:** Given: $K$ antennas, $L$ users. Weight vector $w \in \mathbb{C}^K$. Signal power to user $l$: $|h_l^\top w|^2$. Problem: $\min_{w} \|w\|^2 \quad \text{s.t.} \quad |h_l^\top w| \geq \gamma_l, \; l=1,\ldots,L$ The constraint $|h_l^\top w| \geq \gamma_l$ is a norm constraint - SOCP. **Problem 2 - Minimum-time orbit maneuver (Acikmese-Ploen 2007):** $\min T$ s.t. $\|T_t\|_2 \leq T_{max}, \; \ddot{r} = g + T_t/m$ The thrust constraint $\|T_t\|_2 \leq T_{max}$ is conic. This exact formulation underlies the Falcon 9 landing algorithm.

SOCP duality

The second-order cone is self-dual: $(K_{SOC})^* = K_{SOC}$. This means the dual of an SOCP is again an SOCP - unlike LP where the dual transposes the data but stays LP. Self-duality simplifies optimality analysis and gives clean KKT conditions. It also explains why interior point methods work so efficiently: the barrier function has a small self-concordance parameter.

**Dual cone of SOC:** For cone $K = \{(x,t): \|x\|_2 \leq t\}$, the dual cone is: $K^* = \{(u, s): \sup_{(x,t) \in K} u^\top x + s \cdot t \leq 0\} = K$ **KKT conditions for SOCP:** for the $i$-th conic constraint: 1. Primal feasibility: $\|A_i x + b_i\|_2 \leq c_i^\top x + d_i$ 2. Dual feasibility: $(\lambda_i, \mu_i) \in K_{SOC}$, i.e. $\|\lambda_i\|_2 \leq \mu_i$ 3. Complementary slackness: $\lambda_i^\top (A_i x + b_i) + \mu_i (c_i^\top x + d_i) = 0$ If the primal is strictly feasible (Slater condition holds) - strong duality holds, gap is zero.

Interior point for SOCP: computational side

Interior point methods for SOCP run in $O(\sqrt{n})$ iterations, each costing $O(n^3)$ for dense problems. Total: $O(n^{3.5})$ to reach accuracy $\varepsilon$. In practice ECOS solves problems with thousands of variables in seconds. The barrier parameter for SOC is 2 (optimal for this cone), which is why SOCP interior point methods are so stable.

**Barrier function for SOC:** For the constraint $\|x\|_2 \leq t$, the logarithmic barrier is: $\phi(x, t) = -\log(t^2 - \|x\|_2^2)$ This is a self-concordant barrier with parameter $\vartheta = 2$. The interior point method minimizes $f_0(x) + (1/\tau) \sum_i \phi_i(x)$, gradually increasing $\tau$. **SOCP solvers:** - **ECOS** - open-source, C, used by cvxpy by default for SOCP - **MOSEK** - commercial, fastest for large-scale problems - **SeDuMi** - historically first, MATLAB - **Clarabel** - modern open-source, Rust core, supports SOCP+SDP

Key ideas

• **SOCP = conic constraints:** $\|A_i x + b_i\|_2 \leq c_i^\top x + d_i$ defines convex conic sets. LP, QP, QCQP are all special cases of SOCP
• **Self-dual cone:** $(K_{SOC})^* = K_{SOC}$. The dual of SOCP is again SOCP. Strong duality holds under Slater condition
• **Interior point:** logarithmic barrier $-\log(t^2 - \|x\|^2)$ with parameter 2. ECOS, MOSEK, Clarabel solve in $O(n^{3.5})$ total operations
• **In practice:** cvxpy automatically recognizes cp.norm in constraints and builds SOCP. Portfolio risk, beamforming, trajectories - canonical applications

Related topics

SOCP occupies a central position in the hierarchy of convex programs:

• Semidefinite Programming (SDP) — SOCP is a subclass of SDP: SOC constraints are a special case of LMI
• Interior Point Methods — The main algorithm for SOCP uses self-concordant barriers
• Lagrange Duality — KKT conditions for SOCP use the dual cone of SOC

Вопросы для размышления

• Why does rocket landing require SOCP rather than LP? What changes in the physics when you add a thrust magnitude constraint?
• How does the portfolio problem change if you add a cardinality constraint (limit on the number of nonzero positions)?
• The second-order cone in R^(n+1) is self-dual. What does this imply about the geometry of the feasible region?

Связанные уроки

• cvx-03 — Convex sets and cones - foundation of SOCP
• cvx-04 — Lagrange duality, KKT conditions
• cvx-09 — SDP strictly generalizes SOCP
• cvx-05 — Interior point - the main solver for SOCP
• la-25-quadratic-forms