Н.М. Новикова - Дискретные и непрерывные задачи оптимизации, страница 9

задача (9), эхвивалентная задаче условной минимизации пип р(х), Ф>з, T. ~з — -и сводится к безусловной минимизации специальной барьерной функ- ции й(х), не позволяющей методу Ньютона выйти за ограничения х ) О, если в этих ограничениях выбрано начальное приближение. Различные виды барьерных функций см. в [4,5] — для них характер- но быстрое возрастание при приближении изнутри к границе множе- ства ограничений (тогда яак штрафная фуняция стремится х нулю при приближении к множеству ограничений — извне).

Зля реше- ния общей задачи МП (1),(3) с ограничениями-неравенствами мето- ду Кармархара соответствует использование вместо рассмотренной выше штрафной фуняции, основанной на срезке, лоеаряфмическов барьерной фуняции, равной 1 — — ! и(-у;(я)] С. 44 при у;(х) ( 0 уг б М и +со в противном случае. Эта функция также прибавляется к целевой, и справедливо соотношение, аналогичное (4). Другие способы сведения задач условной оптимизации к безусловной, основанные на методе множителей Лагракжа, будут вытекать из результатов следующего параграфа.

З9. Двойственность в МП Необходимыг условия локального минимума обобивенно дифференчиругмых функиий нри ограничениях«неравенствах. Теорема Куна-Твккгра. Понятие о регулярносгли ограничений-неравенств в задаче МН. Метод множителей Лагранжа. 1. В этом параграфе будем рассматривать задачу условной оптимизации (1) с Х С В,, Х ф й, по преимуществу, с ограничениями неравенствами (3).

Как уже отмечалось, условие равенства нулю градиента для таких задач может не иметь никакого отношения к точкам условного экстремума. Поэтому выведем соответствующие необходимые условия для рассматриваемого случая. Вначале они будут даны в достаточно общей форме, допускающей применение для широкого класса задач МП (кусочно-гладких и при произвольным образом заданных ограничениях, а также не обязательно конечно- мерных). Затем проведем конкретизацию для ограничений (3). Для обычных задач МП (конечномерных, с дифференцируемыми функциями) справедливы все дальнейшие построения и выводы при замене знака T обычным градиентом.

Таким образом, основой обобшения является следуюшее ОПРЕЕЕЛЕНИЕ 4. Функция у называется диффгргнииругмоб во Адамару в точке х б В.", если существует вектор (уу(х) б Вн, такой .что Уу б йн выполнено: "'+'"' "*'=( Л*) у) (ч,у') (+О,у) T Для бесконечномерных задач, когда у — функционал: Š— Вг, где Е— некоторбе функпиональное пространство, требуется: Чу(х) б Е' для пространства Е', сопряженного к Е, и х, у б Е. В гладком случае ~Дх) = йгацу(х) и можно положить у тождественно равным у. 45 В безусловной оптимизации существенную роль играли направления спуска (убывания целевой функции). В условной оптимизации, кроме убывания целевой функпии, требуется отслеживать еще н невыход за ограничения. Поэтому вводится понятие возмохсиого или доиуси»имаго направления в точке х Е Х для множества ограничений Х как такого вектора у, для которого Это > 0: х+ту Е Х Ыт Е и(0, тв].

Замыкание множества всех допустимых направлений в точке х для Х дает. следующее Опгкдклкник б. Кои»иииггшаиым хоиусом н множеству Х в точке х называется множество векторов К(Х, х) =' (у) В ((»»> у»))~ »: (т», у») -> (+О, у), х+ т»у» Е Х Ы1). Очевидно, для й (с Х К(Х, х) = 9, а для х' Е )п»Х К(Х, х') = =В.и. Для х Е дХ в случае гладкой границы конус К(Х,х) называется также конусом каса»игльиых и соответствует касательным направлениям для ограничений-равенств. Ткогкмл 1 (воша») вид необходимых условай лохальиого минимума в задаче (1)). Пусть фуннция 1 дифференцируема по Адамару, Х С Ка> Х )1 9, хо — точка локального минимума ) в задаче (!), тогда Ыу Е К(Х, х ) (»>>>,»(х ), у) > О.

Локлзлткльстно. Выберем у Е К(Х,хо). Зля соответствующих ему по определению 5 (т»,у») выполнено хо + т»у» Е Х, и, начиная с достаточно большого 1> хо + т»у» Е Х П О,(хо) (ябо т» 0), следовательно, по определеняю 1 1(хо + т»у») > 1(хо). В пределе получим Пш ,)'(х + ту') — 1(х ), 1(х + т»у») — 1(х ) — 1цп > О, (т,г')-(+о,г) т (т>,г>) (+в,г) »» и требуемое соотношение вытекает из определения 4.

Содержательно данные условяя означают, что среди допустимых направлений в точке локального минимума не должно быть направлений убывания целевой функции (см. утверждение 3 18). Однако в таком общем виде этими условиями не удобно пользоваться. Конкретизируем полученные условия для ограничений-неравенств, когда Х задается формулой (3). Введем Ых Е Х множество 46 индексов о(н) = (1 б М! у;(и) = О) — активных ограничений в точке н, т.е. таких неравенств из (3), которые в этой точке выполнены как равенства.

И определим множество (конус) 0(х) =' (у б П."~ (17у~(х),у) < О йу б,7(х)). Опгеделение 6. Множество Х для ограничений неравенств (3) называется регу ырным о нзочке х б Х, если 0(х) С К(Х, н). ТЕОРЕМА 2 (необяооимые услооия зонального минимума с ограничениями.мераоенстоами7'. Пусть функции 7, у; % б М дифференцируема по Адамару, Х ф 9, хо — точка локального минимума 7" в задаче (1),(3) и множество Х регулярно в точке но. Тогда ЗЛ > О: (7Ц(хо) + ~~, ' Л,у (но)) О (5 у и з(ио ) Поклзятелъство.

По теореме 1 и из определения регулярности Х в во следует, что (177(но), у) > О для всех у, удовлетворяющих условию (~уу(х ), у) < О Уу' б 7(х ). Значит, по определению 3 З7, линейное неравенство ((77(н~),у) > О является следствием системы линейных неравенств (((7у (х ),у) < О Уу б 7(н~)). Приведя это неравенство к стандартному виду ( — (77(н~), у) < О и применив афинную лемму Фаркаша (З7), получим, что ЭЛу > О: — ~~(х ) = ~~~ Лу~уу(н~).

уев(оо) Таким образом, для регулярных ограничений необходимым условием локального минимума в гладкой задаче (1),(3) является равенство нулю дифференциала функции в фигурных скобках в (5) для хоть каких-нибудь Лу > О. Чтобы не записывать в явном виде множество активных ограничений, вводят фунниию Лагриннса Ь(Л,н) = 7(х)+ ~ Л уу(х) =' Дх) +(Л,у(но)) укм (регулярной) задачи (1),(3), где вектор-функция у( ) =' (уу( ) ~ 7' б М). Из теоремы 2 следует, что равенство нулю дифференциала функции Лагранжа для Л. > О также является необходимым условием локального минимума в регулярной задаче (1),(3), ибо миоживзгли Лаграижа Л, соответствующие неактивным ограничениям, можно взять равными нулю.

Последнее условие записывается как (6) (Л,у(х )) = О и называется условием доволкяющсй иежгсюкосгви. Итак, доказана ТеОРемА 3 (вриииив овщималькосвги Лагранжа). В предположениях теоремы 2 для задачи (1),(3) сушествует неотрицательный вектор множителей Лагранжа Л > О, такой, что для х выполнены о услогия овгаимальиости — (6) и ~ Цхо, Л) = О. Пля выпуклых задач (1),(3) данные необходимые условия являются в регулярном случае и достаточными, и может быть доказана ТЕОРемА 4 (Кука, Таккгра). Если в задаче (1),(3) функции 7, уу б С (1Еи) выпуклы и множество Х регулярно (в любой точке), то х' — точка оптимума в этой задаче тогда н только тогда, когда в ней выполнены условия оптимальности для Л > О.

докАзАтелъстВО. Необходимость следует из предыдуших теорем, покажем достаточность. Пля данного Л в точке х' выполнено условие экстремальности х' для функции Е(., Л). С учетом неотрицательности Л эта функция выпукла по х, значит, х' является точкой ее минимума (см. утверждение 2 18). Отсюда и из условия дополняюшей нежесткости получим, что у(х') = Дх*)+(Л,у(х')) = ь(х*, Л) < И(х, Л) =' у(х) + (Л, у(х)) < у(х) 1гх б Х (ибо у (х) < О для х, удовлетворяющих ограничениям), что и требуется в определении (2). Аналогичные теоремам 2-4 утверждения справедливы и для случая, когда Х задается ограничениями-равенствами, и для смешанных систем ограничений равенств и неравенств: уу(х) < О, у<(х) = О.

Только на соответствующие ограниченням-равенствам множители Лагранжа Л; не надо накладывать условия неотридательности, а на условие дополняющей нежесткости этн ограничения не влияют (в случае ограничений-равенств вообще опускаем (6) и приходим к классическому врагилу миожиглслгй Лагранжа). 2. Теперь вспомним, что полученные условия являются значимыми лишь в предположении регулярности ограничений, для которого определение 6 не дает конструктивного способа проверки. В данном 48 пункте будут рассмотрены некоторые достаточные условия регуляр- ( ности ограничений неравенств (3) для гладких задач.

Кроме 0(х), определенного в п.1, введем также множество Со(х) =' (у б В,"~ ('7уу(х),у) ( О )() б,l(х))» отличающееся заменой нестрогого неравенства строгим. Но это множество уже включается в контингентный конус. УтВЕРЖДЕИИе 5. В предположении дифференцируемости по Адамару (или обычной дифференцируемости) функций уу, задающих ограничения (3), Со(х) С К(Х, х) »»х б Х.