Нелинейное программирование: метод Лагранжа

В нелинейном программировании нужно выбрать лучшее допустимое решение, когда цель или хотя бы одно ограничение нелинейны. Например, затраты растут как квадрат отклонения от плана, а допустимые сочетания параметров заполняют круг. Метод множителей Лагранжа связывает изменение цели с ограничениями и помогает найти кандидатов на оптимум. Для неравенств его дополняют условия Каруша - Куна - Таккера, или ККТ. В калькуляторе ниже можно менять радиус допустимого круга и наблюдать, когда ограничение действительно влияет на решение.
Постановка задачи и допустимая область
Общая задача минимизации имеет вид
Здесь - вектор управляемых переменных, - целевая функция, а ограничения задают допустимое множество. Нелинейность может быть в цели, в ограничении или сразу в обоих. Минимум ищут только среди допустимых точек; безусловный минимум может лежать вне разрешённой области. При поиске максимума удобно минимизировать , сохраняя те же ограничения.
Для конкретности будем минимизировать квадрат расстояния до точки :
Допустимое множество - круг вместе с границей. При малом точка недоступна: ближайшая к ней допустимая точка находится на окружности. Когда радиус достигает 2, центр линий уровня становится допустимым. Дальнейшее расширение круга уже не улучшает цель.
В ролике показана не траектория численного алгоритма, а семейство точных решений при разных . Линия уровня цели - окружность с центром ; на активной границе она касается допустимого круга. Сама геометрия условного экстремума подробнее разобрана в статье о множителях Лагранжа для равенств.
Как записать функцию Лагранжа для неравенства
Зафиксируем соглашение о знаках: задача на минимум, ограничение записано как , множитель . Тогда
Для нашего круга , поэтому
При нескольких неравенствах добавляют по одному слагаемому ; для каждого равенства добавляют множитель без ограничения знака. Противоположное соглашение о знаке тоже возможно, но менять его надо во всех условиях одновременно. Важно: стационарность лагранжиана сама по себе ещё не доказывает минимум исходной задачи.
Градиент цели в решении с активной границей направлен противоположно градиенту ограничения. Из-за этого на допустимой касательной не остаётся направления первого порядка, которое улучшало бы цель. Для нелинейной границы направление нормали зависит от точки, поэтому его вычисляют в найденном решении, а не выбирают заранее.
Условия ККТ и активность границы
Для одного гладкого неравенства необходимые условия ККТ в локальном минимуме при подходящем условии регулярности записываются так:
Первые три условия означают соответственно стационарность, допустимость точки и допустимость множителя. Последнее называется дополняющей нежёсткостью: если , то ; если , то . Однако активное ограничение может иметь и нулевой множитель. В нашем примере это происходит ровно при .
ККТ не всегда обязательны без оговорок: при нарушении регулярности оптимум может существовать, а подходящего конечного множителя не будет. Например, минимум при достигается в единственной допустимой точке , но там , и уравнение невозможно. Проверка регулярности - часть решения, особенно если градиент активного ограничения обращается в ноль.
Решение примера при радиусе 1
Положим . Частные производные дают систему стационарности:
Сначала проверим внутреннюю точку. Если , то , а стационарность требует . Эта точка вне круга, значит внутреннего решения нет.
На границе . Так как , из второго уравнения следует . Тогда или . Для первое уравнение даёт ; для оно даёт , что нарушает знак ККТ. Остаётся допустимый кандидат
Глобальность здесь легко проверить отдельно: для любой точки круга , поэтому , а . Равенство достигается в . Значит это единственный глобальный минимум. Такой прямой довод сильнее простого утверждения, что система ККТ решена.

Что меняется при другом радиусе
Из той же системы и геометрии получаем точное решение для всех :
При граница активна, и . При точка находится внутри круга, и . При точка на границе, но множитель уже нулевой. Эти три случая можно проверить ползунком: по мере роста радиуса значение цели падает до нуля и затем остаётся нулевым.
Множитель имеет смысл чувствительности, если параметризовать ограничение как с . В активном режиме оптимальное значение и
При увеличение правой части на небольшое уменьшает оптимальное значение примерно на . Это локальное приближение, а не точная формула для большого изменения. Чувствительность к самому радиусу другая: на активном участке. Поэтому численный смысл множителя зависит от того, как именно записано ограничение.
Когда условия дают глобальный ответ
В нашем примере выпукла, а круг - выпуклое множество. Более того, строго выпукла, поэтому допустимый минимум единственен. Здесь найденная точка ККТ глобально оптимальна. В общем случае выпуклой задачи с дифференцируемой выпуклой целью и выпуклыми неравенствами допустимая точка, удовлетворяющая ККТ, даёт глобальный минимум; равенства при этом должны быть аффинными.
Без выпуклости условия ККТ обычно дают лишь кандидатов: среди них могут оказаться локальные минимумы, максимумы или седловые точки. Их нужно исследовать и сравнивать с другими кандидатами и возможными нерегулярными точками. Существование глобального минимума тоже требует обоснования: например, непрерывная цель на непустом компактном допустимом множестве достигает минимума. Если множество неограниченно, сравнения нескольких стационарных точек недостаточно.
В квадратичном программировании цель квадратична, а ограничения линейны; наш круг показывает случай нелинейного ограничения. Когда систему ограничений неудобно решать непосредственно, используют также метод штрафных функций: он заменяет исходную задачу последовательностью вспомогательных задач. Для численного решения возникающих скалярных уравнений иногда применим метод половинного деления, если найдён отрезок со сменой знака непрерывной функции.
Как организовать решение с несколькими ограничениями
В прикладной задаче переменных и ограничений может быть больше двух, а геометрическую картинку построить трудно. Удобно сохранить логику примера в виде последовательности проверок. Сначала выпишите все ограничения в едином соглашении о знаках и определите область, где существуют производные. Уравнения, задающие границы исходной области определения, тоже нельзя терять при поиске решения.
Затем для каждого неравенства рассмотрите два возможных состояния: оно активно, либо его множитель равен нулю. При нескольких ограничениях перебирают согласованные наборы активных ограничений. Для каждого набора решают стационарные уравнения вместе с выбранными равенствами, а потом проверяют все исходные неравенства и знаки множителей. Например, если ограничений два, кандидат с первой активной и второй неактивной границей должен удовлетворять первому равенству и второму неравенству, а второй множитель в этом случае равен нулю.
Перебор может вернуть одну и ту же точку несколько раз, когда активное ограничение имеет нулевой множитель. Это не ошибка: достаточно объединить совпадающие кандидаты, сохранив все необходимые проверки. Если градиенты активных ограничений линейно независимы, выполняется одно из стандартных условий регулярности. Если зависимы, нельзя автоматически заключать, что решения нет: нужно проверить другое подходящее условие регулярности или отдельно исследовать такую точку.
Последний шаг зависит от постановки. Для локального исследования полезны вторые производные лагранжиана по допустимым направлениям; положительность соответствующей квадратичной формы при подходящих условиях даёт достаточный признак строгого локального минимума. Для глобального ответа используют структуру задачи, например выпуклость, либо доказывают, что рассмотрены все возможные места минимума. В численном расчёте дополнительно проверяют невязки: насколько близок градиент лагранжиана к нулю, выполняются ли ограничения и мало ли произведение каждого множителя на соответствующую невязку ограничения. Малые невязки свидетельствуют о приближённом выполнении условий, но сами по себе не гарантируют глобальность в невыпуклой задаче.
Частые ошибки
- Пропускают знак множителя. Для минимума с и лагранжианом необходимо ; иначе появляется лишний кандидат.
- Считают всякую границу обязательной. Неактивное ограничение выполняется строго и имеет нулевой множитель. Но активная граница тоже может иметь нулевой множитель.
- Объявляют стационарную точку глобальным минимумом. Проверяйте допустимость, регулярность и достаточные условия или сравнивайте значения с обоснованием полноты списка.
- Путают параметры чувствительности. Множитель в примере относится к правой части , а не непосредственно к радиусу .
FAQ
Всегда ли ограничение в оптимуме активно? Нет. При безусловный минимум лежит внутри круга, и ограничение не мешает его достичь.
Можно ли применять обычный метод Лагранжа к неравенству как к равенству? Можно исследовать отдельный случай активной границы, но затем надо проверить знак множителя и отдельно рассмотреть неактивный случай. Полная запись делается через ККТ.
Гарантируют ли ККТ глобальный минимум? Не вообще. Для выпуклой задачи с указанными выше условиями они достаточны; в невыпуклой задаче нужны дополнительные исследования.
Коротко
Метод множителей Лагранжа в нелинейном программировании связывает градиент цели с градиентами ограничений. Для неравенств условия ККТ добавляют знак множителя и дополняющую нежёсткость. В задаче о круге оптимум сначала лежит на границе, затем становится внутренним; проверка выпуклости или прямое сравнение значений превращает найденного кандидата в доказанный глобальный минимум.
Читайте также

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

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

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

Абсолютная и относительная погрешность числа
Абсолютная и относительная погрешность приближённого числа: формулы, расчёт в процентах, оценка при округлении и подробные примеры сравнения точности.

Абсолютная пропускная способность СМО: формула
Как найти абсолютную пропускную способность СМО через интенсивность потока и вероятность отказа: формула, пример расчёта и отличие от относительной способности.

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе
Алгоритм Флойда-Уоршелла на примере: как получить матрицу кратчайших путей для всех пар вершин, восстановить маршрут и вовремя обнаружить отрицательный цикл.