3.4 Обобщенное правило множителей Лагранжа

Более содержательные необходимые условия минимума могут быть получены, когда жо — локальный экстремум задачи (3.3), для которого конусы Гг-, г = 0,1,..., га + 1, непусты и выпуклы. Тогда по теореме Дубовицкого-Милютина существуют не равные нулю одновременно векторы с; 6 Г*, г = 0,1,..., га+1, такие, что со +.. . + ст+1 = 0. Это достаточно общее условие экстремума для задач с ограничениями уточняется в данном параграфе.

Рассмотрим следующую задачу:

тт/(ж), (3-4)

срг(х) < 0, i = l,...,s, (3.5)

щ(х) = 0, 1 = 8 + 1,... ,к, (3.6)

ж е О С Пп. (3.7)

Считаем, что функции /, - непрерывно дифференцируемы, О - выпуклое, замкнутое множество, гЫС ф 0. Как правило, мно­жество О имеет простую структуру. Например, О = {ж | жг- > 0, г = 1,.. .,п}.

Покажем, что при этих предположениях можно воспользовать­ся необходимым условием экстремума из теоремы 3.6 и теоремой Дубовицкого-Милютина. Для этого представим задачу (3.4)-(3.7) в виде задачи (3.3), введя следующие множества Со = {х \ /(х) < Дж0)}, Ог = {ж | срг(х) < 0}, г = 1,..., в, От = С,От+1 = {ж | 1^ч(х) = 0, г = в+ 1,..., к}, где га = в+ 1 и жо — допустимое реше­ние задачи (3.4)-(3.7). Доказательство непустоты и выпуклости конусов Гг-, г = 0,..., га + 1, основывается на следующих утвер­ждениях.

Лемма 3.7 Пусть /(ж) — непрерывно-дифференцируемая функ­ция и /'(жо) ф 0. Тогда конус Го является открытым выпуклым множеством и

Т0 = {ееКп\ </'Ы,е> < 0}.

Лемма 3.8 Пусть <~р{(х) — непрерывно-дифференцируемая функ­ция, для которой справедливо либо </зг(жо) < 0, либо ¥>'(жо) ф О. Тогда конус Гг- является открытым выпуклым множеством и

 

Кп,   если <~р{(хо) < О, {е е В:71 \ (</?'(ж0),е) < 0},   если </?г'(ж0) = О.

Лемма 3.9 Пусть О — выпуклое множество из Ка, гЫС ф 0 и жо € О. Тогда конус Тт является открытым выпуклым множе­ством и

Тт = {е £ Па | е = г/(ж — жо), V > 0, ж 6 гЫС}. Заметим, что если жо € тЮ, то Гт = Ка.

Лемма 3.10 Пусть <^г-(ж),г = в+ 1,..., к, — непрерывно-диффе­ренцируемые функции. Тогда конус Тт+\ является замкнутым выпуклым множеством и

Гт+1 ={ееПа\ <¥>-Ы,е) = 0,г = 5+ 1,...,к}.

Доказательство лемм 3.7-3.10 можно найти в [1].

Теорема 3.7 (Обобщенное правило множителей Лагранжа) Пусть жо — оптимальное решение задачи (3.4)-(3.7). Тогда существу­ют величины А°, г = 0,..., к, не все равные нулю, такие, что

А° > 0, г = 0,...,з,

А°(^г(ж0) = 0, i = l,...,s,

к

(АоГЫ + £ ХЫЫ, х - ж0) > 0

г = 1

для любого х из О. (Величины А° принято называть множите­лями Лагранжа.)

Доказательство. Убедимся сначала, что без ограничения общ­ности можно предполагать выполненными следующие условия:

1) ГЫ ф о,

2) для любого г = 1,..., в, либо </?г'(жо) < 0, либо ¥,'(жо) ф 0. Действительно, пусть /'(жо) = 0. Тогда теорема верна при

Ад = 1, А° = 0, г > 1. Предположим теперь, что </зг-(жо) = 0 и (^'(жо) = 0 при некотором г = 1,... ,й. Тогда теорема верна при А° = 1,А° = 0^-/г.

Из лемм 3.7-3.10 следует, что конусы внутренних и предель­ных направлений из точки жо выглядят следующим образом:

Г0 = {ее Д" | </'Ы,е> < 0},

для любого 1=1,. . . ,в

_ Г i?^г,   если </?г(ж0) < 0,

1 ~ \ {е£Еп\ (^(ж0), е) < 0},   если ^(ж0) = 0,

Гт = {е £ _йп | е = 1у(х — жо), г/ > 0, ж 6 гга^С},

Гт+1 ={ееДп | (^'(ж0),е) = 0,^ = 5+1,...,/г,}.

Все эти конусы непусты и выпуклы. Так как жо — оптималь­ное решение задачи (3.4)-(3.7), то П™"^1^ = 0. Тогда из теоремы Дубовицкого-Милютина следует, что существуют не равные ну­лю одновременно векторы с{ 6 Г*, г = 0, ...,га+ 1 такие, что со + С1 + ... + ст+1 = 0.

Посмотрим, что представляют собой в рассматриваемом слу­чае сопряженные конусы. Прежде всего покажем, что

Гц = {с0 | с0 = -А0/'(ж0), А0 > 0}.

Из определения сопряженного конуса следует, что со принад­лежит Гц тогда и только тогда, когда для любого е 6 Го верно (со, е) > 0. Отсюда получаем, что конус Гц содержит всевозмож­ные векторы вида — Ао/'(жо), где Ао > 0.

Покажем, что

ПС{со|со = -Ао//Ы,Ао>0}.

Пусть вектор с не принадлежит выпуклому замкнутому множе­ству {со | со = — Ао/'(жо), Ао > 0}. Тогда по первой теореме отде­лимости существует ненулевой вектор е такой, что ( — Ао/'(жо), е) > (с, е) при любом Ао > 0. Полагая Ао = 0, получим (с, е) < 0. Будучи поделенным на Ао > 0 при Ао —> со неравенство дает (/'(жо),е) < 0. Значит, с не принадлежит конусу Гд. Точно так же

Г* = {сг | сі = -Хгср'г(х0),Хг > 0}

для тех і < в, при которых (рі(хо) = 0. Если же (рі(хо) < 0, то Г* = {0}. Следовательно, при всех і < в имеем

Г* = {сг | сі = -\і(р'і(х0), Хг > 0, Хгсрг(х0) = 0}.

Легко проверить, что

к

Т*т+1 = {ст+1 | ст+і = - ^2 \цр[(х0)}.

і=в+1

Таким образом, учитывая полученные представления сопряжен­ных конусов и равенство со + с\ + ... + ст+і = 0 получаем:

к

ст = А°/'ы+ЕА^:-ы є с

г = 1

А°>0, г = 0,...,5,

А°(^г(ж0) = 0, і = 1,..

где А°, г = 0,..., к, - некоторые множители, которые не должны быть равны нулю одновременно (условие нетривиальности набора векторов сі, 0 < і < т + 1).

По определению конус состоит из векторов с, удовлетво­ряющих неравенству (с, и(х — жо)) > 0 при всех и > 0 и любых ж £ тЮ. Так как любая точка выпуклого множества О является предельной точкой множества гЫС, то для с £ при всех х £ О выполняется (с, ж — жо) > 0 и, следовательно,

к

(ХОоГ(хо) + ^2Х^'Ы,х-хо)>0

1=1

для любого ж из С Теорема доказана.

Необходимые условия оптимальности теоремы 3.7 называются обобщенным правилом множителей Лагранжа, а величины А°, г = О,..., к, — множителями Лагранжа. В теореме 3.7 нельзя ис­ключить случай, когда множитель Ад при градиенте целевой функ­ции /'(жо) равен нулю, и тогда необходимые условия экстремума не зависят от оптимизируемой функции. Такие задачи назовем вырожденными в точке жо- Один из способов, позволяющих вы­делять классы невырожденных задач, дает теорема Дубовицкого-Милютина. Если Ад = 0, то со = 0 и с\ + ... + ст+\ = 0. Из лемм 3.7-3.10 следует, что конусы Г1,Г2,...,Гт — открытые множе­ства. Следовательно, по теореме Дубовицкого-Милютина имеем

Г1ПГ2П...ПГт+1 =0.

Значит, если пересечение данного множества конусов непусто, то равенство Ад = 0 исключается. Наиболее просто условия, гаран­тирующие отличие Ад от нуля в обобщенном правиле множите­лей Лагранжа, получаются для тех задач (3.4)-(3.7), в которых О = Ка.

Теорема 3.8. (Необходимые условия Куна-Таккера) Пусть жо - оптимальное решение задачи (3.4)-(3.7), О = Ка и множество {(^'(жо) | ¥г(хо) = 0} - линейно независимо. Тогда существуют множители А°, г = 1,.. .,к, такие, что:

А° > 0,г= (3.8)

56

\г(рг(х0) = О, г = 1,..., в, (3.9)

к

/'ы + ЕА°^ы = о.

(3.10)

1=1

Доказательство. Из условия О = Ка следует, что неравенство (с, х — хо) > 0 может быть выполнено для всех х £ О только при с = 0. Следовательно, по теореме 3.7 имеем

Если А° = 0, то Е^=1 = Е{А°¥>'(жо) | ¥>*Ы = 0} = 0, что

противоречит условию теоремы о линейной независимости мно­жества {(^'(жо) | <-Р{(хо) = 0}. Поэтому обе части равенства (3.11) можно разделить на А[] > 0. Понятно, что множители А°/А[], г = удовлетворяют необходимым условиям (3.8)-(3.10). Тео­рема доказана.

Рассмотрим равенства (3.9), (3.10) и ограничения </зг(жо) = 0, г = ..., к. Они образуют систему из к + п уравнений с к + п неизвестными А°, г = 1,..., к; х^ j = 1,.. .,п. Используя какой-нибудь численный метод решения подобных систем, можно най­ти решение (А°,жо). Однако, в силу того, что условия (3.8)-(3.10) не являются достаточными условиями оптимальности, точка жо может даже не быть локальным экстремумом задачи (3.4)-(3.7). Необходимые и достаточные условия оптимальности удается по­лучить для более узких классов нелинейных задач. Например, для задач выпуклого программирования, которые рассматрива­ются ниже.