Лекция: Правило множителей Лагранжа

 

Рассмотрим так называемую классическую задачу на условный минимум или задачу с ограничениями в виде уравнений.

Пусть на заданы функции, .

Положим .

 

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

Теперь определим на вектор-функцию. Тогда, для краткости, запишем .

Введем следующую функцию:

,

 

где. Эта функция переменных называется функцией Лагранжа. Переменные называются множителями Лагранжа.

Теорема 1. (Правило множителей Лагранжа) Пусть функции непрерывно дифференцируемы на , точка такова, что система векторов линейно независима. Если – локальный минимум функции на множестве, то существует вектор такой, что

. (1)

Согласно определению функции Лагранжа условие (1) можно записать как систему равенств

 

.

Как использовать эту теорему для отыскания условных экстремумов? Составим систему

(2)

Запишем систему (2) подробнее:

Она состоит из уравнений относительно переменных. Пусть вектор – некоторое ее решение. В этом случае вектор называется условно стационарной точкой функции. Таким образом, решая систему (2), мы можем найти все условно стационарные точки. Среди них содержатся все точки условного локального минимума.

Теорема 2. (Необходимое условие условного минимума второго порядка) Пусть выполнены все условия теоремы 1 и, кроме того, функция дважды дифференцируема в точке. Тогда для того, чтобы была локальным условным минимумом, необходимо, чтобы матрица была неотрицательно определена на подпространстве

.

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

Теорема 3. (Достаточное условие условного минимума второго порядка) Пусть выполнены все предположения теоремы 2. Тогда для того, чтобы условно стационарная точка была локальным условным минимумом, достаточно, чтобы матрица была положительно определена на подпространстве .

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

 

 

Задача нелинейного программирования

 

Рассмотрим теперь задачу на условный минимум с ограничениями в виде неравенств. Поло-

жим Часто простейшие ограничения системы неравенств выписывают от-

дельно. Например, такими ограничениями могут быть ограничения на знак переменных. В этом

 

случае .

Целевая функция и все функции, вообще говоря, нелинейны, поэтому такую задачу отыскания условного минимума называют задачей нелинейного программирования.

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

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

Введем следующие определения.

Определение 3. Ограничение с номером ( ) называется активным (или жестким) в точке, если .

Определение 4. Ограничение с номером i ( ) называется пассивным(или нежестким) в точке, если .

Множество номеров всех активных в точке ограничений обозначим. Таким образом,

.

Определение 5. Пусть в задаче нелинейного программирования; векторы,,. Будем говорить, что вектор удовлетворяет условию дополняющей нежесткости, если выполнено равенство

. (3)

Условие (3) можно записать как. Отсюда, в силу знакопостоянства слагаемых,. Поэтому, если -тое огра-ничение задачи нелинейного программирования пассивно в точке, то. Таким образом, ограничение на знак множителя Лагранжа является в

точке активным. Если же (ограничение на знак в точке пассивно), то, что означает активность -того ограничения задачи в точке .

Теорема 4. Пусть в задаче нелинейного программирования. Пусть неотрицательные векторы, таковы, что для всех. Тогда удовлетворяет условию дополняющей нежесткости.

Доказательство. По условию теоремы

,

то есть

. (4)

Покажем, что отсюда следует неравенство

(5)

Действительно, если найдется значение ( ) такое, что, то, полагая для всех из неравенства (4) имеем при любых неотрицательных значениях компоненты, что невозможно при достаточно больших .

Итак, (5) имеет место, поэтому с учетом неотрицательности вектора получаем, что .

Так как векторы и ,

. (6)

С другой стороны, из (4) при получаем

 

. (7)

Из (6) и (7) следует (3). Что и требовалось.

Теорема 5. Пусть в задаче нелинейного программирования. Пусть неотрицательные векторы, удовлетворяют условию дополняющей нежесткости и неравенству

. (8)

Тогда вектор – решение задачи нелинейного программирования.

Доказательство. Из (8) и (3) получаем

. (9)

Пусть. Тогда и, так как, имеем. Отсюда и из (9) получаем. Что и требовалось.

Заметим, что в условиях теоремы 5 точкаявляется условным минимумом функции по переменным на неотрицательном ортанте

-мерного евклидова пространства.

Определение 6. Неотрицательный вектор называется седловой точкой функции

Лагранжа, если для всех и выполняются неравенства

. (10)

Теорема 6. (О связи седловой точки функции Лагранжа с решением задачи нелинейного программирования) Если – седловая точка функции Лагранжа, то вектор – решение задачи нелинейного программирования.

Справедливость этого утверждения непосредственно вытекает из теорем 4 и 5.

Теорема 6 – достаточное условие оптимальности, но оно, вообще говоря, не является необходимым. Например, седловых точек не существует в случае, если. Существуют также задачи нелинейного программирования, у которых, но их функция Лагранжа не имеет седловых точек ([2], стр. 238). Тем не менее, для некоторых классов задач нелинейного программирования наличие седловой точки функции Лагранжа является не только достаточным, но и необходимым условием оптимальности (см. теоремы Куна-Таккера в разделе «Выпуклое программирование»).

еще рефераты
Еще работы по информатике