EssayAI
Блог
Блог
Математика и алгоритмы

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

8 ноября 2026Время чтения: 8 минут
#нелинейное программирование#множители лагранжа#условия ккт#выпуклая оптимизация#ограничения
Нелинейное программирование: метод Лагранжа

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

Постановка задачи и допустимая область

Общая задача минимизации имеет вид

min⁡xf(x)приgi(x)≤0,hj(x)=0.\min_x f(x)\quad\text{при}\quad g_i(x)\leq 0,\quad h_j(x)=0.

Здесь xx - вектор управляемых переменных, ff - целевая функция, а ограничения задают допустимое множество. Нелинейность может быть в цели, в ограничении или сразу в обоих. Минимум ищут только среди допустимых точек; безусловный минимум может лежать вне разрешённой области. При поиске максимума удобно минимизировать −f-f, сохраняя те же ограничения.

Для конкретности будем минимизировать квадрат расстояния до точки (2,0)(2,0):

f(x,y)=(x−2)2+y2,x2+y2≤r2,r>0.f(x,y)=(x-2)^2+y^2,\qquad x^2+y^2\leq r^2,\quad r>0.

Допустимое множество - круг вместе с границей. При малом rr точка (2,0)(2,0) недоступна: ближайшая к ней допустимая точка находится на окружности. Когда радиус достигает 2, центр линий уровня становится допустимым. Дальнейшее расширение круга уже не улучшает цель.

Допустимый круг расширяется и сжимается: золотая точка движется по границе, пока круг не достигает точки безусловного минимума, после чего остаётся на месте.

В ролике показана не траектория численного алгоритма, а семейство точных решений при разных rr. Линия уровня цели - окружность с центром (2,0)(2,0); на активной границе она касается допустимого круга. Сама геометрия условного экстремума подробнее разобрана в статье о множителях Лагранжа для равенств.

Как записать функцию Лагранжа для неравенства

Зафиксируем соглашение о знаках: задача на минимум, ограничение записано как g≤0g\leq 0, множитель λ≥0\lambda\geq 0. Тогда

L(x,y,λ)=f(x,y)+λg(x,y).L(x,y,\lambda)=f(x,y)+\lambda g(x,y).

Для нашего круга g=x2+y2−r2g=x^2+y^2-r^2, поэтому

L=(x−2)2+y2+λ(x2+y2−r2).L=(x-2)^2+y^2+\lambda(x^2+y^2-r^2).

При нескольких неравенствах добавляют по одному слагаемому λigi\lambda_i g_i; для каждого равенства добавляют множитель без ограничения знака. Противоположное соглашение о знаке тоже возможно, но менять его надо во всех условиях одновременно. Важно: стационарность лагранжиана сама по себе ещё не доказывает минимум исходной задачи.

Градиент цели в решении с активной границей направлен противоположно градиенту ограничения. Из-за этого на допустимой касательной не остаётся направления первого порядка, которое улучшало бы цель. Для нелинейной границы направление нормали зависит от точки, поэтому его вычисляют в найденном решении, а не выбирают заранее.

Условия ККТ и активность границы

Для одного гладкого неравенства необходимые условия ККТ в локальном минимуме при подходящем условии регулярности записываются так:

∇f+λ∇g=0,g≤0,λ≥0,λg=0.\nabla f+\lambda\nabla g=0,\qquad g\leq 0,\qquad \lambda\geq 0,\qquad \lambda g=0.

Первые три условия означают соответственно стационарность, допустимость точки и допустимость множителя. Последнее называется дополняющей нежёсткостью: если g<0g<0, то λ=0\lambda=0; если λ>0\lambda>0, то g=0g=0. Однако активное ограничение g=0g=0 может иметь и нулевой множитель. В нашем примере это происходит ровно при r=2r=2.

ККТ не всегда обязательны без оговорок: при нарушении регулярности оптимум может существовать, а подходящего конечного множителя не будет. Например, минимум xx при x2≤0x^2\leq 0 достигается в единственной допустимой точке x=0x=0, но там g′(0)=0g'(0)=0, и уравнение 1+λg′(0)=01+\lambda g'(0)=0 невозможно. Проверка регулярности - часть решения, особенно если градиент активного ограничения обращается в ноль.

Решение примера при радиусе 1

Положим r=1r=1. Частные производные дают систему стационарности:

2(x−2)+2λx=0,2y+2λy=0.2(x-2)+2\lambda x=0,\qquad 2y+2\lambda y=0.

Сначала проверим внутреннюю точку. Если x2+y2<1x^2+y^2<1, то λ=0\lambda=0, а стационарность требует (x,y)=(2,0)(x,y)=(2,0). Эта точка вне круга, значит внутреннего решения нет.

На границе x2+y2=1x^2+y^2=1. Так как λ≥0\lambda\geq 0, из второго уравнения следует y=0y=0. Тогда x=1x=1 или x=−1x=-1. Для x=1x=1 первое уравнение даёт λ=1\lambda=1; для x=−1x=-1 оно даёт λ=−3\lambda=-3, что нарушает знак ККТ. Остаётся допустимый кандидат

(x∗,y∗)=(1,0),λ∗=1,f(x∗,y∗)=1.(x^*,y^*)=(1,0),\quad \lambda^*=1,\quad f(x^*,y^*)=1.

Глобальность здесь легко проверить отдельно: для любой точки круга x≤1x\leq 1, поэтому (x−2)2≥1(x-2)^2\geq 1, а y2≥0y^2\geq 0. Равенство достигается в (1,0)(1,0). Значит это единственный глобальный минимум. Такой прямой довод сильнее простого утверждения, что система ККТ решена.

График минимального значения цели в зависимости от радиуса: при радиусе 1 минимум равен 1, а после радиуса 2 равен нулю
График минимального значения цели в зависимости от радиуса: при радиусе 1 минимум равен 1, а после радиуса 2 равен нулю

Что меняется при другом радиусе

Из той же системы и геометрии получаем точное решение для всех r>0r>0:

x∗=min⁡{r,2},y∗=0,f∗(r)=max⁡{2−r,0}2.x^*=\min\{r,2\},\qquad y^*=0,\qquad f^*(r)=\max\{2-r,0\}^2.

При 0<r<20<r<2 граница активна, x∗=rx^*=r и λ∗=2/r−1>0\lambda^*=2/r-1>0. При r>2r>2 точка (2,0)(2,0) находится внутри круга, f∗=0f^*=0 и λ∗=0\lambda^*=0. При r=2r=2 точка на границе, но множитель уже нулевой. Эти три случая можно проверить ползунком: по мере роста радиуса значение цели падает до нуля и затем остаётся нулевым.

Множитель имеет смысл чувствительности, если параметризовать ограничение как x2+y2≤bx^2+y^2\leq b с b=r2b=r^2. В активном режиме оптимальное значение V(b)=(2−b)2V(b)=(2-\sqrt b)^2 и

V′(b)=1−2b=−λ∗.V'(b)=1-\frac{2}{\sqrt b}=-\lambda^*.

При b=1b=1 увеличение правой части на небольшое Δb\Delta b уменьшает оптимальное значение примерно на Δb\Delta b. Это локальное приближение, а не точная формула для большого изменения. Чувствительность к самому радиусу другая: df∗/dr=−2λrd f^*/dr=-2\lambda r на активном участке. Поэтому численный смысл множителя зависит от того, как именно записано ограничение.

Когда условия дают глобальный ответ

В нашем примере ff выпукла, а круг - выпуклое множество. Более того, ff строго выпукла, поэтому допустимый минимум единственен. Здесь найденная точка ККТ глобально оптимальна. В общем случае выпуклой задачи с дифференцируемой выпуклой целью и выпуклыми неравенствами допустимая точка, удовлетворяющая ККТ, даёт глобальный минимум; равенства при этом должны быть аффинными.

Без выпуклости условия ККТ обычно дают лишь кандидатов: среди них могут оказаться локальные минимумы, максимумы или седловые точки. Их нужно исследовать и сравнивать с другими кандидатами и возможными нерегулярными точками. Существование глобального минимума тоже требует обоснования: например, непрерывная цель на непустом компактном допустимом множестве достигает минимума. Если множество неограниченно, сравнения нескольких стационарных точек недостаточно.

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

Как организовать решение с несколькими ограничениями

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

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

Перебор может вернуть одну и ту же точку несколько раз, когда активное ограничение имеет нулевой множитель. Это не ошибка: достаточно объединить совпадающие кандидаты, сохранив все необходимые проверки. Если градиенты активных ограничений линейно независимы, выполняется одно из стандартных условий регулярности. Если зависимы, нельзя автоматически заключать, что решения нет: нужно проверить другое подходящее условие регулярности или отдельно исследовать такую точку.

Последний шаг зависит от постановки. Для локального исследования полезны вторые производные лагранжиана по допустимым направлениям; положительность соответствующей квадратичной формы при подходящих условиях даёт достаточный признак строгого локального минимума. Для глобального ответа используют структуру задачи, например выпуклость, либо доказывают, что рассмотрены все возможные места минимума. В численном расчёте дополнительно проверяют невязки: насколько близок градиент лагранжиана к нулю, выполняются ли ограничения и мало ли произведение каждого множителя на соответствующую невязку ограничения. Малые невязки свидетельствуют о приближённом выполнении условий, но сами по себе не гарантируют глобальность в невыпуклой задаче.

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

  • Пропускают знак множителя. Для минимума с g≤0g\leq0 и лагранжианом f+λgf+\lambda g необходимо λ≥0\lambda\geq0; иначе появляется лишний кандидат.
  • Считают всякую границу обязательной. Неактивное ограничение выполняется строго и имеет нулевой множитель. Но активная граница тоже может иметь нулевой множитель.
  • Объявляют стационарную точку глобальным минимумом. Проверяйте допустимость, регулярность и достаточные условия или сравнивайте значения с обоснованием полноты списка.
  • Путают параметры чувствительности. Множитель в примере относится к правой части b=r2b=r^2, а не непосредственно к радиусу rr.

FAQ

Всегда ли ограничение в оптимуме активно? Нет. При r>2r>2 безусловный минимум (2,0)(2,0) лежит внутри круга, и ограничение не мешает его достичь.

Можно ли применять обычный метод Лагранжа к неравенству как к равенству? Можно исследовать отдельный случай активной границы, но затем надо проверить знак множителя и отдельно рассмотреть неактивный случай. Полная запись делается через ККТ.

Гарантируют ли ККТ глобальный минимум? Не вообще. Для выпуклой задачи с указанными выше условиями они достаточны; в невыпуклой задаче нужны дополнительные исследования.

Коротко

Метод множителей Лагранжа в нелинейном программировании связывает градиент цели с градиентами ограничений. Для неравенств условия ККТ добавляют знак множителя и дополняющую нежёсткость. В задаче о круге оптимум сначала лежит на границе, затем становится внутренним; проверка выпуклости или прямое сравнение значений превращает найденного кандидата в доказанный глобальный минимум.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Квадратичное программирование: решение задачи по шагам

Квадратичное программирование: решение задачи по шагам

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

11 июня 20268 минут
Метод штрафных функций: оптимизация с ограничениями

Метод штрафных функций: оптимизация с ограничениями

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

10 мая 20267 минут
Условный экстремум: множители Лагранжа без зубрёжки

Условный экстремум: множители Лагранжа без зубрёжки

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

25 марта 20267 минут
Абсолютная и относительная погрешность числа

Абсолютная и относительная погрешность числа

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

8 ноября 20268 минут
Абсолютная пропускная способность СМО: формула

Абсолютная пропускная способность СМО: формула

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

8 ноября 20268 минут
Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

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

8 ноября 20268 минут