Second-Order Cone Programming (SOCP)

1966 год: для расчёта траектории лунного модуля NASA инженеры проводят недели за вычислениями. 2015 год: SpaceX использует SOCP для посадки первых ступеней Falcon 9 в реальном времени - алгоритм Acikmese-Ploen решает задачу оптимального управления тягой за 3-5 мс на борту. Это стало возможным потому, что задача с ограничениями вида ||тяга|| <= максимум есть SOCP, а не произвольная нелинейная программа.

• **Посадка ракет SpaceX:** ограничение на тягу двигателя ||T|| <= T_max - конусное. Задача минимального расхода топлива при посадке решается как SOCP за миллисекунды
• **Антенные решётки 5G:** beamforming с гарантированным SNR для каждого пользователя - задача SOCP с комплексными переменными. Решается в реальном времени на базовых станциях
• **Робастная регрессия:** при неопределённости данных в шаре радиуса r в пространстве параметров наихудший случай задаётся нормой - это SOCP

Определение и конус второго порядка

1966 год: NASA готовит лунную программу. Инженеры вручную решают задачу минимального расхода топлива для посадочного модуля - задача с ограничениями на тягу двигателя, которые имеют вид норм. Спустя 50 лет та же задача формулируется как SOCP и решается за миллисекунды. SpaceX применяет это для посадки первых ступеней Falcon 9 в реальном времени.

Конус второго порядка (SOC) в пространстве $\mathbb{R}^{n+1}$ - это множество точек $(x, t)$, где $\|x\|_2 \leq t$. Визуально: в 3D это конус мороженого с вершиной в нуле. Формально это выпуклый замкнутый конус. LP работает с полупространствами (плоскими гранями). SOCP добавляет криволинейные конические ограничения - и при этом сохраняет полиномиальную сложность.

**Стандартная задача 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$ Ограничение $\|A_i x + b_i\|_2 \leq c_i^\top x + d_i$ требует, чтобы вектор $A_i x + b_i$ лежал внутри конуса: норма вектора ограничена линейной функцией. **Иерархия конических программ:** ``` LP ⊂ QP ⊂ QCQP ⊂ SOCP ⊂ SDP ``` Каждый класс строго шире предыдущего, но все решаются за полиномиальное время interior point методами.

Ключевые формулировки SOCP

Сила SOCP - в том, что многие прикладные задачи с норм-ограничениями сводятся к нему автоматически. Три канонических примера: робастная оптимизация с шаровой неопределённостью, минимальное время перевода орбиты, формирование диаграммы направленности антенной решётки.

**Задача 1 - Антенная решётка (beamforming):** Дано: $K$ антенн, $L$ пользователей. Вектор весов $w \in \mathbb{C}^K$. Мощность сигнала пользователю $l$: $|h_l^\top w|^2$. Задача: $\min_{w} \|w\|^2 \quad \text{s.t.} \quad |h_l^\top w| \geq \gamma_l, \; l=1,\ldots,L$ Ограничение $|h_l^\top w| \geq \gamma_l$ - это норм-ограничение, то есть SOCP. **Задача 2 - Минимальное время манёвра орбиты (Acikmese-Ploen 2007):** $\min T$ s.t. $\|T_t\|_2 \leq T_{max}, \; \ddot{r} = g + T_t/m$ Ограничение на тягу $\|T_t\|_2 \leq T_{max}$ - конусное. Именно эта формулировка лежит в основе алгоритма посадки Falcon 9.

Двойственность SOCP

Конус второго порядка является самодвойственным: $(K_{SOC})^* = K_{SOC}$. Это означает, что двойственная задача SOCP снова является SOCP - в отличие от, например, LP (двойственная к LP есть LP, но с транспонированными данными). Свойство самодвойственности упрощает анализ оптимальности и вывод KKT-условий.

**Двойственный конус SOC:** Для конуса $K = \{(x,t): \|x\|_2 \leq t\}$ двойственный конус: $K^* = \{(u, s): \sup_{(x,t) \in K} u^\top x + s \cdot t \leq 0\} = K$ **KKT-условия для SOCP:** для $i$-го конусного ограничения: 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}$, т.е. $\|\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$ Если primal строго выполнимо (interior point) - выполняется strong duality, зазор равен нулю.

Interior point для SOCP: вычислительная сторона

Interior point методы для SOCP работают за $O(\sqrt{n})$ итераций, каждая из которых стоит $O(n^3)$ (для плотных матриц). Итого $O(n^{3.5})$ для поиска решения с точностью $\varepsilon$, что на порядки быстрее наивного перебора. На практике ECOS решает задачи с тысячами переменных за секунды.

**Barrier function для SOC:** Для ограничения $\|x\|_2 \leq t$ используется логарифмический барьер: $\phi(x, t) = -\log(t^2 - \|x\|_2^2)$ Это самосогласованный барьер (self-concordant barrier) с параметром $\vartheta = 2$. Interior point метод минимизирует $f_0(x) + (1/\tau) \sum_i \phi_i(x)$ с постепенным увеличением $\tau$. **Солверы для SOCP:** - **ECOS** - открытый, C, используется cvxpy по умолчанию для SOCP - **MOSEK** - коммерческий, самый быстрый для крупных задач - **SeDuMi** - исторически первый, MATLAB - **Clarabel** - современный открытый, Rust-ядро, поддерживает SOCP+SDP

Ключевые идеи

• **SOCP = конусные ограничения:** $\|A_i x + b_i\|_2 \leq c_i^\top x + d_i$ задают выпуклые конусные множества. LP, QP, QCQP - частные случаи SOCP
• **Самодвойственный конус:** $(K_{SOC})^* = K_{SOC}$. Двойственная задача SOCP снова SOCP. Strong duality при условии Слейтера
• **Interior point:** логарифмический барьер $-\log(t^2 - \|x\|^2)$ с параметром 2. ECOS, MOSEK, Clarabel решают за $O(n^{3.5})$ общих операций
• **Практика:** cvxpy автоматически распознаёт cp.norm в ограничениях и строит SOCP. Портфельный риск, beamforming, траектории - канонические применения

Связанные темы

SOCP занимает центральное место в иерархии выпуклых программ:

• Semidefinite Programming (SDP) — SOCP - подкласс SDP: SOC-ограничение записывается как LMI
• Interior Point Methods — Основной алгоритм решения SOCP - self-concordant barriers
• Двойственность Лагранжа — KKT для SOCP используют двойственный конус SOC

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

• Почему для посадки ракеты нужен именно SOCP, а не LP? Что меняется в физике задачи при добавлении ограничения на тягу?
• Как изменится сложность задачи портфельной оптимизации, если добавить ограничение на количество ненулевых позиций (cardinality constraint)?
• Конус второго порядка в R^(n+1) самодвойственен. Что это говорит о геометрии пространства допустимых решений?

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

• cvx-03 — Выпуклые множества и конусы - фундамент SOCP
• cvx-04 — Двойственность Лагранжа, KKT-условия
• cvx-09 — SDP строго обобщает SOCP
• cvx-05 — Interior point - основной солвер для SOCP
• la-25-quadratic-forms