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

С точки зрения численных методов существенно также разделение на локальную и глобальную оптимизацию. В определении (2) речь идет о глобальном минимуме, который, однако, найти не просто, и поэтому задачу стараются свести к дискретной оптимизации на множестве локальных минимумов. Опгеделеиие 1. Точка х 6 Х называется точкой локального минимума в ЗМП (1), если Зг> 0: У(хо) < 7(х) Чх 6 ХПО,(хг). Здесь и далее О,(х) обозначает г-окрестность точки х. Лля поиска локального минимума применяются спепиальные методы, которые при определенных предположениях оказываются эффективными.

Тогда как общая задача глобальной оптимизации является гяР-трудной. Лействительно, к ней сводится г1Р-полная. Утвегждеиие 1. ЦЛНссЗМП. ЛокАЗАтельство. Поскольку задача ЛН является частным случаем задачи ЛП, то для сведения ЦЛН к ЗМП достаточно представить условие целочисленности переменных в виде ограничений (неравенств) на вещественные переменные, что нетрудно сделать, например, так: (ху б Е) эквивалентно (ху б Щ г1п~(кху) < О). ' Поэтому методы глобальной оптимизации будут рассмотрены в равд.4, а в данном параграфе остановимся на поиске локального экстремума. Отметим, что для ряда экстремальных постановок задач физики точки локального экстремума имеют самостоятельное значение. Кроме того, существует целый класс ЗМП, для которого локальный экстремум совпадает с глобальным минимумом, это — задачи выпуклого программирования.

ОЛРЕЛЕЛЕНИЕ 2. Функция у называется гыауклой ма Х, если ее надграфик ер1йга$х~ =' ((х, у)~ у > у(х), х б Х) — выпуклое множество. Функпия, выпуклая на всей области определения, называется выпуклой. Множество называется выпуклым, если вместе с любыми 39 двумя своими точками оно содержит отрезок, их соединяюший.

Утверждение 2. Любая точка локального минимума выпуклой функщзи является точкой ее глобального мынимума. ДОИАЗАтельство. Пусть у(х ) > у(х'). Тогда у(х ) > у(х) для всех точек х полуинтервала (хс, х*] (по определению 2), а значит, и в некоторой окрестности хс — противоречие с определением 1. Для решения задач выпуклого программирования применйм метод эллипсоидов, причем в гладком случае отсечение полуэллипсоида проводится на основе градиента невыполненного ограничения в полной аналогии с алгоритмом из зб.

Поэтому зада~а поиска сприближеныого решеняя задачи выпуклого программиговаыия оказывается полиномиально разрешимой. Для осглрых задач выпуклого программирования — когда функция цели убывает в окрестности минимума не медленнее некоторой линейной функцки — можно получить и точное решение. 2. Обшими методами локальной оптимизации (для произвольного, не обязательно выпуклого, случая) являются мешены локалькоео сауска. ОПРЕНЕЛЕНИЕ 3.

Вектор Ь б П~ называется каяравлекаем убывания функции у в точке х, если у(х+аЬ) < у(х) для всех достаточно малых а > О. УтВЕРЖНЕНИЕ 3. Пусть у дифференнируема в точке х. Тогда, если (Исаях), Л) < О, то Л вЂ” направление убывания функции у в точке х, и наоборот, если Ь вЂ” направление убывания функции у в точке х, то (йгадДх), Л) < О. ДОКАЗАтвльство. Из условия дифференцируемости У имеем для достаточно малых а > О: у(х+ аЬ) — у(х) = (йгаоЩх), аЬ) + о(а) = —.а((йгасЩх), Л) + о(а)/а).

Очевидно, последняя добавка не изменит знака выражения в фигурных скобках, если скалярное произведение строго отрицательно или строго положительно. Отсюда автоматически вытекает требуемое утверждение. Таким образом, направление локального убывания дифференцируемой функции должно составлять острый угол с ее антнградиентом, который является в смысле линейного приближения наилучшым направлением убывания Для мнемоники приведем эпиграф к главе, посвяшеыной градиентным методам минимизации, из 1-го издания 40 книги Ф. П. Васильева Численные метаоды решения экситремальных задач: "Вот кто-то с горочки спустился — антиградиент!" Если йга<Щх) = О, то и будет стаацаонараоа гаечкой. Отметим, что в условной оптимизации равенство нулю градиента уже не является необходимым условием мннимума (соответствующие условия будут рассмотрены в у9).

Но в более простом случае Х = К" можно, двигаясь небольшими шагами в направлении антиградиента функции у в текущей точке, прийти в стационарную точку, как правило, локального минимума. Так мы получаем идею ерадиеитиого мешода безусловной мяивмвзаяиа, задаваемого итеративной процедурой ть — т ~,~~,Щ '), 1.— 1,2,..., Ы ' бВ,а. Параметр ат называется шаговым множителем и может выбираться, исходя из различных соображений, разными способами.

1) Пассивные способы — (от) выбирается заранее. Постояннын шаг — ат —— ао для достаточно малых ао. Убывающий шаг (если ао не известно или при наличии помех)— ат ь О, ~" тзт = оо, ~ тттз < оо, например ттт — — 1/1. 2) Адаатввиыс способы — (ттт) зависит от реализующейся (л'). Метод скорейшего спуска — ат Е Ага т1по>о у(в~ тт агадт (* )).

Метод дробления шага (деления пополам) — если Дв'+ ) > Дв'), то возврат к 4-й итерации с ат .— — ттт/2. (Возможно и увеличение шага при стабильном убывании у, т.е. приближенный скорейший спуск.) Правило Армихо — путем дробления шага добиваемся для тзт выполнения условия у(х' — тттйгадЯхт)) — у(вт) < -сат11йгадДвт)~)з. В общем случае дифференцируемой, ограниченной снизу у можно получить сходимость градиентного метода к множеству стационарных точек, а при дополнительных предположениях доказывается (за исключением варианта с убывающим шагом) линейная сиоросшь сяодамостаа, которая в выпуклых задачах означает ~)хт+' — л'~! < йд))вт — в'~) для некоторого О < й < 1. Указанная линейная опенка объясняется тем, что в процессе минимизации градиентным методом используется линейная аппроксимация целевой функции на каждом шаге.

Более высокую скорость сходимостн получают для методов, основанных на квадратичной аппроксимации, в предположении дважды дифференцируемости у. Типичным примером здесь является метаод Ньютаоиа. 41 Пусть г' б Сз(Ка), разложим функцию у в ряд Тейлора в окрестности текушей точки х'. ях)-ях') = (йгаддх ),х-х )+-(1о(х')(х-х"),х-х )+оцх-х1']] ). 2 Выберем х'+' из условия минимизации квадратичной аппроксимации у(х) в точке х', т.е. квадратичной части прирашения у(х)-у(х'), получим метод Ньютона: х'+' = х' — (уо(х')) гйгаг]~(х'), 1 = 1,2,..., где начальное приближение х' должно находиться достаточно близко к точке оптимума х'.

В таком случае (и при дополнительных предположениях, более сильных, чем для приведенной ранее оценки скорости сходимости градиентного метода) для метода Ньютона будет справедлива коаоратичкаа скорость схооамости []хг+г — х*]] < щх1 — х" ~~~, т.е. )~х ь — х")) < — (ф)х — х'~О что предполагает ][х' — х'[[ < 1/Я (оценку для Я см., например, в (5, с. 192]). Еше рвэ подчеркнем, что градиентный метод в отличие от ньютоновского сходится при любом начальном приближении.

Из определения метода Ньютона также следует требование невырожденности матрицы вторых производных (гессиана) функции у. Нетрудно видеть, что полученная формула метода Ньютона решения задач безусловной минимизации совпадает с формулой метода Ньютона решения системы уравнений бгадДх) = О, соответствуюшей необходимым условиям экстремума. 3. Лля задач условной минимизации, например пцп х, з си[1,2] предложенные методы нуждаются в модификации. В частности, для приведенного примера, когда множество Х имеет достаточно простую структуру, указанные выше формулы совмешаются с процедурой проектирования на Х на каждом шаге метода. Так приходим к методу ароекции ериоиеита х"+ = Ргх(х' — а~йгабЩх')), 1 = 1,2,..., Мх б В.".

Лля более сложных множеств Х, допустим, задаваемых ограниче- ниями-неравенствами Х=(хбН~[рл(х)<О ЧвбМ), (3) универсальным способом освобождения от ограничений является их штрафование. А именно для достаточно большой'константы С > О вместо задачи условной минимизации (1),(3) рассматривают задачу безусловной минимизации оштрафованной целевой функции пип (Ц(х) + С,» [у~(х)]"), где ~~~ [у~(х)]"— ° ЕМ юе'М 1пп ппп (у(х)+ С ~[у+(х)]") = 7'. С1аа лейте АТЕМ (4) Если р = 1 (функция-срезка и, следовательно, штрафная функция является острой), то ЭС': ш1п(у(х) + С* ~; м у,+(х)) = У' (сушествует точный штраф). Однако прн р > 1 — сладкий штраф-подобное равенство означало бы несушественность ограничений * б Х (точка безусловного минимума и так находится в Х).

Утвигждннии 4. Пусть |,рл б Сз(К"), выпуклы, р > 1 и ЗС'. х~ =' агкш1п(у(х) + С' 1 [уй(х)]") б Х, тогда х б Агй ппп у(х), т.е. пцп у(х) = ш1пу(х). аеп" леп" тех Локязлтнльство. Так как х~ — точка безусловного экстремума дифференцируемой функции, то градиент оштрафованной функции цели вней равен нулю: йгаЦ(х )+С'р);[рр(х )]г 'йгадрл(х ) = О. Но из условия х~ б Х все выражения в квадратных скобках, а значит, и второе слагаемое равны нулю. Отсюда следует йгаоЩх~) = О, т.е. необходимое условие экстремальности точки хо для задачи безусловной оптимизации, которое в выпуклом случае оказывается и 43 это функаая штрафа (штрафная функция) для ограничений-неравенств, у+() =' шах[О,у()] — среэка у, параметр штрафа р > 1.

(Лругие вилы функций штрафа см. в [4,5].) В условиях непрерывности функций у, у;, непустоты Х и ограниченности множества Лебега функции у можно доказать, что с ростом константы штрафа достаточным (см. утверждение 2). Поэтому я~ — точка безуслов- ного минимума у. Но х Е Х, так что х — и точка условного минимума у" на Х, ибо безусловный минимум не превышает услов- ного. Утверждение дохазано. Таким образом, для гладкого штрафа не удается свести задачу условной минимизации к безусловной, тем не менее формула (4) по- зволяет итеративно комбинировать метод штрафов и градиентный метод в следующей процедуре: 1Ух' Е Н.в х+ = х'-о~(бгаЦ(х )+С~р~ь ]у+(х )]э ~йгадяс(х )), 1 = 1,2,..., гем которая сходится при определенных соотношениях между (аф) и (СД, в частности для убывающего шага при 2 , 'озСз '< оо (напри- мер, а~ — — 1/$, С~ < ~/3).

Утверждение 4 показывает, что траеятории метода штрафа про- ходят, вообще говоря, вне множества ограничений Х, хотя и сходят- ся к данному множеству. Из-за этого рассмотренный метод иногда также называют методом внешних штрафов в отличие от методов евушрекксй взочкв, или барьеров. Типичным примером применения метода барьеров является описанный в з7 метод Кармаркара, когда.