§2. Метод множителей Лагранжа

Метод множителей Лагранжа является классическим методом решения задач математического программирования (в частности выпуклого). К сожалению, при практическом применении метода могут встретиться значительные вычис­лительные трудности, сужающие область его использования.

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

Рассмотрим классическую задачу оптимизации

₍₄₎

Эта задача выделяется из задачи (1)- (3) тем, что среди ограничений нет неравенств, нет условий неотрицатель­ности переменных, их дискретности, т < п и функции f(х) и φ_i(x ) непрерывны и имеют частные производные по крайней мере второго порядка.

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

Предположим, что в точке х* функция f(х) имеет ло­кальный условный экстремум и ранг матрицы равен т. Тогда необходимые условия запишутся в виде:

⁽⁵⁾

где

⁽⁶⁾

есть функция Лагранжа; λ₁,... , λ_m – множители Лагранжа.

Существуют также и достаточные условия, при выполне­нии которых решение системы уравнений (5) определяет точку экстремума функции f(х). Этот вопрос решается на основании исследования знака второго дифференциала функ­ции Лагранжа. Однако достаточные условия представляют главным образом теоретический интерес.

Можно указать следующий порядок решения задачи (5) методом множителей Лагранжа:

1) составить функцию Лагранжа (6);

2) найти частные производные функции Лагранжа по всем переменным х₁,... , х_п, λ₁,... , λ_m и приравнять их нулю. Тем самым будет получена система (5), состоящая из п + т уравнений. Решить полученную систему (если это окажется возможным!) и найти таким образом все стационарные точки функции Лагранжа;

3) из стационарных точек, взятых без координат λ₁,... , λ_m, выбрать точки, в которых функция f(х) имеет услов­ные локальные экстремумы при наличии ограничений. Этот выбор осуществляется, например, с применением доста­точных условий локального экстремума. Часто исследование упрощается, если использовать конкретные условия задачи.

§3. Градиентные методы

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

Рассмотрим задачу максимизации нелинейной дифференцируемой функции f(х). Суть градиентного поиска точки максимума х* весьма проста: надо взять произвольную точку х_о и с помощью градиента , вычисленного в этой точке, определить направление, в котором f(х) возрастает с наибольшей скоростью, а затем, сделав небольшой шаг в найденном направлении, перейти в новую точку x₁. По­том снова определить наилучшее направление для пе­рехода в очередную точку х₂ и т. д.

Таким обра­зом, надо построить последовательность точек х_о, x₁,... так, чтобы она сходилась к точке максимума х*.

Градиентные методы, как правило, позволяют получать точное решение за бесконечное число шагов и только в неко­торых случаях – за конечное. В связи с этим градиентные методы относят к приближенным методам решения.

Движение из точки x_k в новую точку х_k+1 осуществляется по прямой, проходящей через точку x_k и имеющей уравнение

где λ_k — числовой параметр, от которого зависит величина шага.

Градиентные методы отличаются друг от друга способом выбора величины шага. Распространенным является вариант градиентного поис­ка, называемый методом наискорейшего подъема.