06.09.2025 18:24
Alek_dr 2 580 Источник

Если Вы когда-то учились в вузе на технической специальности или учитесь сейчас (иначе, зачем бы Вам эта статья), у Вас наверняка есть предмет, который назывался примерно так — «Методы оптимизации» / «Введение в оптимизацию» или что-то похожее. Задачки там примерно такие: «завод производит продукцию k типов, как бы произвести n_1 деталей первого типа, ..., n_k деталей k-го и как можно дешевле». Потом рассказывалось про симплекс-метод для задач линейного программирования и про метод Лагранжа для задач нелинейного. Про указанные выше условия где-то упоминается, но без примеров, где-то сразу абстрактные примеры с матрицами, а может быть Ваш препод и вовсе написал в своей методичке, мол, это выходит за рамки курса. В этой статье предлагаю аккуратно разжевать на простом примере, что такое условия Каруша–Куна–Таккера (ККТ).

Что нам позволяют найти условия ККТ

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

\min_{x \in \mathbb{R}^n}{f(x)} \\ g_i(x) \le 0, \forall i=1\dots m \\h_i(x)=0, j=1 \dots p

На всякий случай поясним: здесь написано, что есть некая функция, зависящая от вектора x, которую нужно минимизировать. Также, есть m ограничений-неравенств и p ограничений-равенств. Это не единственная форма записи: можно искать максимум, может не быть какого-то из типов ограничений, но обычно задачу рассматривают именно в таком виде, либо же приводят к данному виду.

Последовательность действий, при решении с помощью ККТ

  • Запись задачи в указанном виде

  • Проверка регулярности

  • Составление функции Лагранжа

  • Запись условий ККТ

  • Поиск стационарных точек

  • Проверка достаточных условий

Пример. Собираем вискас (A Blending Problem)

Возьмем простой пример и шаг за шагом проверим все пункты.

Задача взята из документации к библиотеке PuLP (очень, кстати, полезная штука).

Надо собрать пачку вискаса из курицы x_1 и говядины x_2 так, чтобы содержащиеся в них протеин, жиры, клетчатка и соль удовлетворяли ограничениям, а стоимость одной пачки была как можно меньше.

Задача:

\min_{x}{0.013x_1 + 0.008x_2}

such that

1.00x_1+1.00x_2=100

h(x)

вес содержимого каждой пачки 100 г.

0.100x_1+0.200x_2 \ge 8.0

g_1(x)

не менее 8 г. протеина

0.080x_1+0.100x_2 \ge 6.0

g_2(x)

не менее 6 г. жиров

0.001x_1+0.005x_2 \le 2.0

g_3(x)

не более 2 г. клетчатки

0.002x_1+0.005x_2 \le 0.4

g_4(x)

не более 0.4 г. соли

Запишем задачу в указанном виде. В нашем случае задача уже на минимум, однако необходимо переписать ограничения g_1 и g_2 с противоположным знаком. Также, хоть это явно и не прописано в условиях задачи, надо иметь ввиду, что по смыслу x_1 и x_2 неотрицательны, это тоже надо учесть как отдельные ограничения-неравенства. Из всего сказанного выше получаем:

\min_{x}{0.013x_1 + 0.008x_2}

such that

1.00x_1+1.00x_2-100=0

h(x)

-0.100x_1-0.200x_2+8.0 \le 0

g_1(x)

-0.080x_1-0.100x_2+6.0 \le 0

g_2(x)

0.001x_1+0.005x_2-2.0 \le 0

g_3(x)

0.002x_1+0.005x_2-0.4 \le 0

g_4(x)

-x_1 \le 0

g_5(x)

-x_2 \le 0

g_6(x)

  • Запись задачи в указанном виде

Регулярность. Выше было сказано, что задача должна быть «адекватной». Так вот, математики называют это условием регулярности. Дать строгое определение регулярности труднее, чем просто проверить, что она есть. Но, неформально, ChatGPT даёт следующее объяснение:

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

Существует три основных критерия регулярности:

  1. Независимость градиентов активных ограничений (об активных ограничения скажем ниже);

  2. Условие Слейтера;

  3. Все ограничения — линейные функции.

Нам достался самый простой случай, когда все ограничения линейные. Условие регулярности выполнено.

  • Запись задачи в указанном виде

  • Проверка регулярности

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

Условия ККТ несколько расширяют функцию Лагранжа. Обычно, она используется в случае, если в задаче присутствуют только ограничения-равенства. В нашем же случае, имеют место как равенства, так и неравенства. Расширенная функция Лагранжа выглядит так:

L(x,\lambda, \mu)=f(x)+\sum_{i=1}^{m}{\lambda_{i}g_i(x)}+\sum_{j=1}^{p}{\mu_{j}h_j(x)}

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

L(x,\lambda, \mu)=0.013x_1 + 0.008x_2 + \\\lambda_1(-0.1x_1 - 0.2x_2 + 8.0) + \\\lambda_2(-0.08x_1-0.1x_2+6.0) + \\\lambda_3(0.001x_1 + 0.005x_2-2.0) + \\\lambda_4(0.002x_1 + 0.005x_2 - 0.4) + \\\lambda_5 x_4 + \lambda_6 x_2 + \\\mu(x_1 + x_2 - 100)

Лагранж готов. Галочка.

  • Запись задачи в указанном виде

  • Проверка регулярности

  • Составление функции Лагранжа

Условия ККТ

Ну вот, добрались до самого интересного. Прежде чем запишем сами условия, отметим один важный момент. ККТ — необходимые условия. Т.е., если мы найдем такую точку (x_1, x_2) и такие множители Лагранжа, что они будут удовлетворять всем условиям, значит мы нашли точку — кандидат на оптимальность. Является ли она оптимальной, это еще нужно будет проверить с помощью достаточных условий. Но это последний пункт нашего списка. Итак, теорема:

Пусть для задачи математического программирования выполнено условие регулярности. Тогда, если x^* — локальный минимум, то найдутся такие \lambda^* и \mu^*, что выполнены следующие условия:

  1. Стационарность

    \nabla_{x}L(x^{*}, \lambda^{*}, \mu^{*})=0

  2. Дополняющая нежёсткость

    \lambda_{i}^{*}g_i(x^{*})=0, \forall i=1, \dots , m

  3. Неотрицательность

    \lambda_{i}^{*} \ge 0, \forall i=1, \dots , m

Теперь, вооружившись этими условиями, будем искать стационарные точки. Найдем градиент лагранжиана по переменным x и приравняем к нулю:

\begin{cases} \frac{\partial L}{\partial x_1}=0.013-0.1 \lambda_1 -0.008 \lambda_2 + 0.001\lambda_3+0.002 \lambda_4 - \lambda_5 + \mu=0\\ \frac{\partial L}{\partial x_2}=0.008-0.2 \lambda_1 -0.1 \lambda_2 + 0.005\lambda_3+0.005 \lambda_4 - \lambda_6 + \mu=0 \end{cases}

А дальше смотрим на второе условие. Оно, очевидно, означает следующее: для каждого ограничения-неравенства либо само неравенство равно нулю, либо соответствующий множитель Лагранжа равен нулю. Если неравенство в точке x^* обращается в нуль, это ограничение называется активным. Ограничения-равенства активны всегда. Геометрически активность интуитивно правильно понимается: именно эти ограничения участвуют в решении, а там где они пересекаются и находится точка оптимума. Посмотрим на нашу задачу (благо переменных всего две).

Видим, что не выполнить ограничение g_3 довольно сложно, да и ограничение-равенство сильно сужает область поиска. Давайте временно забудем про g_3 и немного приблизим график. Точка оптимума находится на пересечении равенства и ограничения g_4. Итак, пара ограничений (h, g_4) — активные ограничения.

Но как бы мы искали активные ограничения в n-мерном пространстве? Да, пришлось бы заниматься комбинаторикой. В n-мерном пространстве,  в худшем случае, пришлось бы перебрать C_m^n комбинаций, для каждой комбинации проверить стационарность, неотрицательность и выполнение ограничений. Если есть ограничения-равенства, перебор упрощается, т.к. равенства всегда активны. Поэтому, действуя вслепую, в нашей задаче пришлось бы перебрать комбинации (h, g_1), (h, g_2), (h, g_3), (h, g_4), (h, g_5), (h, g_6). И если мы их переберем, то убедимся, что везде, кроме (h, g_4), что-то не выполняется: или множители Лагранжа отрицательны, или не выполняется система ограничений в найденной точке. Заметим также, что если в n-мерном пространстве задано p=m равенств, все эти танцы с бубном, т.е. выписыванием лагранжиана и проверкой регулярности не имеют смысла. Если решение существует, то оно единственно и находится из решения системы равенств (останется только проверить выполнение ограничений-неравенств). Но это рассуждение справедливо только для случая линейных ограничений. 

Вернемся к нашей задаче и найдем точку оптимума аналитически. Мы знаем, что активны ограничения g_4 и h. Значит, в функции Лагранжа \lambda_4 — неотрицательна,  ограничение g_4 равно нулю, остальные множители также равны нулю. Из этих соображений запишем систему:

\begin{cases} 0.002x_1+0.005x_2-0.4=0\\ x_1+x_2-100=0 \end{cases}

Решение системы: x_1=\frac{100}{3}, x_2=\frac{200}{3}.

Теперь из той же системы уравнений найдем соответствующие множители Лагранжа.

\begin{cases} 0.002\lambda_4+\mu+0.013=0\\ 0.005\lambda_4+\mu+0.008=0 \end{cases}

Решая систему, находим:

\lambda_4 = 1.66666666666667

\mu=−0.0163333333333333.

Для полной ясности запишем

x_1 = \frac{100}{3}, x_2=\frac{200}{3}

\lambda_1=0, \lambda_2=0, \lambda_3=0, \lambda_4 = 1.66666666666667, \lambda_5=0, \lambda_6=0

\mu=−0.0163333333333333.

Вот она, точка, в которой выполняются все условия ККТ: градиенты по x в найденной точке равны нулю, условия дополняющей нежесткости выполнены, найденная «лямбда» больше нуля (на «мю» такое ограничение не накладывалось). Ставим сразу две галочки.

  • Запись задачи в указанном виде

  • Проверка регулярности

  • Составление функции Лагранжа

  • Запись условий ККТ

  • Поиск стационарных точек

Теперь осталось проверить, что выполняется достаточное условие. В нашем случае проверка весьма условная. Достаточное условие звучит так:

Если исходная задача выпуклая, а для стационарной точки выполнены условия ККТ, то x^* — глобальный минимум. 

Это именно наш случай: у нас все функции линейны, а значит выпуклы, а значит задача тоже выпуклая. Ну вот и всё, ставим последнюю галочку.

  • Запись задачи в указанном виде

  • Проверка регулярности

  • Составление функции Лагранжа

  • Запись условий ККТ

  • Поиск стационарных точек

  • Проверка достаточных условий

Не такое уж и страшное это ваше ККТ. Хотя, в нелинейном случае, возможно, пришлось бы немного повозиться с проверками регулярности и достаточным условием.

Мне показалось, что с конкретным численным примером и пошаговым решением в интернете есть проблемы, а тема не самая простая — надо поразбираться. Так пусть будет на один пример больше. Спасибо всем, кто дочитал, надеюсь, кому-то стало понятнее. 

Источники:

  • Курс лекций МФТИ «Введение в теорию выпуклой оптимизации»

  • И.Л.Акулич. «Математическое программирование в примерах и задачах»

  • Practical Mathematical Optimization by Jan A.Snyman, Daniel N.Wilke

  • https://coin-or.github.io/pulp/CaseStudies/a_blending_problem.html

Комментарии (2)


  1. kompilainenn2
    06.09.2025 18:28
    #28805234

    Если Вы когда‑то учились в вузе на технической специальности или учитесь сейчас (иначе, зачем бы Вам эта статья), у Вас наверняка есть предмет, который назывался примерно так — «Методы оптимизации» / «Введение в оптимизацию» или что‑то похожее.

    Учился на технической специальности, ничего даже близко похожего не было


    1. Krawler
      06.09.2025 18:28
      #28805276

      Оно еще может называться "Исследование операций". У нас такое было