Математика / Численная оптимизация

Условия Каруша—Куна—Таккера: комплементарная нежёсткость

Условия Каруша—Куна—Таккера: дополнительная нежёсткость даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Опубликовано: 1 ноября 2026 г.Обновлено: 1 ноября 2026 г.

Оптимизация и исследование операций Страницы с задачами и решениями Есть историческая справка Диагностика условий

Формула

\lambda_i g_i(x)=0,\quad\lambda_i\ge0,\quad g_i(x)\le0

Схема min x² при ограничении x≥1

Допустимая область начинается с x=1. Минимум в ней: x=1, f=1, λ=2.

Обозначения

$x$: аргумент, состояние или вектор данных конкретной задачи, единицы исходной модели
$n,k,i,j$: целые индексы узла, шага либо компоненты, безразмерные
$ε / err$: допуск или оценка вычислительной ошибки, если она используется, единицы результата

Условия применения

Запись использует ограничения g_i(x)≤0 и множители lambda_i≥0 для задачи минимизации; знак меняется при другой конвенции ограничений. Комплементарность проверяют только вместе с допустимостью и стационарностью, а не вместо них; при активном g_i=0 множитель может быть положительным.

Ограничения

Результат нельзя переносить на похожую по словам, но другую модель. Оценка ошибки может быть локальной, а сходимость — зависеть от гладкости, обусловленности или начальных данных. Округление, вырождение матрицы и нарушения ограничений меняют смысл вычисления. Число после знака равенства не заменяет проверку: следует показать, какая именно формула применена, в каких единицах получен ответ и почему условия выполнены. Для информационных величин особенно важно не смешивать биты и натуральные единицы.

Подробное объяснение

Неравенство g_i(x)≤0 допускает запас: если g_i(x)<0, ограничение не «давит» на решение и соответствующий множитель обязан быть нулём. Если λ_i>0, произведение заставляет g_i(x)=0.

Стационарность объединяет градиент цели с градиентами активных ограничений. В одномерном примере знак множителя виден непосредственно: ограничение x≥1 записывается как 1−x≤0, поэтому в производной появляется −λ.

KKT — не простой способ угадать оптимум. Сначала проверяют допустимость, затем знаки множителей, дополнительную нежёсткость и стационарность; каждое условие исключает свой тип ложного ответа.

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

В активном случае g(1)=0 и λ=2: дополнительная нежёсткость выполнена, а стационарность 2·1−2=0. В неактивном случае x=3, g(3)=−2<0, поэтому λ=0; производная (x−3)² в точке 3 также равна нулю. Два случая демонстрируют обе ветви произведения λg=0.

Как пользоваться формулой

Выпишите \lambda_i g_i(x)=0,\quad\lambda_i\ge0,\quad g_i(x)\le0 и отметьте искомую величину; не заменяйте её одноимённым параметром из другой модели.
Подготовьте данные в требуемой форме: проверьте индексы, знак, область аргумента, нормировку либо размерность.
Выполните первое задание по действиям и сохраните промежуточные значения каждого коэффициента, отношения или суммы.
Проверьте результат естественным способом: симметрией, точным частным случаем, невязкой или исходным ограничением.
Разберите второе задание: изменённые данные показывают границу применимости и предупреждают типичную ошибку метода.

Историческая справка

Условия оптимальности получили современное имя по работам Уильяма Каруша (диссертация 1939 года), Гарольда Куна и Альберта Таккера (1951). Они расширили метод множителей Лагранжа на неравенства и стали базой нелинейного программирования. Дополнительная нежёсткость компактно выражает развилку: либо ограничение строго запасно и множитель равен нулю, либо множитель может быть положительным, но тогда ограничение должно быть активным. Позднейшая теория уточнила условия регулярности, при которых эти условия необходимы или достаточны.

Уильям Каруш защитил диссертацию с соответствующими условиями в 1939 году, а Кун и Таккер опубликовали классическую работу «Nonlinear Programming» в 1951 году. Современное название было закреплено позже, когда теория нелинейного программирования систематизировала условия квалификации.

Историческая линия формулы

Название KKT объединяет Каруша, Куна и Таккера; оно не означает, что все части теории появились в одной публикации. Корректное применение требует проверять допустимость и условия регулярности, а выпуклость нужна для сильных выводов о глобальном минимуме. Источник в карточке указан для различения исторического имени, публикации и современной вычислительной формы; эти уровни не следует смешивать.

Пример

Минимизируем x² при x≥1, то есть g(x)=1−x≤0. В оптимуме x=1, стационарность 2x−λ=0 даёт λ=2; произведение λg=2·0=0. Ограничение активно. В активном случае g(1)=0 и λ=2: дополнительная нежёсткость выполнена, а стационарность 2·1−2=0. В неактивном случае x=3, g(3)=−2<0, поэтому λ=0; производная (x−3)² в точке 3 также равна нулю. Два случая демонстрируют обе ветви произведения λg=0. Неравенство g_i(x)≤0 допускает запас: если g_i(x)<0, ограничение не «давит» на решение и соответствующий множитель обязан быть нулём. Если λ_i>0, произведение заставляет g_i(x)=0.

Частая ошибка

Нельзя писать λ≥0 для ограничения, заранее записанного в форме g≥0: знак зависит от соглашения. Нельзя проверять только λg=0, забывая допустимость. Не следует объявлять точку глобальным минимумом без выпуклости. И не каждый минимум удовлетворяет простым KKT без условия регулярности. В разборе «Условия Каруша—Куна—Таккера: дополнительная нежёсткость» проверяют именно обозначения и условия данной записи.

Практика

Задачи с решением

Неактивное ограничение и lambda=0

Условие. Для min (x−3)² при x≥1 проверьте дополнительную нежёсткость.

Решение. Запишем g(x)=1−x≤0. В точке x=3 g=−2, а стационарность даёт λ=0; λg=0.

Ответ. Ограничение неактивно, λ=0.

Проверка недопустимой точки

Условие. Проверьте точку x=0.

Решение. g(0)=1>0, поэтому точка недопустима и условия KKT не применяют к ней как к кандидату.

Ответ. x=0 недопустима.

Дополнительные источники

https://doi.org/10.1525/9780520411586-036
https://web.stanford.edu/~boyd/cvxbook/

Связанные формулы

Математика

Отражение в методе Нелдера—Мида

$x_r=\bar x+\alpha(\bar x-x_w),\quad\alpha=1$

Отражение в методе Нелдера—Мида даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Математика

Обновление BFGS для обратной матрицы Гессе

$H_{k+1}=(I-\rho sy^T)H_k(I-\rho ys^T)+\rho ss^T,\quad\rho=(y^Ts)^{-1}$

Обновление BFGS для обратной матрицы Гессе даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Математика

Симплекс-метод: правило минимального отношения

$\theta^*=\min_{i:a_{ij}>0}\frac{b_i}{a_{ij}}$

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