Квадратичное программирование 🎯

Когда ты запускаешь sklearn.svm.SVC().fit(X, y), внутри происходит не что-то похожее на градиентный спуск нейросети, а решение совершенно конкретной, строго определённой математической задачи: найти вектор множителей Лагранжа $\alpha$, который максимизирует квадратичную функцию при линейных ограничениях. Это не приближённая эвристика и не итеративное блуждание по ландшафту потерь в надежде на удачу — это задача из отдельного, хорошо изученного класса, для которого существуют алгоритмы с доказуемой сходимостью к глобальному оптимуму. Этот класс называется квадратичным программированием (Quadratic Programming, QP), и именно ему посвящён сегодняшний урок.

В уроке 281 ты разбирал симплекс-метод для линейного программирования — задачи, где и целевая функция, и ограничения линейны. В уроке 282 — двойственность, зеркальное отражение прямой задачи, которое для SVM неожиданно оказалось не просто удобной переформулировкой, а единственным практическим способом обучить модель с ядрами. Сегодня мы сделаем следующий логический шаг: разберём, что меняется, когда целевая функция перестаёт быть линейной и становится квадратичной, при этом ограничения остаются линейными. Разница выглядит небольшой на бумаге — одна степень у переменной вместо другой, — но она меняет саму геометрию задачи и требует новых алгоритмов взамен симплекс-метода.

Библиотеки libsvm и scikit-learn, обучая метод опорных векторов, под капотом не изобретают собственную магию — они вызывают QP-решатель (в случае libsvm это специализированный алгоритм SMO, «последовательная минимальная оптимизация», Sequential Minimal Optimization) именно потому, что двойственная задача SVM, выведенная в уроке 282 наполовину, оказывается классической задачей квадратичного программирования: квадратичной функцией от множителей Лагранжа $\alpha$ при линейных ограничениях на них. Сегодня мы доведём этот вывод до конца и явно покажем, какая матрица $Q$ стоит за этой квадратичной функцией и почему она гарантированно положительно полуопределена для любого ядра, удовлетворяющего теореме Мерсера.

К концу урока ты будешь понимать разницу между линейным и квадратичным программированием на уровне геометрии допустимой области и линий уровня целевой функции, уметь проверять выпуклость произвольной задачи КП через матрицу $Q$, самостоятельно выводить двойственную задачу SVM как задачу КП и понимать (на уровне интуиции, без глубокого вывода) принцип работы двух основных семейств алгоритмов решения QP — метода активного набора и методов внутренней точки.

История

Квадратичное программирование как самостоятельная область оптимизации оформилось практически сразу вслед за линейным. В 1956 году Гарри Марковиц, разрабатывая математическую теорию портфельной оптимизации, столкнулся с задачей, которую линейное программирование решить не могло в принципе: минимизировать дисперсию портфеля активов (величину принципиально квадратичную — сумму произведений весов и элементов ковариационной матрицы) при линейных ограничениях на состав портфеля и ожидаемую доходность. Марковиц вместе с Уильямом Уолфом предложил один из первых практических алгоритмов для этого класса задач — метод, основанный на модификации симплекс-метода для учёта квадратичного слагаемого, известный сегодня как критический линейный алгоритм (critical line algorithm). За эту работу, заложившую основы современной портфельной теории, Марковиц в 1990 году получил Нобелевскую премию по экономике.

Параллельно, в конце 1950-х и в 1960-х годах, Филип Уолф (Philip Wolfe) и Э. М. Л. Бил (E. M. L. Beale) формализовали условия оптимальности для задач КП и предложили метод активного набора ограничений (active set method) как естественное обобщение симплекс-метода на квадратичный случай. Идея была элегантной: раз симплекс-метод уже умеет угадывать, какие ограничения активны в оптимуме, для линейной задачи, — можно применить ту же логику к квадратичной, только внутри каждого «угадывания» решать не линейную, а квадратичную подзадачу.

Настоящий взрыв интереса к квадратичному программированию в машинном обучении произошёл в 1990-е годы благодаря Владимиру Вапнику и методу опорных векторов. Вапник и его коллеги сознательно сформулировали обучение SVM как задачу выпуклого квадратичного программирования — не потому, что это было единственно возможное решение задачи классификации, а потому, что выпуклая QP гарантировала то, чего не могли гарантировать нейросети того времени: единственный, глобально оптимальный, воспроизводимый результат обучения. Когда задачи стали настолько большими, что общие QP-солверы перестали справляться с миллионами обучающих примеров, Джон Платт в 1998 году предложил алгоритм SMO — метод, разбивающий гигантскую задачу QP на последовательность крошечных подзадач с двумя переменными, каждая из которых решается аналитически в закрытой форме. Именно алгоритм Платта и его модификации до сих пор работают внутри libsvm, а значит, и внутри sklearn.svm.SVC.

Постановка задачи квадратичного программирования и отличие от линейного программирования

Интуиция

В линейном программировании (урок 281) целевая функция линейна: её линии уровня — параллельные гиперплоскости, а допустимая область — многогранник, пересечение полупространств. Симплекс-метод работает именно потому, что можно строго доказать: оптимум линейной функции на многограннике всегда достигается в одной из его вершин, а значит, достаточно перебирать (умным образом) только вершины, а не всю бесконечную область.

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

Определение

Определение. Задачей квадратичного программирования (КП, QP) называется задача минимизации квадратичной функции при линейных ограничениях:

$$\min_{x \in \mathbb{R}^n} \quad \frac{1}{2} x^\top Q x + c^\top x$$$$\text{при ограничениях: } Ax \le b, \quad Ex = d$$

где $Q$ — симметричная матрица размера $n \times n$, $c \in \mathbb{R}^n$, а ограничения $Ax \le b$ и $Ex = d$ линейны (как и в линейном программировании из урока 281). Множитель $\frac{1}{2}$ перед квадратичной формой — стандартное соглашение: оно делает градиент целевой функции равным просто $Qx + c$, без лишнего множителя 2.

Обрати внимание: единственное формальное отличие от общей задачи линейного программирования — добавка $\frac{1}{2}x^\top Qx$ к целевой функции. Допустимая область по-прежнему многогранник (пересечение полупространств и гиперплоскостей задаёт выпуклое множество ровно так же, как в уроке 280) — меняется исключительно форма самой целевой функции, а вместе с ней и то, где именно внутри этого многогранника стоит искать минимум.

Примеры

Пример 1: минимум внутри многогранника, а не в вершине. Рассмотрим задачу $\min x_1^2 + x_2^2$ при ограничении $x_1 + x_2 \ge 1$. Целевая функция — сумма квадратов, $Q = 2I$ (единичная матрица с коэффициентом 2), безусловный минимум этой квадратичной формы находится в точке $(0,0)$ — но эта точка не удовлетворяет ограничению $x_1+x_2\ge1$. Значит, минимум задачи с ограничением лежит на границе допустимой области, на прямой $x_1+x_2=1$. Минимизируя $x_1^2+(1-x_1)^2$ по одной переменной, получаем $x_1^*=0{,}5$, значит оптимум находится в точке $(0{,}5,\ 0{,}5)$ — это середина ребра допустимой области, а не какая-либо вершина. Если бы это была задача линейного программирования с той же допустимой областью (например, при дополнительных ограничениях $x_1\le1$, $x_2\le1$, задающих треугольник с вершинами $(1,0)$, $(0,1)$, $(1,1)$), оптимум линейной целевой функции обязан был бы попасть в одну из этих трёх вершин — но оптимум квадратичной функции сознательно «выбрал» середину стороны, не совпадающую ни с одной вершиной.

Пример 2: портфель Марковица. Инвестор распределяет капитал между активами с весами $x = (x_1, \dots, x_n)$, $\sum_i x_i = 1$, $x_i \ge 0$ (запрет коротких позиций). Дисперсия портфеля равна $x^\top \Sigma x$, где $\Sigma$ — ковариационная матрица доходностей активов. Задача Марковица — минимизировать риск при ограничении на ожидаемую доходность $\mu^\top x \ge r_{\min}$:

Это классическая задача КП: $Q = \Sigma$, целевая функция квадратична, все три группы ограничений линейны. В отличие от линейной задачи распределения ресурсов (урок 280), оптимальный портфель здесь почти никогда не сосредоточен в одном-двух активах (что соответствовало бы «вершине» допустимой области) — как раз наоборот, минимизация дисперсии обычно требует диверсификации, распределения капитала по многим активам сразу, потому что именно так уменьшается сумма попарных ковариаций в квадратичной форме. Оптимум типично лежит внутри многогранника допустимых весов, а не на его границе.

Пример 3: прямая задача мягкого зазора SVM. Прямая (не двойственная) задача обучения SVM с мягким зазором сама по себе — задача КП относительно переменных $(w, b, \xi)$:

Целевая функция квадратична по $w$ (и линейна по $\xi$), а ограничения линейны по всем переменным $(w,b,\xi)$ сразу. Формально эту задачу уже можно было бы отдать общему QP-решателю без перехода к двойственной форме — но число переменных здесь растёт вместе с размерностью признакового пространства $d$ (плюс одна переменная $\xi_i$ на каждый обучающий пример), а при переходе к ядрам (как ты помнишь из урока 282) размерность признакового пространства может быть даже бесконечной. Именно поэтому на практике решают не эту прямую задачу, а двойственную — к её полному выводу мы вернёмся в третьем блоке этого урока.

Почему это важно

Понимание того, что оптимум КП может оказаться где угодно — внутри области, на грани произвольной размерности или в вершине, — объясняет, почему для КП нельзя напрямую использовать симплекс-метод: сама идея «перебирать только вершины» перестаёт быть корректной стратегией. Нужен принципиально другой алгоритмический аппарат, который умеет работать и с гранями, и с внутренностью допустимой области, — именно к нему мы перейдём в последнем блоке урока, после того как разберёмся с условием выпуклости задачи.

Выпуклость задачи КП: положительная полуопределённость матрицы $Q$

Интуиция

В уроке 278 ты доказал общую теорему: у выпуклой функции любой локальный минимум является глобальным, а критерий выпуклости дважды дифференцируемой функции — положительная полуопределённость её гессиана в каждой точке. У квадратичной формы $f(x) = \frac{1}{2}x^\top Qx + c^\top x$ есть особенность, которая делает применение этого критерия предельно простым: её гессиан равен $Q$ и не зависит от точки $x$ вообще. В отличие от MSE и логистической регрессии из урока 278, где гессиан приходилось вычислять как отдельную матрицу для каждой конкретной модели данных, здесь достаточно проверить знакоопределённость одной-единственной матрицы — и это сразу говорит о выпуклости целевой функции на всём пространстве, без единого исключения.

Определение

Критерий выпуклости КП. Задача квадратичного программирования $\min \frac{1}{2}x^\top Qx + c^\top x$ при линейных ограничениях выпукла тогда и только тогда, когда матрица $Q$ положительно полуопределена ($Q \succeq 0$, то есть $v^\top Q v \ge 0$ для любого $v \in \mathbb{R}^n$). Допустимая область, заданная линейными ограничениями $Ax \le b$, $Ex = d$, всегда выпукла как пересечение полупространств и гиперплоскостей (это установлено ещё в уроке 277) — независимо от знакоопределённости $Q$. Значит, единственное условие, которое требуется проверить для выпуклости всей задачи КП, — это знакоопределённость матрицы $Q$.

Если $Q \succeq 0$, задача выпуклая КП: по теореме урока 278 любой локальный минимум автоматически оказывается глобальным, а значит, алгоритмы решения (метод активного набора, методы внутренней точки) могут гарантированно находить именно глобальный оптимум. Если же $Q$ не является положительно полуопределённой (у неё есть хотя бы одно отрицательное собственное значение), задача называется невыпуклой КП — и, за исключением отдельных частных случаев, поиск глобального оптимума такой задачи NP-труден: к невыпуклой QP сводится, например, классическая NP-трудная задача MAX-CUT (задача о максимальном разрезе графа).

Примеры

Пример 1: ковариационная матрица Марковица всегда положительно полуопределена. Для любой ковариационной матрицы $\Sigma$ и любого вектора весов $v$ выполняется $v^\top \Sigma v = \operatorname{Var}(v^\top X) \ge 0$, потому что дисперсия любой случайной величины (в данном случае — доходности портфеля с весами $v$) не может быть отрицательной. Это тот же самый приём, что и с $X^\top X \succeq 0$ в MSE из урока 278: $\Sigma \succeq 0$ для абсолютно любого набора активов, без единого дополнительного условия на данные. Значит, задача Марковица — выпуклая КП всегда, и метод внутренней точки, разбираемый ниже, гарантированно найдёт её глобальный оптимум.

Пример 2: гессиан прямой задачи SVM. В прямой задаче $\frac{1}{2}\|w\|^2 + C\sum_i\xi_i$ по переменным $(w,b,\xi)$ гессиан — блочно-диагональная матрица: единичный блок $I_d$ по переменным $w$ и нулевые блоки по $b$ и по всем $\xi_i$ (линейная часть $C\sum\xi_i$ не даёт вклада во вторую производную). Такая блочно-диагональная матрица положительно полуопределена (собственные значения — единицы из блока $I_d$ и нули из остальных блоков, отрицательных нет), но не положительно определена строго — из-за нулевых блоков. Задача выпуклая, но не строго выпуклая: по теореме урока 278 оптимальный вектор весов $w^*$ единственен (блок по $w$ строго положительно определён), а вот пара $(b^*, \xi^*)$, дающая то же самое минимальное значение целевой функции, в принципе может быть не единственной — на практике значение $b^*$ дополнительно фиксируется через условия дополняющей нежёсткости (complementary slackness) на опорных векторах.

Пример 3: невыпуклая КП — почему авторы задач избегают индефинитной $Q$. Возьмём $Q = \operatorname{diag}(2, -2)$ — знаконеопределённую матрицу (в точности гессиан седловой функции $x_1^2 - x_2^2$ из урока 278). Задача $\min x_1^2 - x_2^2$ при, скажем, $-1 \le x_1, x_2 \le 1$ не выпукла: критерий урока 278 нарушен, и на границе допустимой области у такой задачи могут быть сразу несколько точек, локально удовлетворяющих условиям оптимальности первого порядка, но с разными значениями целевой функции — общий QP-солвер, рассчитанный на выпуклый случай, не даёт гарантии найти среди них именно глобально наилучшую. Именно поэтому и Марковиц, конструируя целевую функцию через ковариационную матрицу, и Вапник, конструируя SVM через норму $\|w\|^2$ и матрицу Грама (пример из следующего блока), сознательно выбирали такую форму задачи, у которой $Q$ положительно полуопределена по построению, — это не случайное совпадение удачных примеров, а обязательное инженерное требование к любой задаче, которую хочется надёжно решать.

Почему это важно

То, что гессиан квадратичной формы постоянен и не зависит от $x$, превращает проверку выпуклости КП из потенциально трудоёмкой аналитической задачи (как в общем случае из урока 278, где для каждой новой функции потерь нужно заново вычислять гессиан) в разовую алгебраическую проверку одной матрицы. Ровно на этом основаны все современные библиотеки решения QP (quadprog, OSQP, cvxopt.solvers.qp): прежде чем гарантировать сходимость к глобальному минимуму, они либо требуют от пользователя подтверждения, что $Q \succeq 0$, либо сами это проверяют — а если условие нарушено, честно сообщают, что найденное решение может оказаться лишь локальным.

Двойственная задача SVM как задача квадратичного программирования

Интуиция

В уроке 282 ты уже видел финальную формулу двойственной задачи SVM без подробного вывода — сейчас мы восстановим этот вывод шаг за шагом и явно покажем, что получившаяся задача — это именно задача КП в смысле определения из первого блока этого урока, с явной матрицей $Q$, вектором $c$ и линейными ограничениями. Идея перехода к двойственной задаче та же, что и в уроке 282: прямая задача SVM растёт по числу переменных вместе с размерностью признакового пространства, а при использовании ядер (kernel trick) эта размерность может быть неограниченно велика или даже бесконечна (как у RBF-ядра). Двойственная задача, наоборот, имеет ровно $N$ переменных — по одному множителю Лагранжа $\alpha_i$ на каждый из $N$ обучающих примеров, — независимо от размерности признакового пространства. Именно эта независимость и делает возможным обучение SVM с ядрами на практике.

Определение

Двойственная задача SVM — задача квадратичного программирования относительно вектора множителей Лагранжа $\alpha = (\alpha_1, \dots, \alpha_N)$:

$$\max_\alpha \ \sum_{i=1}^N \alpha_i - \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_j y_i y_j \langle x_i, x_j\rangle$$$$\text{при } 0 \le \alpha_i \le C \ \text{ для всех } i, \qquad \sum_{i=1}^N \alpha_i y_i = 0$$

Переписывая как задачу минимизации в стандартной форме из первого блока: $\min_\alpha \frac{1}{2}\alpha^\top Q\alpha - \mathbf{1}^\top\alpha$, где $Q_{ij} = y_i y_j \langle x_i, x_j\rangle$, при ограничениях $0 \le \alpha_i \le C$ (два линейных неравенства на каждую переменную, так называемые box-ограничения, то есть двусторонние ограничения-«коробки») и одном линейном равенстве $\sum_i \alpha_i y_i = 0$.

Вывод (полный)

Начнём с прямой задачи мягкого зазора, уже знакомой из первого блока:

Составим лагранжиан с множителями $\alpha_i \ge 0$ на ограничения зазора и $\mu_i \ge 0$ на ограничения $\xi_i \ge 0$:

По методологии урока 282 (двойственная функция — это минимум лагранжиана по прямым переменным) приравняем к нулю частные производные по $w$, $b$ и $\xi_i$:

Из последнего условия и $\mu_i \ge 0$ сразу следует $\alpha_i \le C$ — вот откуда берётся верхняя граница box-ограничения (эта граница — прямое следствие штрафа $C$ за нарушение зазора, и её нет в задаче с жёстким зазором, где $C=\infty$). Подставим найденное выражение $w = \sum_i \alpha_i y_i x_i$ обратно в лагранжиан. Слагаемое $\frac{1}{2}\|w\|^2$ превращается в $\frac{1}{2}\sum_i\sum_j \alpha_i\alpha_j y_iy_j\langle x_i,x_j\rangle$, слагаемое с $b$ обнуляется благодаря условию $\sum_i\alpha_iy_i=0$, а слагаемые с $\xi_i$ и $\mu_i$ взаимно сокращаются (поскольку $C - \alpha_i - \mu_i = 0$). После всех сокращений остаётся ровно двойственная функция

которую нужно максимизировать при $0\le\alpha_i\le C$ и $\sum_i\alpha_iy_i=0$ — это в точности формула из определения выше. Обрати внимание: данные $x_i$ входят в итоговую задачу только через скалярные произведения $\langle x_i, x_j\rangle$ — ни разу по отдельности. Это и есть та самая «магия» из урока 282, доведённая теперь до конкретной формулы: раз скалярное произведение — единственное место, где участвуют признаки объектов, его можно заменить на значение произвольного ядра $K(x_i,x_j)$ без изменения структуры задачи КП.

Примеры

Пример 1: матрица $Q$ через ядерную матрицу Грама. Определим $K$ как матрицу Грама, $K_{ij}=\langle x_i,x_j\rangle$ (или $K_{ij}=K(x_i,x_j)$ для произвольного ядра), и $D_y = \operatorname{diag}(y_1,\dots,y_N)$. Тогда $Q = D_y K D_y$. По теореме Мерсера ядерная матрица Грама $K$ всегда положительно полуопределена для допустимого ядра (это в точности условие, которое отличает «настоящее» ядро от произвольной функции сходства). Проверим, что $Q$ тоже положительно полуопределена: для любого $v$,

поскольку $K \succeq 0$, а $(D_yv)$ — это просто ещё один вектор в $\mathbb{R}^N$. Значит, двойственная задача SVM — выпуклая КП для любого ядра, удовлетворяющего теореме Мерсера, будь то линейное, полиномиальное или RBF-ядро с бесконечномерным признаковым пространством. Это прямой аналог того, как $X^\top X\succeq0$ гарантировала выпуклость MSE в уроке 278 при любых данных, — здесь ту же роль для SVM играет свойство Мерсера ядра.

Пример 2: числовой пример с двумя точками. Возьмём два линейно разделимых объекта: $x_1=(1,1)$, $y_1=+1$ и $x_2=(-1,-1)$, $y_2=-1$, и задачу с жёстким зазором ($C=\infty$, ограничение $\alpha_i\le C$ не активно). Скалярные произведения: $\langle x_1,x_1\rangle=2$, $\langle x_2,x_2\rangle=2$, $\langle x_1,x_2\rangle=-2$. Матрица $Q$: $Q_{11}=y_1y_1\cdot2=2$, $Q_{22}=y_2y_2\cdot2=2$, $Q_{12}=Q_{21}=y_1y_2\cdot(-2)=(-1)\cdot(-2)=2$. Ограничение равенства: $\alpha_1 y_1+\alpha_2y_2=0 \Rightarrow \alpha_1=\alpha_2$. Подставляя $\alpha_1=\alpha_2=\alpha$ в целевую функцию $g(\alpha)=(\alpha_1+\alpha_2) - \frac12(Q_{11}\alpha_1^2+2Q_{12}\alpha_1\alpha_2+Q_{22}\alpha_2^2)$, получаем $g=2\alpha-\frac12(2\alpha^2+4\alpha^2+2\alpha^2)=2\alpha-4\alpha^2$. Максимум: $\frac{dg}{d\alpha}=2-8\alpha=0 \Rightarrow \alpha^*=0{,}25$. Тогда $w^*=\alpha_1y_1x_1+\alpha_2y_2x_2=0{,}25(1,1)+0{,}25(1,1)=(0{,}5,\,0{,}5)$ (второе слагаемое: $0{,}25\cdot(-1)\cdot(-1,-1)=(0{,}25,0{,}25)$, сумма даёт $(0{,}5,0{,}5)$), $\|w^*\|=\frac{\sqrt2}{2}$, а ширина зазора $\frac{2}{\|w^*\|}=2\sqrt2$ — ровно расстояние между двумя обучающими точками, что и ожидается для минимального разделяющего примера из двух объектов.

Пример 3: почему нельзя оптимизировать один $\alpha_i$ за раз. Из-за линейного ограничения равенства $\sum_i\alpha_iy_i=0$ нельзя изменить единственную координату $\alpha_k$, зафиксировав все остальные, — любое такое изменение немедленно нарушит ограничение равенства (если только $y_k$ не домножается на компенсирующее изменение какого-то другого $\alpha_j$). Минимальный «блок», который можно менять, не выходя за пределы допустимой области, — это ровно пара переменных $(\alpha_i, \alpha_j)$, у которых изменения взаимно компенсируют друг друга. Это прямое объяснение того, почему алгоритм SMO Джона Платта решает подзадачи именно из двух переменных за раз, а не из одной, — такова структура ограничений, а не произвольный выбор автора алгоритма.

Почему это важно

Обучение SVM на практике — это в буквальном смысле слова решение задачи квадратичного программирования, а не какая-то отдельная, специфичная только для SVM процедура. Когда ты вызываешь sklearn.svm.SVC(kernel='rbf').fit(X, y), внутри вызывается libsvm, который собирает матрицу $Q=D_yKD_y$ (или, чаще, её отдельные строки по требованию, чтобы не хранить целиком гигантскую матрицу $N\times N$) и запускает SMO — специализированный QP-решатель под структуру box-ограничений и одного линейного равенства. Гарантия глобальной оптимальности найденного решения — не эмпирическое наблюдение, а прямое следствие двух фактов, доказанных в этом уроке: допустимая область (box-ограничения плюс гиперплоскость) выпукла всегда, а матрица $Q$ положительно полуопределена для любого допустимого ядра.

Общие подходы к решению задачи КП

Интуиция

Раз оптимум КП может лежать где угодно — внутри области, на грани произвольной размерности или в вершине, — единой стратегии «обходи только вершины», как в симплекс-методе, недостаточно. Сложились два принципиально разных семейства алгоритмов. Первое — метод активного набора (active set method) — прямое обобщение логики симплекс-метода: угадываем, какие ограничения-неравенства выполняются как равенства в оптимуме (то есть «активны»), решаем получившуюся задачу с одними лишь равенствами, проверяем условия оптимальности и по необходимости добавляем или убираем ограничения из набора, повторяя процесс. Второе семейство — методы внутренней точки (interior-point methods) — устроено принципиально иначе: вместо движения по границе допустимой области (вдоль рёбер и вершин) траектория алгоритма идёт строго через внутренность многогранника, никогда не касаясь границы до самого конца, а близость к границе штрафуется специальной барьерной функцией.

Определение

Метод активного набора. На каждой итерации фиксируется текущее предположение о наборе активных ограничений $\mathcal{A}$ (тех, что выполняются как равенства). Задача КП с ограничениями только из $\mathcal{A}$, взятыми как равенства, сводится к системе линейных уравнений через условия Каруша — Куна — Таккера (урок 279). Если решение этой системы допустимо (не нарушает остальные, неактивные ограничения) и знаки множителей Лагранжа при активных ограничениях-неравенствах верны, процесс останавливается — найден оптимум. Иначе набор $\mathcal{A}$ корректируется (ограничение добавляется или убирается), и итерация повторяется.

Методы внутренней точки. Строго допустимая (внутренняя) точка $x^{(0)}$ последовательно уточняется, минимизируя целевую функцию с добавленным логарифмическим барьером $-\mu\sum_i \log(b_i - a_i^\top x)$, который резко возрастает при приближении к любой границе $a_i^\top x = b_i$. Параметр барьера $\mu$ постепенно уменьшается от итерации к итерации; последовательность решений «барьерных» подзадач образует так называемый центральный путь (central path), который сходится к истинному оптимуму исходной задачи КП за полиномиальное число итераций.

Примеры

Пример 1: активный набор на задаче из первого блока. Вернёмся к $\min x_1^2+x_2^2$ при $x_1+x_2\ge1$. Начальная гипотеза: ограничение неактивно ($\mathcal{A}=\varnothing$). Безусловный минимум $(0,0)$ не удовлетворяет ограничению — гипотеза неверна. Обновляем набор: ограничение становится активным, решаем задачу с равенством $x_1+x_2=1$ через множитель Лагранжа $\lambda$: условия стационарности дают $2x_1=\lambda$, $2x_2=\lambda$, откуда $x_1=x_2$, а из $x_1+x_2=1$ получаем $x_1=x_2=0{,}5$ — тот же ответ, что и в первом блоке, но теперь получен через формальную процедуру активного набора, которая обобщается на произвольное число ограничений.

Пример 2: SMO как специализированный метод активного набора. Алгоритм SMO для SVM устроен как крайний, вырожденный случай метода активного набора: на каждой итерации «активной» объявляется ровно одна пара переменных $(\alpha_i,\alpha_j)$, задача для этой пары решается аналитически в закрытой форме (это одномерная задача после подстановки ограничения равенства), остальные $N-2$ переменных фиксируются. Такая специализация возможна именно потому, что структура ограничений двойственной задачи SVM исключительно проста (box-ограничения плюс одно линейное равенство) — для КП с более сложными, произвольными линейными ограничениями общий метод активного набора приходится применять без такого упрощения.

Пример 3: методы внутренней точки для задачи Марковица. Промышленные инструменты портфельной оптимизации при большом числе активов (сотни и тысячи бумаг) типично используют методы внутренней точки, а не активный набор: число возможных комбинаций активных ограничений в задаче Марковица растёт экспоненциально с числом активов, что делает метод активного набора практически медленным на таких масштабах, тогда как методы внутренней точки гарантируют сходимость за число итераций, растущее лишь полиномиально (обычно логарифмически) с размером задачи. Именно поэтому солверы вроде cvxopt.solvers.qp или OSQP, используемые в библиотеках финансовой оптимизации, по умолчанию реализуют именно эту стратегию.

Почему это важно

Выбор между методом активного набора и методом внутренней точки на практике определяется масштабом и структурой конкретной задачи: активный набор эффективен, когда заранее ожидается, что в оптимуме активна лишь небольшая доля ограничений (типичная ситуация для SVM — большинство $\alpha_i$ обнуляются, «выживают» только множители опорных векторов), а методы внутренней точки предпочтительны для больших плотных задач общего вида, где число потенциально активных ограничений велико. Понимание этой развилки на уровне интуиции — не праздное любопытство, а прямое объяснение того, почему libsvm использует SMO (специализированную версию активного набора) вместо общего солвера внутренней точки: разработчики библиотеки эксплуатируют специфическую разреженную структуру решения SVM, которую общий QP-солвер не умеет использовать сам по себе.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Запиши задачу $\min 3x_1^2 + 2x_2^2$ при $x_1+x_2=1$ в стандартной форме КП, явно указав матрицу $Q$ и вектор $c$.

Задание 2: Проверь, положительно ли определена матрица $Q=\begin{pmatrix}4&1\\1&3\end{pmatrix}$, вычислив её собственные значения (или воспользовавшись критерием угловых миноров).

Задание 3: Чем принципиально отличается допустимая область задачи КП от допустимой области задачи ЛП с теми же линейными ограничениями?

Задание 4: Для $\min x_1^2+x_2^2$ при $x_1+2x_2\ge2$ найди точку оптимума и укажи, лежит ли она в вершине, на грани или внутри допустимой полуплоскости.

Задание 5: Ковариационная матрица трёх активов равна $\Sigma=\begin{pmatrix}0{,}04&0{,}01&0\\0{,}01&0{,}09&0\\0&0&0{,}01\end{pmatrix}$. Является ли задача Марковица с этой матрицей выпуклой?

Задание 6: Гессиан прямой задачи SVM по переменным $(w,b,\xi)$ — блочно-диагональная матрица $\operatorname{diag}(I_d, 0, 0,\dots,0)$. Положительно ли она определена? Положительно ли полуопределена?

Задание 7: В двойственной задаче SVM ограничение $\sum_i \alpha_i y_i = 0$ линейно. Почему оно не превращает задачу в задачу ЛП?

Задание 8: Объясни своими словами, почему box-ограничения $0\le\alpha_i\le C$ в двойственной задаче SVM возникают именно из штрафа $C\sum\xi_i$ в прямой задаче.

Задание 9: Задача $\min x_1^2-x_2^2$ при линейных ограничениях — выпуклая или невыпуклая КП? Обоснуй через матрицу $Q$.

Задание 10: Почему методы внутренней точки называются именно так — что они делают иначе по сравнению с методом активного набора?

Средние задания (11–20)

Задание 11: Для матрицы Грама $K=\begin{pmatrix}2&-2\\-2&2\end{pmatrix}$ и меток $y=(1,-1)$ вычисли матрицу $Q=D_yKD_y$ двойственной задачи SVM.

Задание 12: Докажи, что $Q=D_yKD_y$ положительно полуопределена, если $K\succeq0$, для произвольных $y_i\in\{-1,+1\}$ и произвольной размерности $N$.

Задание 13: Почему теорема Мерсера важна именно для гарантии выпуклости двойственной задачи SVM, а не просто «для того чтобы ядро работало»?

Задание 14: В прямой задаче Марковица добавь ограничение $x_i \le 0{,}4$ для каждого актива (лимит на долю одного актива в портфеле). Останется ли задача выпуклой КП?

Задание 15: Реши задачу $\min x_1^2+2x_2^2$ при $x_1+x_2=1$ методом множителей Лагранжа (это эквивалент шага метода активного набора при активном ограничении-равенстве).

Задание 16: Двойственная задача SVM с жёстким зазором (hard margin, $C=\infty$) для трёх точек: $x_1=(0,0)$, $y_1=-1$; $x_2=(2,0)$, $y_2=+1$; $x_3=(4,0)$, $y_3=+1$. Заметь, что эти точки лежат на одной прямой (одномерная задача классификации). Какая из точек, скорее всего, окажется НЕ опорным вектором и почему (без полного решения QP)?

Задание 17: Почему в SMO нельзя обновлять только $\alpha_i$, оставляя все остальные $\alpha_j$ ($j\ne i$) неизменными?

Задание 18: Сформулируй задачу Ridge-регрессии с ограничением неотрицательности весов ($w_i\ge0$ для всех $i$, non-negative least squares, то есть метод наименьших квадратов с неотрицательными весами) как задачу КП, указав $Q$ и $c$.

Задание 19: Объясни, почему в общем случае метод активного набора требует итеративной корректировки набора $\mathcal{A}$, а не находит правильный набор ограничений сразу за один шаг.

Задание 20: Портфель из двух активов с $\Sigma=\begin{pmatrix}0{,}04&0{,}02\\0{,}02&0{,}01\end{pmatrix}$, ограничение $x_1+x_2=1$, $x_i\ge0$. Найди портфель минимальной дисперсии (без ограничения на доходность), решив задачу через множитель Лагранжа для равенства и проверку неотрицательности.

Продвинутые задания (21–30)

Задание 21: Докажи, что если $Q\succ0$ (строго положительно определена) и допустимая область непуста, то задача КП имеет единственное решение.

Задание 22: В задаче $\min\frac12x^\top Qx+c^\top x$ без ограничений при $Q\succ0$ найди аналитическое решение через градиент.

Задание 23: Покажи, что условия KKT для задачи КП с одним ограничением-равенством $Ex=d$ и без неравенств сводятся к системе линейных уравнений (в отличие от общего нелинейного случая KKT из урока 279).

Задание 24: Опираясь на предыдущее задание, объясни, почему метод активного набора для КП значительно проще в реализации, чем аналог для задачи общего вида с нелинейной целевой функцией.

Задание 25: Двойственная задача SVM с ядром RBF $K(x_i,x_j)=\exp(-\gamma\|x_i-x_j\|^2)$. Объясни, почему увеличение параметра $\gamma$ не влияет на выпуклость задачи, но влияет на её решение.

Задание 26: Приведи содержательный контрпример: опиши (без явного построения) ситуацию, в которой задача КП имеет несколько разных точек глобального минимума с одинаковым значением целевой функции.

Задание 27: Задача КП имеет $N=10\,000$ переменных, но, как ожидается, в оптимуме активно лишь около 50 ограничений (разреженное решение, как в SVM). Какой из двух подходов — метод активного набора или общий метод внутренней точки — скорее всего окажется эффективнее, и почему?

Задание 28: Объясни, почему условие $Q\succeq0$ проверяется один раз для всей задачи КП, тогда как в общей (не квадратичной) выпуклой задаче условие $\nabla^2f(x)\succeq0$ пришлось бы в принципе проверять в каждой точке $x$ отдельно.

Задание 29: Задача КП имеет $Q\succeq0$, но $Q$ вырождена (есть нулевое собственное значение), и вектор $c$ не ортогонален соответствующему собственному вектору. Покажи на общих соображениях, что задача без ограничений в этом случае вообще не имеет минимума (целевая функция неограничена снизу).

Задание 30: Сформулируй своими словами, почему теорема Мерсера — это ровно то условие, которое гарантирует, что любой выбор ядра в SVM (лишь бы оно удовлетворяло теореме) сохраняет всю доказанную в этом уроке цепочку гарантий: выпуклость, единственность значения минимума, применимость QP-солверов.

Частые ошибки

Ошибка 1. Считают, что раз ограничения в задаче КП линейны (как и в ЛП), то оптимум обязан находиться в вершине допустимого многогранника — по аналогии с симплекс-методом.

Как выглядит: «допустимая область — многогранник, значит решение должно быть в одной из его вершин, как в линейном программировании».

Почему возникает: привычка из уроков 280–281, где именно ограничения (а не целевая функция) определяли структуру допустимой области, и там оптимум действительно всегда в вершине.

Как правильно: теорема «оптимум в вершине» верна только для линейной целевой функции; для квадратичной целевой функции оптимум может лежать где угодно — внутри области, на грани произвольной размерности или в вершине, — в зависимости от того, куда «указывает» безусловный минимум квадратичной формы относительно многогранника.

Ошибка 2. Путают положительную полуопределённость матрицы $Q$ с требованием, чтобы все её элементы были неотрицательны.

Как выглядит: «в матрице $Q$ есть отрицательные числа вне диагонали — значит, задача невыпуклая».

Почему возникает: интуитивное (и неверное) обобщение свойства «неотрицательности» с чисел на матрицы напрямую, без учёта того, что положительная полуопределённость — свойство квадратичной формы $v^\top Qv$ для всех векторов $v$, а не отдельных элементов матрицы.

Как правильно: матрица $Q=\begin{pmatrix}2&2\\2&2\end{pmatrix}$ из числового примера SVM этого урока содержит только положительные элементы и при этом вырождена (одно нулевое собственное значение), а матрица с отрицательными внедиагональными элементами вполне может быть положительно определена (как в задании 2); знакоопределённость нужно проверять через собственные значения или критерий угловых миноров, а не «на глаз» по знакам элементов.

Ошибка 3. Считают, что переход от прямой задачи SVM к двойственной — чисто техническое упрощение, не меняющее содержательного смысла задачи.

Как выглядит: «двойственная задача — это то же самое, просто записанное иначе, выбор любой из форм равноценен».

Почему возникает: верно, что при сильной двойственности оптимальные значения обеих задач совпадают (урок 282), и это легко спутать с полной эквивалентностью всех аспектов постановки.

Как правильно: число переменных различается принципиально ($d+1+N$ в прямой задаче против $N$ в двойственной), а главное — только двойственная форма делает возможным ядерный трюк, поскольку лишь в ней данные входят исключительно через скалярные произведения; при переходе к ядрам с бесконечномерным признаковым пространством прямую задачу в её явном виде решить попросту невозможно.

Ошибка 4. Считают, что раз задача КП выпуклая, любой алгоритм (включая обычный градиентный спуск без учёта ограничений) автоматически найдёт правильный ответ.

Как выглядит: «функция выпуклая — запущу обычный градиентный спуск по $\alpha$ и получу решение двойственной задачи SVM».

Почему возникает: смешение двух разных гарантий из урока 278: выпуклость гарантирует, что если алгоритм сойдётся к точке с нулевым градиентом (или к точке, удовлетворяющей условиям KKT), эта точка будет глобальным оптимумом — но не гарантирует, что наивный градиентный спуск без учёта ограничений вообще останется в допустимой области.

Как правильно: ограничения $0\le\alpha_i\le C$ и $\sum_i\alpha_iy_i=0$ обязаны учитываться алгоритмом на каждом шаге (проекцией, штрафом или, как в SMO, аналитическим сохранением допустимости при каждом обновлении пары переменных) — простое покоординатное движение по антиградиенту без такого учёта немедленно выведет точку за пределы допустимой области.

Ошибка 5. Полагают, что метод активного набора всегда быстрее методов внутренней точки, поскольку «работает только с частью ограничений».

Как выглядит: «активный набор рассматривает меньше ограничений за раз, значит он в принципе эффективнее внутренней точки».

Почему возникает: интуитивная, но неполная экстраполяция от отдельно взятой итерации (действительно более дешёвой) на всю задачу целиком, без учёта числа итераций до сходимости.

Как правильно: число итераций метода активного набора может расти экспоненциально с размером задачи в худшем случае (как и симплекс-метод из урока 281), тогда как методы внутренней точки гарантируют сходимость за число итераций, полиномиальное от размера задачи; какой из подходов быстрее на практике — зависит от структуры конкретной задачи (разреженность ожидаемого решения, размер задачи), а не является универсальным правилом.

Ошибка 6. Забывают, что box-ограничения $0\le\alpha_i\le C$ появляются только в задаче с мягким зазором, и ошибочно переносят верхнюю границу $C$ на задачу с жёстким зазором.

Как выглядит: «в любой задаче SVM обязательно есть ограничение $\alpha_i\le C$».

Почему возникает: мягкий зазор — намного более распространённый на практике вариант SVM, поэтому его формулировка воспринимается как единственная.

Как правильно: верхняя граница $C$ — прямое следствие штрафного слагаемого $C\sum\xi_i$ в прямой задаче (задание 8); в задаче с жёстким зазором (без допуска на нарушение отступа, соответствует формальному пределу $C\to\infty$) остаётся только ограничение $\alpha_i\ge0$ без верхней границы.

Главное запомнить

• Задача квадратичного программирования (КП) — это минимизация квадратичной функции $\frac12x^\top Qx+c^\top x$ при линейных ограничениях $Ax\le b$, $Ex=d$; допустимая область устроена так же, как в линейном программировании, различается только форма целевой функции.

• В отличие от линейного программирования, где оптимум линейной функции всегда достигается в вершине многогранника (урок 281), оптимум квадратичной функции может лежать внутри допустимой области, на грани произвольной размерности или в вершине — в зависимости от того, где относительно многогранника находится безусловный минимум квадратичной формы.

• Задача КП выпукла тогда и только тогда, когда матрица $Q$ положительно полуопределена ($Q\succeq0$); в этом случае по теореме урока 278 любой локальный минимум является глобальным.

• Гессиан квадратичной формы равен постоянной матрице $Q$ и не зависит от точки $x$ — в отличие от общего случая выпуклой функции, где гессиан приходится проверять в каждой точке отдельно, проверка выпуклости КП сводится к однократному анализу знакоопределённости одной матрицы.

• Ковариационная матрица в задаче Марковица всегда положительно полуопределена по определению дисперсии, а значит, задача портфельной оптимизации выпукла для любого набора активов без дополнительных условий.

• Двойственная задача SVM — классическая выпуклая задача КП относительно множителей Лагранжа $\alpha$: целевая функция $\sum_i\alpha_i-\frac12\alpha^\top Q\alpha$ с $Q_{ij}=y_iy_j\langle x_i,x_j\rangle$, ограничения $0\le\alpha_i\le C$ и $\sum_i\alpha_iy_i=0$.

• Выпуклость двойственной задачи SVM для любого допустимого ядра гарантируется теоремой Мерсера: матрица Грама ядра $K$ положительно полуопределена, а значит, и $Q=D_yKD_y$ тоже положительно полуопределена при любых метках и любом наборе точек.

• Библиотеки libsvm и scikit-learn обучают SVM, решая эту двойственную задачу КП специализированным алгоритмом SMO — обучение SVM на практике буквально сводится к вызову QP-решателя, а не к отдельной эвристике.

• Метод активного набора обобщает идею симплекс-метода на квадратичный случай: угадывает набор активных ограничений, сводит подзадачу к линейной системе через условия KKT, итеративно корректирует набор.

• Методы внутренней точки движутся строго через внутренность допустимой области вдоль центрального пути, штрафуя приближение к границе логарифмическим барьером, и сходятся за полиномиальное число итераций — они предпочтительнее для больших плотных задач, тогда как активный набор (в частности, SMO) эффективнее при ожидаемом разреженном решении.

Связь с темами курса

Что нужно было знать до этого урока

Этот урок напрямую опирается сразу на три предыдущих. Из урока 281 (симплекс-метод) — понимание того, почему в линейном программировании оптимум всегда достигается в вершине, что задаёт контраст для понимания геометрии КП. Из урока 282 (двойственность) — сама идея перехода от прямой задачи к двойственной через лагранжиан и условия стационарности, которую этот урок доводит до полного явного вывода на примере SVM. Из урока 278 (выпуклые функции) — критерий выпуклости через положительную полуопределённость гессиана и главная теорема о том, что у выпуклой функции любой локальный минимум глобален; здесь этот критерий применяется в его самом простом частном случае, поскольку гессиан квадратичной формы постоянен.

Что изучить дальше

Следующий урок 284 разбирает целочисленное программирование — что происходит, когда к линейным или квадратичным ограничениям добавляется требование целочисленности переменных. Этот шаг превращает даже, казалось бы, «простую» задачу из выпуклой в NP-трудную в общем случае: сама допустимая область (набор целых точек внутри многогранника) перестаёт быть выпуклым множеством, и вся аккуратная геометрическая картина, построенная в сегодняшнем уроке, требует принципиально иных методов решения — ветвей и границ, отсечения плоскостями, релаксации.

Где это нужно в жизни

🤖 Метод опорных векторов. Это центральный пример урока: обучение SVM на практике — это решение двойственной задачи КП относительно множителей Лагранжа $\alpha_i$. Матрица $Q=D_yKD_y$ строится из ядерной матрицы Грама, её положительная полуопределённость гарантируется теоремой Мерсера для любого допустимого ядра (линейного, полиномиального, RBF), а решают эту задачу специализированные QP-солверы — в первую очередь алгоритм SMO Джона Платта, работающий внутри libsvm и, соответственно, внутри sklearn.svm.SVC. Разреженность решения (большинство $\alpha_i=0$) — прямое следствие условий дополняющей нежёсткости из KKT: только опорные векторы, лежащие на границе зазора или внутри него, получают ненулевой множитель.

💰 Портфельная оптимизация. Модель Марковица минимизирует дисперсию портфеля $x^\top\Sigma x$ при линейных ограничениях на состав и доходность — классическая выпуклая КП, применяемая ежедневно в количественных финансах для расчёта оптимального распределения активов.

📐 Регуляризованная линейная регрессия с ограничениями. Non-negative least squares (задание 18) и другие варианты регрессии с линейными ограничениями на веса (например, ограничение суммы весов единицей в задачах смешивания или аллокации) — тоже задачи КП, где гессиан $\frac1nX^\top X+\lambda I$ проверяется на положительную определённость ровно так же, как в уроке 278.

🎮 Компьютерная графика и робототехника. Задачи обнаружения столкновений и построения траекторий с ограничениями на скорость и ускорение часто формулируются как последовательность небольших задач КП, решаемых в реальном времени — здесь важна именно скорость сходимости метода активного набора на компактных, часто повторяющихся подзадачах.

Интересные факты

• Алгоритм SMO, предложенный Джоном Платтом в 1998 году специально для ускорения обучения SVM, работает с подзадачами ровно из двух переменных не потому, что это удобное округлое число, а потому, что это математически минимальный размер подзадачи, на котором можно изменить решение, не нарушив линейное ограничение равенства $\sum_i\alpha_iy_i=0$ — задача 17 в блоке практики восстанавливает это рассуждение формально.

• Гарри Марковиц получил Нобелевскую премию по экономике в 1990 году за теорию, математическое ядро которой — не что иное, как задача квадратичного программирования; при этом сам термин «квадратичное программирование» на момент публикации его работы в 1952 году ещё не был общепринятым, и Марковицу с Уильямом Уолфом пришлось фактически заново изобретать алгоритмический аппарат для своего частного случая задачи.

• В некоторых практических реализациях QP-решателей для SVM (в том числе исторически в ранних версиях libsvm) матрица $Q$ размера $N\times N$ никогда не строится и не хранится целиком в памяти даже для сотен тысяч обучающих примеров — вместо этого solver вычисляет нужные строки $Q$ «на лету» через значения ядра, что делает возможным обучение SVM на данных, для которых полная матрица Грама попросту не поместилась бы в оперативную память.

• Общая (не выпуклая) задача квадратичного программирования с произвольной, знаконеопределённой матрицей $Q$ является NP-трудной — к ней можно свести, например, задачу MAX-CUT о разбиении графа на две части с максимальным числом рёбер между частями; это ровно та причина, по которой авторы прикладных моделей (Марковиц, Вапник) так тщательно заботились о том, чтобы их конкретная матрица $Q$ была заведомо положительно полуопределена по построению, а не полагались на удачу.

Лайфхаки

• Прежде чем передавать самостоятельно сформулированную задачу КП в солвер, всегда явно проверь знакоопределённость матрицы $Q$ (через numpy.linalg.eigvalsh(Q) — если минимальное собственное значение неотрицательно, задача выпуклая); большинство практических «странных» результатов QP-солвера объясняются именно тем, что $Q$ на самом деле не положительно полуопределена из-за ошибки в её построении.

• Если задача выглядит как КП, но $Q$ получилась близкой к положительно полуопределённой с крошечными отрицательными собственными значениями из-за численных ошибок с плавающей точкой, добавь небольшую регуляризацию $Q \leftarrow Q + \varepsilon I$ с малым $\varepsilon>0$ — этот приём (тот же самый, что Ridge-регуляризация из урока 278) гарантированно восстанавливает строгую положительную определённость и устраняет численную неустойчивость решателя.

• При работе с SVM на больших датасетах ($N>10\,000$) не пытайся собрать полную матрицу $Q$ размера $N\times N$ в памяти — она займёт $O(N^2)$ памяти, что быстро становится непрактичным; используй параметр cache_size в sklearn.svm.SVC, который управляет тем, сколько строк ядерной матрицы solver хранит в кэше одновременно, вычисляя остальные по требованию.

• Если хочешь на практике убедиться, что оптимум двойственной задачи SVM разрежен (большинство $\alpha_i^*=0$), после обучения посмотри на model.support_vectors_.shape[0] в scikit-learn относительно общего числа обучающих примеров — как правило, число опорных векторов оказывается заметно меньше общего размера выборки, что прямая иллюстрация условий дополняющей нежёсткости KKT.

• При постановке собственной оптимизационной задачи (не обязательно SVM) сначала попробуй сформулировать её как выпуклую КП, а не сразу как общую нелинейную задачу или задачу для нейросети — если получится, ты автоматически получишь гарантию единственного, воспроизводимого, вычислимого за предсказуемое число итераций решения, вместо того чтобы полагаться на удачу случайной инициализации и множественные перезапуски.

• Для небольших и средних задач КП (сотни-тысячи переменных) не пиши собственный солвер с нуля — используй проверенные библиотеки (cvxopt, OSQP, quadprog, scipy.optimize.minimize с методом trust-constr): они уже реализуют и метод активного набора, и методы внутренней точки с должной численной устойчивостью, которую трудно повторить самостоятельно с первого раза.

Квадратичное программирование — это ровно та математика, которая превращает метод опорных векторов из красивой геометрической идеи «найти максимальный зазор между классами» в конкретный, вычислимый, гарантированно сходящийся алгоритм. Каждый раз, когда SVC().fit() завершает работу и возвращает тебе обученную модель, за кулисами только что был решён QP — с явной матрицей $Q$, чью положительную полуопределённость гарантирует теорема Мерсера, и с ограничениями, чью структуру эксплуатирует алгоритм SMO. Понимание этой цепочки — от геометрии квадратичных форм до конкретного численного солвера — превращает SVM из «чёрного ящика», который просто работает, в модель, поведение которой ты можешь объяснить и предсказать на уровне математики, лежащей в её основе.