Линейное, квадратичное и полуопределённое программирование

Иерархия выпуклых задач

Выпуклое программирование — это «семейство» задач оптимизации различной сложности. Линейное программирование (ЛП) — простейшее: линейная цель, линейные ограничения. Квадратичное (КП) — квадратичная цель. Программирование второго порядка (SOCP) — конические ограничения. Полуопределённое (SDP) — матричные ограничения. Каждый следующий класс строго обобщает предыдущий. Понимание этой иерархии позволяет выбрать правильный инструмент для конкретной задачи.

Линейное программирование (ЛП)

Стандартная форма: min cᵀx при Ax ≤ b, x ≥ 0.

Здесь c ∈ ℝⁿ — вектор коэффициентов цели, A ∈ ℝ^{m×n} — матрица ограничений, b ∈ ℝᵐ — правые части.

Геометрия: область допустимых решений — выпуклый многогранник (политоп). Линейная целевая функция достигает минимума в вершине многогранника. Симплекс-метод (Данциг, 1947) «ходит» по вершинам, пока не найдёт оптимальную. Метод внутренней точки — движется через внутренность.

Двойственность ЛП: примальная задача min cᵀx при Ax ≥ b, x ≥ 0 имеет двойственную max bᵀy при Aᵀy ≤ c, y ≥ 0. Сильная двойственность выполнена всегда (при допустимости обеих задач).

Пример — задача о диете: минимизировать стоимость набора продуктов при условии получения достаточного количества питательных веществ. Это классическая ЛП-задача, решённая ещё в 1940-х годах.

Квадратичное программирование (КП)

Стандартная форма: min (1/2)xᵀPx + qᵀx при Ax ≤ b

P ∈ ℝ^{n×n} — матрица при квадратичном члене, должна быть ≽ 0 (положительно полуопределённой) для выпуклости задачи.

Почему ≽ 0? Квадратичная форма xᵀPx выпуклая тогда и только тогда, когда P ≽ 0. Критерий: все собственные значения ≥ 0.

Применение: Портфельная оптимизация Марковица

Дан набор активов с ожидаемыми доходностями μᵢ и ковариационной матрицей Σ. Задача: минимизировать риск wᵀΣw при обеспечении целевой доходности μᵀw ≥ r* и ограничении бюджета Σwᵢ = 1.

min (1/2)wᵀΣw при μᵀw ≥ r*, 1ᵀw = 1, w ≥ 0

Это КП! Ковариационная матрица Σ ≽ 0 по своей природе.

Применение: SVM

min (1/2)‖w‖² при yᵢ(wᵀxᵢ + b) ≥ 1 — строго выпуклое КП с уникальным решением.

Программирование второго порядка (SOCP)

Ограничение SOCP: ‖Aᵢx + bᵢ‖ ≤ cᵢᵀx + dᵢ — норма вектора ограничена линейной функцией x.

Геометрически: допустимое множество — пересечение конусов второго порядка с аффинными подпространствами.

Включает ЛП и КП: ЛП — частный случай (Aᵢ = 0, вырождается в линейное). КП с P ≽ 0 допускает SOCP-формулировку.

Пример: Robust линейное программирование

Имеем ЛП, но матрица A = Ā + δA содержит ошибку. Задача: min cᵀx при (Ā + δA)x ≤ b для всех ‖δA‖_F ≤ ρ.

Робастное ограничение: Āᵢᵀx + ρ‖xᵢ‖ ≤ bᵢ — это ограничение SOCP!

Полуопределённое программирование (SDP)

Задача SDP: min_{X} tr(CX) при tr(AᵢX) = bᵢ, i=1,...,m, X ≽ 0

где X — симметричная матрица n×n, X ≽ 0 означает положительную полуопределённость.

Переменная — матрица X! Это обобщение ЛП (переменная — вектор x) на матричный случай.

Почему это выпуклая задача? Множество ≽ 0 матриц — выпуклый конус. Целевая функция tr(CX) — линейная.

Полный разбор: SDP-релаксация задачи MAX-CUT

Задача: граф G = (V, E). Разбить вершины на два множества S и V∖S, максимизируя число рёбер между ними.

ЦЛП-формулировка: xᵢ ∈ {−1, +1}. Разрез: (1/4)Σ_{(i,j)∈E} (1 − xᵢxⱼ). NP-трудная.

SDP-релаксация (Гёманс-Вильямсон, 1995): заменяем xᵢ ∈ {±1} на векторы vᵢ ∈ ℝⁿ с ‖vᵢ‖ = 1. Произведение xᵢxⱼ → скалярное произведение vᵢᵀvⱼ. Матрица Yᵢⱼ = vᵢᵀvⱼ ≽ 0!

max (1/4)Σ_{(i,j)∈E}(1 − Yᵢⱼ) при Yᵢᵢ = 1, Y ≽ 0

Решение: это SDP! Рандомизированное округление (случайная гиперплоскость) даёт 0.878-аппроксимацию MAX-CUT.

Что это означает: алгоритм гарантированно находит разрез, составляющий не менее 87.8% от оптимального. Это лучший известный полиномиальный алгоритм.

Решатели

На практике задачи решаются специализированными пакетами:

CVXPY (Python): высокоуровневый язык для описания задач
MOSEK: коммерческий, очень быстрый для LP/QP/SOCP/SDP
SCS: открытый, масштабируемый для больших SDP
ECOS: эффективный для встроенных систем

Пример на CVXPY: x = cp.Variable(n); prob = cp.Problem(cp.Minimize(0.5*cp.quad_form(x,P) + q.T@x), [A@x <= b]); prob.solve()

Иерархия классов задач

Существует естественная иерархия выпуклых конических программ по выразительной силе и сложности: LP ⊂ QP ⊂ SOCP ⊂ SDP

Каждый следующий класс строго мощнее: SDP может выразить SOCP через стандартное вложение, SOCP включает QP с положительно полуопределёнными матрицами, QP включает LP. Сложность также растёт: LP решается за O(n^{3.5}) симплексом или внутренней точкой, QP — за O(n³), SOCP — за O(n^{3.5}), SDP — за O(n^{6.5}) для общих задач, хотя структурированные могут быть существенно быстрее.

Промышленные решатели

LP: Gurobi, CPLEX, MOSEK, HiGHS (open source) — миллионы переменных за секунды
QP: OSQP, qpOASES (для управления в реальном времени), Gurobi
SOCP: ECOS, MOSEK, SCS — широко используются в финансах для робастных портфелей
SDP: SDPT3, SeDuMi, MOSEK, COSMO — для задач до нескольких тысяч переменных
Универсальные моделирующие языки: CVXPY, JuMP, YALMIP — позволяют записать задачу в естественной форме и автоматически привести к канонической для решателя

Современные применения

LP в авиации: American Airlines решает задачи с миллионами переменных для назначения экипажей
QP в робототехнике: квадратурные регуляторы (LQR) и MPC (Model Predictive Control) — основа управления манипуляторами и квадрокоптерами
SOCP в финансах: робастные портфели Гольдфарба-Айенгара учитывают неопределённость в оценках доходностей через эллипсоидные множества
SDP в квантовых вычислениях: задачи квантовой томографии, оценки квантовых каналов формулируются через SDP
SDP в комбинаторике: релаксация Гёманса-Уильямсона для MAX-CUT даёт 0.878-аппроксимацию через SDP — рекордный результат теоретической информатики