Convex Optimization на собеседовании

Преподаватель спрашивает про strong duality и Slater's condition. Интервьюер спрашивает: как сформулируешь robust portfolio для миллиона активов и какой solver выберешь? Эти два мира ожиданий - источник провалов на собеседованиях по convex optimization. Production требует не доказательств теорем, а быстрого распознавания формы задачи (LP, QP, SOCP, SDP), правильного routing к solver, и понимания где работает первый порядок, а где interior point. Здесь собран минимум, который реально проверяют в FAANG и quant-фондах.

• **CVXPY routing на production:** автоматический выбор solver (ECOS для SOCP, SCS для SDP, MOSEK для QP) - один и тот же DSL покрывает Stanford research и Two Sigma trading models
• **SVM at scale:** LinkedIn использует distributed QP-solver на миллионах профилей для skill-matching, dual decomposition по worker-нодам с ADMM-агрегацией
• **Robust portfolio at JPMorgan:** Markowitz с covariance uncertainty - SOCP, MOSEK решает за секунды для $n = 5000$ активов с десятью worst-case scenarios

Стандартные формы: LP, QP, SOCP, SDP

Convex optimization на собеседовании обычно начинается с одного вопроса: к какому стандартному классу сводится задача? Четыре основные формы образуют иерархию по выразительности: $\text{LP} \subset \text{QP} \subset \text{SOCP} \subset \text{SDP}$. Узнать форму - значит выбрать solver и ожидаемую сложность.

**Linear Program (LP):** $\min c^T x$ s.t. $Ax \le b$. Solver: simplex (Dantzig 1947) или interior point (Karmarkar 1984). **Quadratic Program (QP):** $\min \frac{1}{2} x^T Q x + c^T x$ при $Ax \le b$ с $Q \succeq 0$. **SOCP:** $\min c^T x$ при $\|A_i x + b_i\|_2 \le c_i^T x + d_i$. **SDP:** $\min C \cdot X$ при $A_i \cdot X = b_i$, $X \succeq 0$.

Где встречается в ML: SVM с soft margin - чистая QP с $n$ переменными ($n$ - размер обучающей выборки) в dual form. Robust portfolio optimization (Markowitz с uncertainty в covariance) - SOCP. Matrix completion для Netflix Prize - SDP-релаксация nuclear norm minimization. LASSO - QP с $\ell_1$-регуляризацией, переписываемой в LP-форме через расщепление переменных.

Кандидат может ошибиться, назвав задачу с $\ell_1$-нормой как QP. На самом деле $\|x\|_1$ кусочно-линейна, не квадратична - LASSO кодируется как QP только если есть $\frac{1}{2}\|Ax-b\|_2^2$ часть. Чистая $\min \|Ax-b\|_1$ - LP через переменные расщепления $x = u - v$, $u, v \ge 0$.

Дуальность: каждая задача имеет двойника

Лагранжиан задачи $\min f_0(x)$ при $f_i(x) \le 0$, $h_j(x) = 0$ - это $L(x, \lambda, \nu) = f_0(x) + \sum \lambda_i f_i(x) + \sum \nu_j h_j(x)$ с $\lambda_i \ge 0$. Dual function $g(\lambda, \nu) = \inf_x L(x, \lambda, \nu)$ всегда вогнута (как infimum линейных функций по $\lambda, \nu$), независимо от выпуклости primal.

Weak duality: $g(\lambda, \nu) \le p^*$ для любых допустимых $\lambda, \nu$. Strong duality: $\sup g = p^*$. Для convex задач Slater's condition (существует строго feasible точка во внутренности) гарантирует strong duality. Это причина, почему convex задачи решаемы через двойственность.

KKT-условия для convex задачи с strong duality эквивалентны оптимальности: stationarity ($\nabla_x L = 0$), primal feasibility ($f_i(x) \le 0$, $h_j(x) = 0$), dual feasibility ($\lambda_i \ge 0$), complementary slackness ($\lambda_i f_i(x) = 0$). Последнее - ключ к интерпретации: либо ограничение активно ($f_i = 0$), либо его множитель ноль.

Зачем dual в production: SVM dual имеет $n$ переменных вместо $d$ (чисел признаков может быть много меньше выборки), и kernel trick живёт именно в dual через $K_{ij} = \phi(x_i)^T \phi(x_j)$. Lagrangian relaxation в mixed integer programming раскладывает связные ограничения: каждое нарушение штрафуется через $\lambda$, основная задача распадается на независимые подзадачи.

Slater's condition не работает для задач с равенствами в форме $h_j(x) = 0$ при отсутствии строгого внутреннего решения. Для линейных равенств достаточно слабого условия (relative interior). На собеседовании правильный ответ: Slater для inequality-задач, refined Slater для линейных equality.

Выбор алгоритма: practical mapping

Выбор алгоритма зависит от scale и structure задачи. Шкала на собеседовании: до 10k переменных - interior point (CVXPY, MOSEK, ECOS), 10k-1M - first-order методы (FISTA, ADMM), миллион и выше - SGD-варианты или специализированные decomposition-схемы.

Interior Point с predictor-corrector (Mehrotra 1992) - polynomial complexity $O(\sqrt{n} \log(1/\epsilon))$ итераций, каждая - факторизация матрицы $O(n^3)$. Используется в MOSEK, CPLEX, Gurobi для medium-scale. Active set для small/medium QP (qpOASES). ADMM для distributed/parallel (cvx-07 covered).

First-order методы: gradient descent $O(1/\epsilon)$ итераций для convex, Nesterov acceleration $O(1/\sqrt{\epsilon})$, FISTA для composite (smooth + nonsmooth) задач. SGD для huge-scale convex с миллиардами примеров - $O(1/\sqrt{T})$ на каждый sample, амортизируется при streaming. Все first-order - GPU-friendly, основа PyTorch/TensorFlow optimizers.

На собеседовании частая ошибка: "для миллиард-переменной LP используйте simplex". Simplex имеет worst-case экспоненциальную сложность (Klee-Minty 1972) и плохо параллелится. Правильный ответ - decomposition + first-order или специализированный large-scale LP solver. Для structure LP (network flow, transportation) - алгоритмы с полиномиальной гарантией.

Real-world: SVM, robust regression, matrix completion

Конкретные ML-задачи и их convex-формулировки. SVM - QP в primal или dual (kernel trick). LASSO - composite optimization $\min \frac{1}{2}\|Ax-b\|_2^2 + \lambda \|x\|_1$, решается FISTA или coordinate descent (cvx-07). Robust regression: замена $\ell_2$ на Huber loss сохраняет выпуклость, защищает от выбросов.

Matrix completion (Netflix Prize): rank-минимизация NP-сложна, поэтому используется nuclear norm relaxation $\min \|X\|_*$ при $X_{ij} = M_{ij}$ для наблюдённых $(i,j)$. Это SDP по теореме Fazel-Hindi-Boyd (2001), решается Singular Value Thresholding (Cai-Candes-Shen 2010) - proximal-метод.

Trust Region Policy Optimization (Schulman et al. 2015) в RL формулирует обновление политики как convex подзадачу: квадратичная аппроксимация surrogate-награды плюс KL-ограничение на новую политику. Решается conjugate gradient на natural gradient direction. Это пример где convex optimization внутри nonconvex RL-цикла.

Production solver routing в CVXPY: ECOS для SOCP, SCS для SDP/large-scale через ADMM, MOSEK как commercial fallback для medium QP/SOCP. Для huge-scale custom proximal или first-order код в PyTorch обходит CVXPY overhead. JPMorgan использует MOSEK для robust portfolio optimization (SOCP с uncertainty sets).

Кандидат может перепутать convex relaxation с самой задачей. Nuclear norm $\|X\|_*$ - это convex envelope of rank function на unit ball spectral norm. Решение SDP даёт $X^*$ с минимальным nuclear norm, но не обязательно с минимальным rank. Гарантии recovery (Candes-Recht 2009): при достаточном числе наблюдений $m \gtrsim r n \log n$ решения совпадают с высокой вероятностью.

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

• **Иерархия LP $\subset$ QP $\subset$ SOCP $\subset$ SDP** определяет solver и сложность. SVM - QP, LASSO - composite QP, robust portfolio - SOCP, matrix completion - SDP. Распознать форму - первый шаг production-решения
• **Strong duality через Slater's condition** делает convex задачи решаемыми через dual. SVM dual с kernel trick, Lagrangian relaxation в integer programming, KKT как полные условия оптимальности - всё опирается на дуальность
• **Выбор алгоритма по scale:** до 10k - interior point (MOSEK), 10k-1M - first-order (FISTA, ADMM), миллиард - decomposition + SGD-варианты. Simplex для миллиарда переменных - типичная ошибка кандидата
• **Convex relaxations** (nuclear norm для rank, $\ell_1$ для cardinality) превращают NP-hard задачи в polynomial-time SDP/QP. Recovery guarantees Candes-Recht-Tao - часть стандартного интервью на ML-research позицию

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

Convex optimization на собеседовании пересекается с алгоритмами и приложениями:

• Проксимальные методы (cvx-07) — ISTA/FISTA/ADMM - основной алгоритмический класс для composite задач (LASSO, matrix completion); прокс-операторы как конструктивный примитив
• Градиентные методы и дуальность (cvx-04) — Базовая теория duality и градиентного спуска; SVM dual решается dual coordinate descent на SMO-варианте
• Online optimization (cvx-13) — Online vs batch convex - production splits: VW для streaming, MOSEK для batch portfolio. Разные алгоритмы под разные продакшн-сценарии
• SVD и low-rank approximation (la-15) — Nuclear norm minimization сводится к SDP через SVD-структуру; SVT-алгоритм - threshold на сингулярных значениях, прямое применение SVD

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

• На собеседовании дают задачу: ranking 100M документов с pairwise constraints. Как сформулировать как convex задачу, какой класс получится, и какой solver предложить? Где границы между convex relaxation и эвристикой?
• Convex теория обещает global optimum за polynomial time. Почему тогда deep learning - non-convex - работает лучше convex моделей на ImageNet? Где convex-теория всё ещё применяется внутри nonconvex pipeline?
• Кандидат говорит: "я обучу LASSO через SGD". Где здесь подвох: какие свойства LASSO теряются при наивном SGD, и какой proximal-вариант (proximal SGD или FISTA) даёт правильную sparsity?

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

• cvx-07 — Proximal methods are key algorithm class
• cvx-13 — Online vs batch convex - production splits
• lt-12-online-regret — Online optimization powers many production systems
• la-15-svd — Matrix factorization underlies many convex relaxations
• ig-09-mirror-descent — Mirror descent applies in convex
• calc-19-gradient