И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 7
Текст из файла (страница 7)
В связи с этим  — оптимальный на классе (Р, Х) алгоритм А (В, Р, Х) определяется, с помощью вспомогательных функций В„В, и множества В,, как решение задачи минимизации по А ~ й А заданной функции шах В,(А, уз» (А, 7, Х) при заданных «,х)е!е.х! ограничениях В, (А, у~~с (А, г', Х)) ~ В„т. е, А(В, Р, Х) = агй ппп шах В,(А, у' (А, Г, Х)). АЕА,В,(А,«чг(А,1 Х))ЕВ, ШХ)Е(Р,Х) Следует отметить, что если для класса (Р„Х,) построен оптимальный алгоритм А, = А (В, Р„Х,) и затем оптимальные алгоритмы А, и А, соответственно для более узких классов (Р„Х,) и (Р„Х,), удовлетворяющих условию (Р„Х,) [) (Р„Х,) = (Р,, Х,), то это еще не значит, что алгоритм А, уже не нужен и можно заменить его построенными более эффективными алгоритмами А, и А,.
Очевидно, такая замена оправдана лишь в тех случаях, когда повышение эффективности А, и А, по сравнению с А, компенсирует дополнительные затраты йа проверку принадлежности ((", Х) ~ с" (Р„Х,) при выборе требуемого алгоритма А„( = 2, 3. Однако проверка принадлежности практической задачи Д, Х) определенному классу задач (Р(, Х() зачастую оказывается почти неосуществимой и поэтому «ранжировка по эффективности» существующих алгоритмов также оказывается весьма проблематичной.
В большинстве случаев правдоподобную оценку эффективности алгоритма дает лишь вычислительный эксперимент. 0.3. Методы отсечении Приведем примеры успешного применения методов отсечений ' для решения ряда важных задач оптимизации.
1, Мввиииввчив квввивыиуквв)н Функций Функцию (' ( [а, И вЂ” «В, [а, Ы ~ В, называют квазивыпуклой, если для любых а < х)< х»( Ь неравенство Г (х,) ~ ) (х,) влечет неравенство х* агд ппп 1 (х) ( х,; а неравенство 1 (х,) ) Г (х») к«(и») влечет неравенство х*~ х,. Поэтому, выбрав х,= (а + Ь вЂ” з)(2 и х,= (а+ Ь+ е)/2, в случае 1(х,) ~ 1 (х,) получим х*~ Х' [х„Ы, а в случае 1 (х,) ~ 1 (х«) получим х'~ Х' = [а, х,[, т. е. в обоих случаях вместо [а, Ь! найдем новый (почтн вдвое короче) отрезэк Х' локализации х*. Повторяя этот процесс, будем находить все более короткие отрезки локализации решения [а, И ~ Х' ~ =эХ»~...
Более эффективные и даже оптимальные алгоритмы локализа. ции х' (по методу Фибоначчи и золотого сечения н другие) описаны в $1.1 — 1А. 24 В. Метод минерале. Мввимиеации лииывцевых Функций Утверждение 1. Если функция Р является минорантной для 1 на множестве Х, т. е. для всех хЕ Х, Р (х) (~(х), х ~ Х, то хе = ага ш[п)'(х) ЕХр з [х[Р(х) ~~(х)) П Х, «рх ! (хе) Е [!и! Р(х), 1(х)!. «зх Действительно, для всех х !2 Хр имеем )'(х) ~ Р (х) ) 1(х). С л е д с т в и е 1. Если Хл= (хт, х«, ..., хл) с:Х, Мм=ш!п~(х~) =~(х~ ) 1-1,л Сл ( т !и Р (х), «ех то ~(х«)Е[Сл, Мл) Поэтому при достижении неравенства Мл — См ( е получим у (х') — 1(х«) ~ з.
Утверждение 2. Если функция ! липшицева на Х, т. е. существует константа Липшица Ь, для которой [ ~ (х') — ~ (хт) [ = Е [ х' — хл ~ прн х', х' Е Х, то функция Рл(х) = шах Ц(х') — Ь[[х — х'[) ~з 1ь»» является минорантой для 1. Поэтому для минимизации липшице- вой функции можно использовать следующий Алгоритм 1: выбираем произвольное х' ~ Х, полагаем Х, = = (х'), А! = 1 и для У = 1, 2, ... вычисляем х"+' = ага ппп Рл (х), «ЯХ Хл+1 =Хи [) [хи+').
Утверждение 3. Если последовательность х', х', ... построена с помощью Алгоритма 1 для липшицеаой функции 1, то !!ш1(хл) = !п1~(х), л» «6х а если при этом Х вЂ” компакт, то 1пп х" = х*. 3. Мивимваацив аывуилых функций, Метод аллин«аидов Утверждение"4. Если функция 1выпукла и ограничена на х ~ Е Л" их Е Х, то существует такое С„-Е В", что линейная функция Р-,р(х) ив м (С;, х — х) +) (х) 25 является минорантой для г на Х, т.
е. для всех х Е Х Р-„~ (х) -Я (1 (х) и, очевидно, Р-„(х) = / (х). С л е д с т в и е 1. Если х' Е Х, то хк с Х: (х ! Рк ~ (х) «( ~ (х') ) П Х, С л е д с т в и е 2. Если х', х', ..., х" р Х, то х«ЕХл а Х П (х!Р„к,(х)(~(х9) Это позволяет исходную задачу минимизации 7 на Х заменить задачей минимизации г на «меньшем» множестве Хл. По-видимому, представляет практический интерес выбирать значения х', х', ..., хл, ...
таким образом, чтобы множество Х ч эффективно «уменьшалось» с ростом У. Для этого целесообразно выбирать элементы х' поближе к центру тяжести или чебышевскому центру множества Х~ Строятся также (у, У)-оптимальные методы, в которых элементы х', х', ..., х" выбираются таким образом, чтобы обеспечить минимальное значение меры к (Хл) (например, диаметра Хл). Особо эффективным оказался следующий метод эллипсоидов (417).
Предположим, что известно число 1«, и точка х' ~ В", удовлетворяющие условию ~ х' — хк !! ( ям т. е. х* принадлежит шару 5 (х», Я,) радиуса Я, с центром в точке х'. Тогда х" принадлежит также и полушару 5,(х~, Я,) = 5 (х', 1«,) (! (х (Р;! (х) (7 (х')). Построим (это нетрудно) гиперэллипсоид минимального объема, содержащий 5, (х', Я,) и затем с помощью линейного преобразования «растянем» пространство таким образом, чтобы данный гиперэллипсоид опять превратился в шар. Очевидно радиус 1««этого нового з Р к ю Р к,(к;«,кт:7Л. и у, повторяя данный процесс, можно локализовать хк в шарах все меньших радиусов.
В итоге получаем последовательность (х"'„ удовлетворяющую неравенствам !! х»+' — хк !! ( д ~ х» — х* ( при независимом (!) от! значении д = 1 — »7»п»( 1, т. е. 1!ш х» = х*. Этот метод легко приспосабливается и для минимизации выпуклой функции ! на заданном выпуклом множестве Х ~ (х ~ д' (х) ( ( О, ! = 1, т) с выпуклымифункциямид': В"-к. 11. Действительно, введем вспомогательную функцию Р (х) = 1 (х) на Х и Р (х) = = д'»(х) вне Х (1„= агяшах д'(х")). Так как Агд ш!п~(х) с с ««х Р Ага ппп Р (х) = Х и при этом Р выпукла вне Х ( нетрудно проверить, что Р -=Рк при хбХ и Р»-=Р„~ при х(с «»Р к~/ к»Р «~«К Я Х), то требуемый полушар можем «отсекать» с помощью Р,- 26 Формально к методам отсечений можно отнести и методы лакал лизации решений на подмножествах Х ~ Х тех элементов х, которые удовлетворяют необходимым условиям оптимальности.
Часто необходимые условия оптимальности оказываются достаточно конструктивными и позволяют отыскать х* (либо локализовать его в «достаточно малых» подмножествах Х). 0.4. 0 локализации решений с помощъю необходимых и достаточных условий оптималъности. Дополнителъная терминология 1. Необходимые уелоелл оцтлмальвоетм длл длффевеццируемых фуввцлй Функцию г называют дифференцируемой в точке х, если существует такой вектор ЧГ' (х), что для всех х в окрестности хсправедливо асимптотическое равенство Г(х) = Г(х)+ (71(х), х — х) + о(!~х — х!!). Вектор Ч) (х) называют градиентом или производной функции Г' в точке х.
Утверждение 1. Оптимальное решение хе, минимизирующее дифференцируемую функцию г" на множестве Х, находится либо на границе Х множества Х, либо на множестве Х* решений х* уравнения Ц (х) = О. Следовательно, задачу минимизации г' на Х можем заменить задачей минимизации Г' на подмножестве Х = Х () (Хе () Х) ~ Х. Справедливость утверждения 1 следует из того, что предположение 7г (х*) чь О для хе Я Х ведет к противоречивому (при малых 2, ) 0) неравенству Г (х* — ) !Ч (х*)) = Г (хе) — )!, ~~ у)' (х') ~~ + + о ()!) < у (хе).
Если существует )' (х», г) ~1)ш (!". (х»+ Хг)— о+ — Г(х»))/Х, то Г'(х', г) называют производной по направлению г для функции Г' в точке х". Утверждение 2. Если г дифференцируема в точке х», то г' (х», г) = (Ц (х)», г). Направление г (х») Ь агу гп!п Г' (х», г) называют направлением ммм наибыстрейшего убывания функции Г в точке х».
С л е д с т в и е 1. Если г дифференцируема, то г (х») = = — 7г (х»). Это значит, что приближение х»+', лучшее чем х', можно вычислить по формуле х»+' = х»+ )!г (х»), », = ага ппп у" (х'+ + ) г (х»)). Сл ед с тв и е 2. Если х* = агд ппп !(Сх, х) + (г(, х)], то к хе — решение линейной системы алгебраических уравнений (С + +С") х+и=О. Лемма (23]. Если х = агд!(С+ С')х = с(], грй А (С+ С*)й, А, = Р— А (С+ С*), й»е' = й»+ А й», А»ь~ = Азы то )) х— — й»))()) А„))т ~'))й)). Поэтому г(» эффективно приближается к искомому х с увеличением й.
Приведем ряд условий оптимальности, справедливых н для граничных точек множества Х. 2. Необходимые и достаточные условия оптимальиоетв для задачи выпуклого програмиировавяя. Теорема Купа — Таккера Напомним необходимые понятия выпуклого анализа. Пусть х', х' ~ Х. Функцию ! называют выпуклой на выпуклом множестве Х, если тЛ с (О, 1] !'(хл) (Ч (х') + (1 — Л) ((х') называютстрого выпуклой, если чЛ р )О, Н! (хл) (Ч(х') + (!в — Л)1 (х') н называютсильно вьтуклой, если при некотором сс .в О Р( 2' 1((Р(х')+Р(х'))/2 — а]х' — -')), х». Ь Лх' + (1 — Л) х'. Аналогично, множество Х называют выпуклым, если ЧЛ Е (О, !] хх р Х, называют строго выпуклым, если при Л Е (О, 1) хк является внутренней точкой Х, и называют сильно выпуклым, если прн не- котором и ) О открытое множество (х))) х — хк ] ( и ] х'— — х')) ппп (Л, 1 — Л)) принадлежит внутренности множества Х, Лс(О, 1). Утверждение 2.
Если функция 1 выпукла и дважды днфферен- цируема, то следующие условия эквивалентны: (1) 1(х') — !(х')) (Ч1(х'), х' — х'); (2) (с7 ! (х+ Лй), й) — неубывающая функция Л; (3) (Чрх~(х)й, й)~О Чх, йЕВ". Утверждение 3. Если ! — дважды непрерывно дифференцируемая функция, то условие сильной выпуклости эквивалентно условию (Ч ! (х) й, й) -. а))й))з, в ~ О, х, й Е В"; сильно выпуклая достигает своего минимума на замкнутом множестве.
Естественно, выпуклая и даже строго выпуклая функция 1 может не достигать своего минимума на замкнутом Х. Утверждение 4. Строго выпуклая функция достигает своего минимума на выпуклом множестве Х лишь в единственной точке. Множество Хе всех решений выпукло и довольно просто опи- сывается с помощью конуса допустимых направлений. Множество К (х') называют конусом допустимых направлений для Х в точке х», если оно состоит из тех векторов Ь, для которых существует число е > О, удовлетворяющее условию х' + в)) с Х Утверждение 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
