Условия оптимальности (KKT) 🔑

В университетском курсе (урок 214) ты уже решал задачи условного экстремума методом множителей Лагранжа — искал точку, где градиент цели параллелен градиенту ограничения, при условии, что это ограничение — уравнение, равенство: $g(x)=0$. Этого достаточно, чтобы вывести аккуратную математическую модель маятника или найти экстремум на кривой. Но открой формулировку задачи метода опорных векторов (SVM) — и ты увидишь ограничения совсем другого типа: не «зазор равен единице», а «зазор не меньше единицы», $y_i(w^\top x_i + b) \ge 1$. Это неравенство, а не равенство, и метод чистого Лагранжа для него, строго говоря, не определён — у неравенства нет единственной «кривой», вдоль которой можно скользить, есть целая допустимая область, внутри которой ограничение вообще не работает, и граница, где оно включается.

Условия Каруша — Куна — Таккера, или условия KKT, — это именно то расширение метода Лагранжа, которое закрывает этот пробел. Они честно отвечают на вопрос: как выглядит система уравнений (и неравенств) на точку экстремума, если часть ограничений — это не жёсткие равенства, а гибкие «не более» или «не менее»? Ответ оказывается устроен на удивление стройно: к обычной стационарности функции Лагранжа добавляются всего три новых требования — допустимость самой точки, неотрицательность множителей при неравенствах и особое условие дополняющей нежёсткости (complementary slackness), которое элегантно решает главную сложность: множитель при неравенстве обязан быть либо нулём (ограничение вообще не участвует в ответе), либо ограничение обязано выполняться точно как равенство (оно «упёрлось» в границу и определяет решение).

Это не абстрактная теоретическая надстройка ради красоты формул. Именно система KKT — это ровно тот математический механизм, который превращает задачу SVM «максимизировать зазор при условии, что все точки классифицированы правильно» в решаемую задачу квадратичного программирования, где дополняющая нежёсткость объясняет одно из самых красивых наблюдений во всём машинном обучении: подавляющее большинство обучающих точек вообще не влияют на итоговую разделяющую гиперплоскость, и только считаные — те, что оказались ровно на границе зазора, — получают ненулевой множитель и становятся опорными векторами. Без KKT это свойство SVM выглядело бы как случайное совпадение; с KKT оно оказывается прямым, неизбежным следствием одного математического условия.

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

История

Условия носят имя трёх математиков, но появились они не одновременно и не в соавторстве, а дважды независимо — с разрывом больше десяти лет и очень разной судьбой признания. Первым их вывел американский математик Уильям Каруш (William Karush) в 1939 году, в возрасте 24 лет, в своей магистерской диссертации в Чикагском университете под названием «Minima of Functions of Several Variables with Inequalities as Side Conditions» («Минимумы функций нескольких переменных с неравенствами в качестве побочных условий»). Каруш полностью вывел необходимые условия оптимальности для задачи с ограничениями-неравенствами — ровно то, что сегодня называется условиями KKT. Но диссертация осталась неопубликованной в научном журнале, циркулировала только внутри университета, и в течение почти двадцати лет о ней попросту никто не знал за пределами Чикаго.

В 1951 году американские математики Гарольд Кун (Harold W. Kuhn) и Алберт Такер (Albert W. Tucker) независимо переоткрыли те же самые условия и опубликовали их в статье «Nonlinear Programming» на Втором Беркли симпозиуме по математической статистике и теории вероятностей. Статья Куна и Такера оказалась в нужном месте в нужное время — расцвет линейного и нелинейного программирования, эпоха Данцига и симплекс-метода, — и условия быстро стали стандартным инструментом всей теории оптимизации под названием «условия Куна — Такера». Лишь в 1970-х годах, когда сообщество оптимизаторов внимательнее изучило историю вопроса, было признано, что Каруш вывел те же результаты на двенадцать лет раньше — и с тех пор общепринятым стало более справедливое название «условия Каруша — Куна — Таккера», сокращённо KKT, хотя в старой литературе (да и порой в современных статьях) до сих пор можно встретить название «условия Куна — Такера».

Эта история — не просто курьёз о приоритете, а хорошая иллюстрация того, как математика иногда развивается: важный результат может годами лежать «на полке», пока не назреет практическая потребность, которая заставит его переоткрыть заново. К концу XX века условия KKT стали фундаментом сразу нескольких прикладных направлений: теории двойственности в выпуклой оптимизации, интерьерных методов (interior point methods) решения задач линейного и квадратичного программирования, и — самое близкое к теме этого курса — теоретического вывода метода опорных векторов, который Владимир Вапник и его коллеги построили в 1990-х годах именно как задачу квадратичного программирования с ограничениями-неравенствами, решаемую через систему KKT.

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

Интуиция

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

Определение

Определение. Общая задача условной оптимизации с ограничениями-равенствами и ограничениями-неравенствами записывается так:

$$\min_{x \in \mathbb{R}^n} f(x) \quad \text{при условиях} \quad h_i(x) = 0,\ i = 1, \dots, p, \qquad g_j(x) \le 0,\ j = 1, \dots, m$$

Функцию $f$ называют целевой функцией, уравнения $h_i(x) = 0$ — ограничениями-равенствами, а $g_j(x) \le 0$ — ограничениями-неравенствами. Множество точек, удовлетворяющих всем ограничениям одновременно, называется допустимым множеством и обозначается $\mathcal{F} = \{x : h_i(x)=0\ \forall i,\ g_j(x) \le 0\ \forall j\}$.

Обрати внимание на техническую, но важную деталь: неравенство всегда приводится к стандартному виду «$\le 0$». Если в исходной формулировке задачи стоит $g(x) \ge c$, её переписывают как $c - g(x) \le 0$; если стоит $g(x) \le c$, переписывают как $g(x) - c \le 0$. Это не произвол — от выбора направления неравенства напрямую зависит знак множителя в условии $\mu \ge 0$, которое мы выведем чуть ниже, так что приводить все неравенства к одной и той же стандартной форме нужно обязательно, ещё до того как садиться выписывать систему.

Примеры

Пример 1: формализация задачи SVM с жёстким зазором. Пусть есть обучающая выборка $(x_i, y_i)$, $y_i \in \{-1, +1\}$, и мы ищем разделяющую гиперплоскость $w^\top x + b = 0$ с максимальным зазором. Задача SVM в стандартной постановке — минимизировать $\frac{1}{2}\|w\|^2$ (эквивалент максимизации зазора $2/\|w\|$) при условии, что каждая точка классифицирована с запасом не меньше единицы: $y_i(w^\top x_i + b) \ge 1$ для всех $i$. Приводим к стандартной форме: $g_i(w, b) = 1 - y_i(w^\top x_i + b) \le 0$. Ограничений-равенств здесь нет вовсе ($p=0$), ограничений-неравенств столько же, сколько точек в выборке ($m = n_{\text{samples}}$). Уже сама эта формализация — не решение, а грамотная постановка — первый обязательный шаг перед тем, как применять KKT.

Пример 2: ограничение на норму весов (ограниченная форма регуляризации). Обычная Ridge-регрессия штрафует большую норму весов, добавляя слагаемое $\lambda\|w\|^2$ прямо в функцию потерь. Но есть эквивалентная альтернативная постановка (её называют ограниченной регуляризацией, или регуляризацией Иванова): минимизировать саму ошибку $\|y - Xw\|^2$ напрямую, но при явном ограничении на допустимый размер весов, $\|w\|^2 \le t$ для какого-то заранее выбранного порога $t$. В стандартной форме: $f(w) = \|y-Xw\|^2$, $g(w) = \|w\|^2 - t \le 0$, без ограничений-равенств. Ты увидишь дальше в этом уроке (и ещё раз в разделе про связь с курсом), что штрафная форма Ridge и эта ограниченная форма — не два разных метода, а буквально одна и та же математика, только записанная по-разному, и связывает их именно множитель из условий KKT.

Пример 3: бюджетное ограничение портфеля. В задаче распределения инвестиций между активами часто одновременно нужны и равенство, и неравенства: доли активов $x_1, \dots, x_n$ обязаны в сумме давать ровно единицу (весь капитал распределён, ни рубля не потеряно и не добавлено) — это равенство $h(x) = \sum_i x_i - 1 = 0$, а каждая доля не может быть отрицательной (нельзя вложить «минус деньги» без разрешения на короткие продажи) — это набор неравенств $g_i(x) = -x_i \le 0$ для каждого $i$. Минимизируемая функция — например, дисперсия портфеля. Эта постановка — типичный пример задачи, где нужны оба вида ограничений сразу, и её нельзя решить ни чистым методом Лагранжа (не хватает механизма для неравенств), ни просто перебором (переменных может быть сотни).

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

Правильная формализация — это добрая половина решения задачи KKT. Если неравенство записано в «неправильном» направлении (не приведено к форме $\le 0$) или забыто явно указать, какие переменные равенства, а какие — неравенства, вся последующая система условий получится с неверными знаками, и решение либо не сойдётся, либо сойдётся к точке, которая на самом деле максимум, а не минимум. Именно поэтому в реальных библиотеках оптимизации (cvxpy, scipy.optimize.minimize с method='SLSQP', решатели квадратичного программирования внутри sklearn.svm.SVC) первым шагом всегда идёт приведение задачи к стандартной форме — и умение делать это руками на бумаге напрямую переносится в умение правильно описать задачу в коде.

Функция Лагранжа и условие стационарности

Интуиция

В уроке 214 функция Лагранжа «замешивала» цель и единственное ограничение-равенство в одну вспомогательную функцию с одним множителем $\lambda$. Здесь идея расширяется естественным образом: если ограничений-равенств несколько, у каждого свой множитель $\lambda_i$; если есть ещё и ограничения-неравенства, к ним тоже добавляется по множителю, но эти множители по традиции обозначают отдельной буквой $\mu_j$ — потому что, в отличие от $\lambda_i$, которые могут быть какого угодно знака, множители $\mu_j$ обязаны быть неотрицательными (мы разберём, почему именно неотрицательными, чуть ниже). Стационарность — условие «градиент вспомогательной функции по $x$ равен нулю» — остаётся ровно тем же самым принципом, что и в чистом методе Лагранжа: в точке условного экстремума градиент цели обязан «уравновешиваться» комбинацией градиентов всех ограничений, которые сейчас реально «работают».

Определение

Определение. Функция Лагранжа для задачи $\min f(x)$ при $h_i(x)=0$, $g_j(x)\le0$ строится так:

$$L(x, \lambda, \mu) = f(x) + \sum_{i=1}^p \lambda_i\, h_i(x) + \sum_{j=1}^m \mu_j\, g_j(x)$$

Условие стационарности требует, чтобы градиент $L$ по переменной $x$ обращался в ноль в точке экстремума $x^*$ при соответствующих множителях $\lambda^*, \mu^*$:

$$\nabla_x L(x^*, \lambda^*, \mu^*) = \nabla f(x^*) + \sum_{i=1}^p \lambda_i^* \nabla h_i(x^*) + \sum_{j=1}^m \mu_j^* \nabla g_j(x^*) = 0$$

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

Примеры

Пример 1: игрушечный SVM в одном измерении. Пусть есть всего одна обучающая точка $x=2$ с меткой $y=+1$, и мы ищем скаляр $w$, минимизирующий $\frac{1}{2}w^2$ при ограничении зазора $y \cdot (w \cdot x) \ge 1$, то есть $2w \ge 1$, в стандартной форме $g(w) = 1 - 2w \le 0$. Строим функцию Лагранжа: $L(w, \mu) = \frac{1}{2}w^2 + \mu(1 - 2w)$. Стационарность: $\dfrac{\partial L}{\partial w} = w - 2\mu = 0$, откуда $w = 2\mu$. Это уравнение пока не даёт единственного ответа — нужно ещё найти сам множитель $\mu$, а для этого понадобится условие дополняющей нежёсткости из следующего раздела. Но уже здесь видно главное: стационарность связывает $w$ и $\mu$ жёсткой линейной зависимостью, и решить систему до конца без остальных условий KKT невозможно.

Пример 2: сочетание равенства и последующая проверка неравенства. Минимизируем $f(x,y) = x^2 + 2y^2$ при равенстве $h(x,y) = x + y - 1 = 0$. Строим $L = x^2+2y^2+\lambda(x+y-1)$ (неравенств здесь пока нет вообще). Стационарность: $\partial L/\partial x = 2x+\lambda=0 \Rightarrow x=-\lambda/2$; $\partial L/\partial y = 4y+\lambda=0 \Rightarrow y=-\lambda/4$. Подставляя в равенство: $-\lambda/2-\lambda/4=1 \Rightarrow -\dfrac{3\lambda}{4}=1 \Rightarrow \lambda=-\dfrac{4}{3}$. Отсюда $x=\dfrac{2}{3}$, $y=\dfrac{1}{3}$. Если теперь добавить к этой же задаче ограничение-неравенство $x \ge 0$, найденная точка $x=2/3>0$ автоматически удовлетворяет ему строго, без касания границы — значит, будь это неравенство добавлено с самого начала, его множитель оказался бы нулевым, а решение осталось бы тем же самым. Это первая иллюстрация того, что часть неравенств в оптимуме попросту «не включается».

Пример 3: ограничение на окружности. Минимизируем $f(x,y) = -x-y$ (эквивалент максимизации $x+y$) при неравенстве $g(x,y) = x^2+y^2-1 \le 0$ (точка внутри единичного круга или на его границе). Функция Лагранжа: $L = -x-y+\mu(x^2+y^2-1)$. Стационарность: $\partial L/\partial x = -1+2\mu x = 0 \Rightarrow x = \dfrac{1}{2\mu}$; аналогично $y=\dfrac{1}{2\mu}$, то есть $x=y$ в любой стационарной точке. Заметь: при $\mu=0$ уравнение $-1+0=0$ противоречиво — значит, множитель здесь заведомо не может быть нулевым, а раз так, по дополняющей нежёсткости (следующий раздел) ограничение обязано быть активным. Уже сама стационарность подсказывает нам, в какую сторону двигаться дальше при решении, ещё до того как мы формально проверили остальные условия.

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

Условие стационарности — это то самое уравнение, которое связывает искомую точку $x^*$ и множители в единую систему; без него у задачи было бы бесконечно много «кандидатов», удовлетворяющих просто допустимости, но никак не связанных с формой самой функции $f$. Именно стационарность гарантирует, что найденная точка — не произвольная точка допустимой области, а именно та, где направление убывания цели полностью «погашено» комбинацией направлений ограничений. В библиотеках квадратичного программирования (например, внутри libsvm, на котором построен sklearn.svm.SVC) стационарность превращается в систему линейных уравнений относительно множителей — и это ровно та система, которую решатель численно решает тысячи раз при обучении SVM.

Дополняющая нежёсткость и геометрия активных ограничений

Интуиция

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

Определение

Условие дополняющей нежёсткости (complementary slackness). Для каждого ограничения-неравенства $j$ в точке $x^*$ с множителем $\mu_j^*$ должно выполняться:

$$\mu_j^*\, g_j(x^*) = 0, \qquad j = 1, \dots, m$$

Это равносильно тому, что для каждого $j$ верно одно из двух: либо $\mu_j^* = 0$ (ограничение неактивно, есть запас, $g_j(x^*) < 0$), либо $g_j(x^*) = 0$ (ограничение активно, выполняется точно как равенство, а множитель при этом может быть как положительным, так и (в вырожденных случаях) нулевым).

Геометрическая интерпретация условия дополняющей нежёсткости идёт рука об руку со стационарностью и даёт наглядную картину всей системы KKT целиком: в точке оптимума условие стационарности можно переписать как $-\nabla f(x^*) = \sum_i \lambda_i^* \nabla h_i(x^*) + \sum_j \mu_j^* \nabla g_j(x^*)$, причём из-за дополняющей нежёсткости в сумму справа реально входят только градиенты активных ограничений (для неактивных $\mu_j^*=0$, их слагаемые обнуляются). А поскольку $\mu_j^* \ge 0$, это означает: антиградиент цели в точке оптимума — это неотрицательная линейная комбинация градиентов активных ограничений. Иначе говоря, направление, в котором можно было бы улучшить $f$, обязательно «упирается» в один из активных заборов — иначе можно было бы сделать маленький шаг в эту сторону и улучшить решение, а значит, найденная точка не была бы оптимальной.

Примеры

Пример 1: одно ограничение активно, второе — нет. Минимизируем $f(x,y)=x^2+y^2$ при двух неравенствах: $g_1(x,y) = 1-x-y \le 0$ (то есть $x+y\ge1$) и $g_2(x,y) = -x \le 0$ (то есть $x\ge0$). Без учёта $g_2$ решение уже известно из предыдущего раздела ($x=y=0{,}5$, $\mu_1=1$, полное решение см. в примере 1 следующего раздела). Проверим $g_2$ в этой точке: $-0{,}5 < 0$ — запас есть, ограничение неактивно. По дополняющей нежёсткости это сразу означает $\mu_2^* = 0$: второе ограничение, хоть формально и присутствует в постановке задачи, вообще не влияет на ответ и может быть мысленно вычеркнуто.

Пример 2: портфель с тремя ограничениями, активно только одно. Минимизируем $f(x,y) = (x-1)^2+(y-1)^2$ при $g_1 = x+y-1 \le 0$, $g_2=-x\le0$, $g_3=-y\le0$ (бюджет и неотрицательность долей). Функция Лагранжа: $L = (x-1)^2+(y-1)^2+\mu_1(x+y-1)+\mu_2(-x)+\mu_3(-y)$. Предположим (и затем проверим), что активно только $g_1$, а $g_2,g_3$ — нет, то есть $\mu_2=\mu_3=0$. Стационарность упрощается: $2(x-1)+\mu_1=0$, $2(y-1)+\mu_1=0$ — сразу видно $x=y$. Подставляя в активное ограничение $x+y=1$: $x=y=0{,}5$. Проверка: $x=0{,}5>0$, $y=0{,}5>0$ — оба неактивных ограничения действительно выполняются со строгим запасом, предположение $\mu_2=\mu_3=0$ подтверждено постфактум. Из стационарности $\mu_1 = 2(1-0{,}5) = 1 \ge 0$ — допустимо. Все условия KKT выполнены: только одно из трёх неравенств оказалось «рабочим».

Пример 3: конкурирующие ограничения — побеждает более строгое. Минимизируем $f(x)=x^2$ при двух неравенствах $g_1(x)=2-x\le0$ (то есть $x\ge2$) и $g_2(x)=5-x\le0$ (то есть $x\ge5$). Условие $x\ge5$ автоматически влечёт $x\ge2$ — второе ограничение «сильнее» и полностью поглощает первое. Ответ очевиден геометрически: $x^*=5$. Проверим через дополняющую нежёсткость: при $x=5$, $g_1(5)=2-5=-3\ne0$ — ограничение неактивно, значит обязано быть $\mu_1^*=0$. А $g_2(5)=5-5=0$ — активно, $\mu_2^*$ может быть положительным. Стационарность: $2x-\mu_1-\mu_2=0$, при $\mu_1=0$: $\mu_2=2x=10\ge0$ — допустимо. Итог: слабое, избыточное ограничение автоматически получает нулевой множитель, даже если формально присутствует в постановке задачи, — дополняющая нежёсткость сама «отфильтровывает» лишнее.

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

Дополняющая нежёсткость — это именно то условие, которое делает систему KKT решаемой на практике: без него у тебя были бы $m$ неизвестных множителей $\mu_j$ и никакого способа понять, какие из них нулевые, а какие нет, кроме перебора всех $2^m$ комбинаций «активно / неактивно». А это же условие — прямое математическое объяснение того, почему SVM называют «разреженным» методом: подавляющее большинство точек обучающей выборки классифицируются с большим запасом, их ограничение $g_i$ строго отрицательно, и по дополняющей нежёсткости их множитель $\mu_i$ обязан быть нулём. В итоге разделяющая гиперплоскость определяется буквально несколькими точками, лежащими ровно на границе зазора, — теми самыми опорными векторами, которые дают алгоритму его название.

Полная система KKT и связь с методом Лагранжа

Интуиция

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

Определение

Полная система условий KKT. Точка $x^*$ вместе с множителями $\lambda^* \in \mathbb{R}^p$, $\mu^* \in \mathbb{R}^m$ удовлетворяет условиям Каруша — Куна — Таккера, если одновременно выполнены все четыре условия:

1. Стационарность: $\nabla f(x^*) + \sum_i \lambda_i^* \nabla h_i(x^*) + \sum_j \mu_j^* \nabla g_j(x^*) = 0$

2. Допустимость (primal feasibility): $h_i(x^*) = 0$ для всех $i$, и $g_j(x^*) \le 0$ для всех $j$

3. Неотрицательность множителей неравенств (dual feasibility): $\mu_j^* \ge 0$ для всех $j$

4. Дополняющая нежёсткость: $\mu_j^* g_j(x^*) = 0$ для всех $j$

При выполнении дополнительного условия регулярности ограничений (constraint qualification, например LICQ — линейная независимость градиентов активных ограничений) эти четыре условия являются необходимыми для того, чтобы $x^*$ было точкой локального минимума. Если же вдобавок $f$ и все $g_j$ выпуклы, а $h_i$ аффинны (линейны), условия KKT становятся ещё и достаточными — любая точка, удовлетворяющая им, гарантированно является глобальным минимумом.

Обрати внимание на частный случай, который прямо связывает этот урок с университетским курсом. Если в задаче вообще нет ограничений-неравенств ($m=0$), условия 3 и 4 становятся пустыми (нет ни одного $\mu_j$, о котором нужно что-то утверждать), и вся система схлопывается ровно до одной формулы — стационарности плюс допустимости равенств:

Это буквально система уравнений метода множителей Лагранжа из урока 214, слово в слово. KKT — это не отдельная, конкурирующая теория, а прямое, естественное расширение метода Лагранжа на случай, когда часть ограничений — не жёсткие уравнения, а гибкие неравенства.

Примеры

Пример 1: полный разбор мини-SVM на двух точках. Возьмём две обучающие точки: $x_1=1$ с меткой $y_1=+1$ и $x_2=-1$ с меткой $y_2=-1$ (в одном измерении, вес $w$ и смещение $b$). Ограничения зазора: для первой точки $y_1(w x_1+b)\ge1 \Rightarrow w+b\ge1$, в стандартной форме $g_1 = 1-w-b\le0$; для второй $y_2(wx_2+b)\ge1 \Rightarrow -(-w+b)\ge1 \Rightarrow w-b\ge1$, в стандартной форме $g_2=1-w+b\le0$. Минимизируем $f(w,b)=\frac12w^2$. Функция Лагранжа: $L=\frac12w^2+\mu_1(1-w-b)+\mu_2(1-w+b)$. Стационарность: $\partial L/\partial w = w-\mu_1-\mu_2=0$; $\partial L/\partial b=-\mu_1+\mu_2=0 \Rightarrow \mu_1=\mu_2$. Предположим (симметрия задачи это подсказывает), что оба ограничения активны: $1-w-b=0$ и $1-w+b=0$. Вычитая одно из другого: $-2b=0\Rightarrow b=0$; складывая: $2-2w=0\Rightarrow w=1$. Из стационарности: $\mu_1+\mu_2=w=1$, а вместе с $\mu_1=\mu_2$ получаем $\mu_1=\mu_2=0{,}5\ge0$ — все условия KKT выполнены. Обе точки оказались активными ограничениями с положительными множителями — обе стали опорными векторами, что полностью соответствует их симметричному, «граничному» расположению относительно разделяющей прямой $w x+b=0$, то есть $x=0$.

Пример 2: равенство и неравенство вместе, неравенство неактивно. Минимизируем $f(x,y)=x^2+y^2$ при равенстве $h(x,y)=x+y-2=0$ и неравенстве $g(x,y)=-x\le0$. Функция Лагранжа: $L=x^2+y^2+\lambda(x+y-2)+\mu(-x)$. Предположим $\mu=0$ (неравенство неактивно) и решим чистую задачу Лагранжа: $2x+\lambda=0$, $2y+\lambda=0 \Rightarrow x=y$; из $x+y=2$: $x=y=1$. Проверка допустимости неравенства: $x=1\ge0$ выполняется строго, значит предположение $\mu=0$ подтверждено, и по дополняющей нежёсткости $\mu\cdot(-1)=0$ действительно даёт $\mu=0$ без противоречий. Итог: $x^*=y^*=1$, $\lambda^*=-2$, $\mu^*=0$ — полная система KKT выполнена, а неравенство в этой конкретной задаче оказалось лишь «подстраховкой», которая не понадобилась.

Пример 3: проекция на шар — связь с ограниченной регуляризацией. Минимизируем $f(x,y)=(x-3)^2+(y-4)^2$ при неравенстве $g(x,y)=x^2+y^2-1\le0$ (аналог ограничения на норму весов $\|w\|^2\le1$ в ограниченной регуляризации из первого раздела урока). Безусловный минимум находится в точке $(3,4)$, но она нарушает ограничение ($9+16=25>1$) — значит, ограничение обязано быть активным. Функция Лагранжа: $L=(x-3)^2+(y-4)^2+\mu(x^2+y^2-1)$. Стационарность: $2(x-3)+2\mu x=0 \Rightarrow x(1+\mu)=3 \Rightarrow x=\dfrac{3}{1+\mu}$; аналогично $y=\dfrac{4}{1+\mu}$. Из активности $x^2+y^2=1$: $\dfrac{9+16}{(1+\mu)^2}=1 \Rightarrow (1+\mu)^2=25 \Rightarrow 1+\mu=5$ (берём положительный корень) $\Rightarrow \mu^*=4\ge0$. Тогда $x^*=3/5=0{,}6$, $y^*=4/5=0{,}8$. Заметь: точка $(0{,}6,\,0{,}8)$ — это в точности вектор $(3,4)$, нормированный до единичной длины, то есть спроецированный на границу допустимого шара вдоль направления к исходному безусловному оптимуму. Это ровно то, что происходит при проецированном градиентном спуске с ограничением на норму весов — метод оптимизации, который явно используется, например, при обучении с ограниченным бюджетом на размер параметров.

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

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

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

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

Задание 1: Найди точку минимума $f(x)=x^2$ при ограничении $x\ge3$ через полную систему KKT.

Задание 2: Найди точку минимума $f(x)=(x-1)^2$ при ограничении $x\le5$.

Задание 3: Найди минимум $f(x,y)=x^2+y^2$ при $x\ge1$, $y\ge1$.

Задание 4: Найди минимум $f(x)=(x+2)^2$ при $x\ge0$.

Задание 5: Найди минимум $f(x,y)=(x-3)^2+y^2$ при равенстве $x=3$ и неравенстве $y\ge2$.

Задание 6: Найди минимум $f(x,y)=x^2+y^2$ при $x+2y\ge4$.

Задание 7: Найди минимум $f(x)=-x$ при $0\le x\le4$.

Задание 8: Найди минимум $f(x,y)=x^2+y^2$ при равенстве $x-y=1$ (без неравенств).

Задание 9: Найди минимум $f(x,y)=(x-2)^2+y^2$ при $x^2+y^2\le4$ и объясни, почему множитель может оказаться нулевым даже при активном ограничении.

Задание 10: Найди минимум $f(x)=x$ при $x\ge-1$.

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

Задание 11: Найди минимум $f(x,y)=x^2+y^2$ при $x+y=1$ и $x\ge0$.

Задание 12: Найди минимум $f(x,y)=x^2+y^2$ при $x+y=1$ и $x\ge0{,}6$.

Задание 13: Игрушечный SVM с одной точкой $x=3$, $y=+1$: найди $w^*$, минимизирующий $\frac12w^2$ при $3w\ge1$.

Задание 14: Найди проекцию точки $(1,2)$ на единичный круг (минимизируй $(x-1)^2+(y-2)^2$ при $x^2+y^2\le1$).

Задание 15: Проверь совместимость ограничений $x\ge1$, $y\ge2$, $x+y\le2$ и объясни, что это значит для системы KKT.

Задание 16: Найди максимум произведения $xy$ при $x+y=10$, $x\ge0$, $y\ge0$ (перепиши как минимизацию $-xy$).

Задание 17: Найди минимум $f(x)=x^2$ при $x\ge1$ и $x\ge-3$.

Задание 18: Найди минимум $f(x,y)=x^2+y^2$ при равенстве $x=y$ и неравенстве $x+y\ge2$.

Задание 19: Найди минимум $f(x,y)=x^2+y^2$ при равенстве $x+2y=3$ (без неравенств).

Задание 20: Найди минимум $f(x,y,z)=x^2+y^2+z^2$ при $x+y+z\ge3$.

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

Задание 21: В задании 1 множитель $\mu^*=6$ был найден для минимизации $x^2$ при $x\ge3$. Объясни, почему при максимизации $x^2$ на том же ограничении $x\ge3$ условие $\mu\ge0$ работать перестаёт (эта задача вообще не имеет решения), и что это говорит о смысле знака $\mu$.

Задание 22: Докажи в общем виде: если в кандидатной точке $x^*$, удовлетворяющей стационарности и допустимости, ограничение $g_j(x^*)$ строго отрицательно, то дополняющая нежёсткость однозначно вынуждает $\mu_j^*=0$.

Задание 23: Опираясь на задание 9, объясни, почему в вырожденном случае (ограничение активно, но множитель нулевой) сдвиг границы допустимой области чуть дальше от оптимума никак не изменил бы найденное решение.

Задание 24: Задача $\min x^2+y^2$ при $x+y\ge1$ имеет выпуклую цель и выпуклую (полуплоскость) допустимую область. Опираясь на теорему из урока 278 о том, что у выпуклой функции любой локальный минимум глобален, объясни, почему найденная точка $(0{,}5,\,0{,}5)$ через KKT гарантированно глобальный минимум.

Задание 25: Покажи явно, что происходит с условиями 3 и 4 полной системы KKT, если ограничений-неравенств нет вовсе ($m=0$), и объясни, почему в этом случае KKT в точности превращается в систему метода Лагранжа из урока 214.

Задание 26: К SVM-примеру из основного текста (точки $x_1=1$, $y_1=+1$ и $x_2=-1$, $y_2=-1$, ответ $w^*=1$, $b^*=0$) добавь третью точку $x_3=2$, $y_3=+1$ и проверь, становится ли она опорным вектором.

Задание 27: Сформулируй в стандартной форме KKT задачу «минимизировать $\|y-Xw\|^2$ при ограничении $\|w\|^2\le t$» (ограниченная форма Ridge) и объясни, чем множитель $\mu^*$ этой задачи содержательно совпадает с коэффициентом регуляризации $\lambda$ обычной штрафной формы Ridge.

Задание 28: В задании 15 система ограничений оказалась несовместной. Сформулируй, какую проверку стоит делать перед тем, как решать систему KKT для любой новой задачи, и почему это особенно важно для задач с несколькими неравенствами.

Задание 29: Найди минимум $f(x,y)=x^2+y^2$ при ограничении $(x-3)^2+(y-3)^2\le2$ (допустимая область — маленький круг вдали от начала координат) через полную систему KKT.

Задание 30: Выпиши полную систему KKT (все четыре условия) для абстрактной задачи $\min f(x)$ при одном равенстве $h(x)=0$ и одном неравенстве $g(x)\le0$, и коротко объясни, что именно ломается в характеризации оптимума, если убрать хотя бы одно из четырёх условий.

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

Не приводить неравенства к единой стандартной форме $g(x)\le0$ перед составлением функции Лагранжа. Если часть ограничений записана как «$\ge$», а часть — как «$\le$», знаки множителей при стационарности перепутаются, и условие $\mu\ge0$ окажется бессмысленным для тех ограничений, где знак не был приведён к стандарту.

Забывать проверять условие $\mu\ge0$ после того, как стационарность и активность ограничения уже дали числовое значение множителя. Иногда формальное решение системы стационарности даёт отрицательный $\mu$ — это верный сигнал, что предположение «ограничение активно» было неверным, и на самом деле оптимум находится внутри допустимой области, а не на этой конкретной границе.

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

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

Не проверять допустимое множество на непустоту перед решением. Несовместные ограничения (как в задании 15 из блока практики) дают либо противоречивую систему уравнений, либо, что хуже, численный решатель может «сойтись» к точке, которая формально удовлетворяет части условий, но реально нарушает исходную постановку задачи.

Путать множители равенств $\lambda_i$ (могут быть любого знака) с множителями неравенств $\mu_j$ (обязаны быть неотрицательны в стандартной задаче минимизации). Это не техническая деталь записи, а содержательное различие: равенство ограничивает решение в обе стороны одинаково, а неравенство «толкает» только в одном направлении, что и объясняет требование неотрицательности.

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

• Условия KKT — это расширение метода множителей Лагранжа (урок 214) на задачи с ограничениями-неравенствами, а не отдельная, независимая теория.

• Функция Лагранжа с несколькими ограничениями строится как сумма цели и всех ограничений, умноженных на свои множители: $\lambda_i$ для равенств, $\mu_j$ для неравенств.

• Стационарность требует, чтобы градиент функции Лагранжа по $x$ обращался в ноль в точке экстремума.

• Допустимость требует, чтобы найденная точка удовлетворяла всем исходным ограничениям задачи — и равенствам, и неравенствам.

• Условие $\mu_j\ge0$ гарантирует, что множитель неравенства толкает решение в правильном направлении — внутрь допустимой области.

• Дополняющая нежёсткость $\mu_j g_j(x^*)=0$ — ключевое условие: множитель либо нулевой (ограничение неактивно), либо ограничение выполняется точно как равенство (активно).

• Геометрически в оптимуме антиградиент цели — неотрицательная комбинация градиентов только активных ограничений.

• При $m=0$ (нет неравенств) полная система KKT в точности превращается в систему метода Лагранжа из урока 214.

• Для выпуклых задач (выпуклая цель, выпуклые неравенства, аффинные равенства) условия KKT не только необходимы, но и достаточны для глобального минимума.

• Именно дополняющая нежёсткость математически объясняет, почему решение SVM определяется лишь несколькими опорными векторами, а не всей обучающей выборкой.

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

Этот урок напрямую продолжает университетский урок 214 («Условный экстремум, метод Лагранжа») — там ты решал задачи только с ограничениями-равенствами, здесь та же самая идея параллельности градиентов расширена на неравенства через множители $\mu_j\ge0$ и дополняющую нежёсткость. Если убрать из полной системы KKT все неравенства, ты получишь ровно ту систему уравнений, которую решал в уроке 214, — это не совпадение, а формальное частное соответствие двух теорий.

Связь с уроком 278 («Выпуклые функции») не менее важна: именно доказанная там теорема «у выпуклой функции любой локальный минимум глобален» превращает необходимые условия KKT в достаточные всякий раз, когда задача целиком выпукла. Без этой теоремы KKT давали бы лишь список кандидатов на экстремум, среди которых пришлось бы отдельно отличать минимумы от седловых точек и максимумов — именно так, как это происходит с невыпуклыми функциями потерь нейросетей.

И, конечно, главная практическая связь этого урока — с методом опорных векторов (SVM). Задача SVM с жёстким зазором — это в точности задача условной оптимизации с ограничениями-неравенствами $y_i(w^\top x_i+b)\ge1$, и её решение выводится ровно через условия KKT: стационарность даёт формулу весов через сумму опорных векторов, а дополняющая нежёсткость объясняет, почему только точки на границе зазора получают ненулевой множитель. Ты увидишь этот вывод в деталях в отдельном уроке про сам SVM — но математический фундамент под ним заложен именно здесь.

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

Диссертация Уильяма Каруша 1939 года пролежала практически незамеченной почти двадцать лет — история условий KKT прекрасно показывает, что важность математического результата иногда осознаётся сообществом далеко не сразу, а лишь когда для него находится «убийственное приложение».

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

В задачах SVM с реальными датасетами в десятки тысяч точек количество опорных векторов (точек с ненулевым множителем $\mu_i$) часто оказывается всего несколько процентов от общего числа обучающих примеров — прямое практическое следствие дополняющей нежёсткости, которое делает предсказание новых точек вычислительно дешёвым: нужно учитывать не всю обучающую выборку, а лишь малую её часть.

Условия KKT легли в основу целого класса численных методов — методов внутренней точки (interior point methods), которые в 1980-х годах (работа Нарендры Кармаркара, 1984) революционизировали решение задач линейного программирования, сделав возможным эффективное решение задач с миллионами переменных — тема, которую ты подробно разберёшь в следующем уроке про линейное программирование.

Лайфхаки

Всегда начинай решение с приведения всех неравенств к стандартной форме $g(x)\le0$ — это займёт одну лишнюю минуту, но избавит от путаницы со знаками множителей на всех следующих шагах.

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

Если после вычисления множителя $\mu_j$ по стационарности он получился отрицательным — это не ошибка вычислений, а прямой сигнал, что предположение об активности этого ограничения было неверным; вернись назад и попробуй вариант, где оно неактивно.

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

Прежде чем доверять численному решателю (scipy.optimize.minimize, cvxpy, решатель SVM) сложную задачу с ограничениями, реши руками маленький игрушечный пример с той же структурой ограничений — это лучший способ проверить, что твоя постановка задачи в коде на самом деле соответствует тому, что ты имел в виду математически.

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

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

Ты только что прошёл путь от одной узкой тропы метода Лагранжа до полноценной теории условий оптимальности, которая одинаково честно работает и для равенств, и для неравенств, — той самой теории, что тихо стоит за каждым вызовом SVC().fit() в scikit-learn. Формулы KKT выглядят громоздко только до тех пор, пока ты не разобрал их вручную на паре собственных примеров, как сегодня, — а дальше они становятся таким же рабочим инструментом, как производная или градиент. Следующий урок разберёт линейное программирование — частный, но невероятно важный на практике случай задачи с ограничениями, где условия KKT превращаются в основу для одного из самых знаменитых алгоритмов оптимизации, симплекс-метода.