XIV Аттетков и др. Методы оптимизации (1081420), страница 25
Текст из файла (страница 25)
5). Методы прямого поиска (см. 6) менее изучены, большинство из них носят эвристический характер и не имеют теоретического обоснования. В то же вромя, они достаточно просты в реализации, что предопределяет их широкое применение при решении прикладных задач оптимизации. В настоящее время не существует универсального метода, применимость которого была бы оправдана и эффективна во всех случаях. Выбор того или иного метода, его программная реализация должны быть согласованы с конкретными условиями, вытекающими из специфики решаемой задачи безусловной минимизации. В этой главе изложены некоторые общие свойства численных методов безусловной минимизации.
4.1. Релаксационнан последовательность Пусть требуется найти точку х* б Я", в которой ограниченная снизу целевая функция Т(х), определенная в К", достигает своего наименьшего значения. Будем считать, что эта точка существует, так что задачу оптимизации можно представить в виде 1(х) -+ппп, х Е Б'.". (4.1) Отметим, что такая точка может быть и не единственной. Общей чертой всех численных методов решения этой задачи является последовательный переход от точки х к точке х, а б И, начиная с некоторой напальной точки х Е К",.
причем на каждой итерации с номером а выполняется условие ~ь = ~(хь) < 1'(х~ ) = 1ь ь Й Е И. (4.2) Так как целевая функция ограничена снизу, то в силу признака Вейерштрасса ~1] невозрастающая последовательность 1Я сходится к некоторому пределу. Однако из этого в общем случае еще не следует, что итерационная последовательность 1хь) 165 4.1. 1'елаксанионнан последовательность Лемма 4.1. Если для элементов последовательности 1рй) выполнены условия Свй 1 — ОВй > Уййвй ~„1Рй 1> О, у~ >О, ЙЕТИ, (4.3) то справедлива оценка со~ <, тп Е 'г1.
Фо 1+'воо 2, й й=1 14.4) ~ После почленного деления первого неравенства в (4.3) на 1ой 11ой находим 1 Фй1 >Ъ Фй йвй-1 'Рй *Сьь: Карманов В.Г. точек х Е вйп., соответствующих значениям 1й, сходится, а если она и сходится, то ее пределом является точка х* Е Й" минимума функции 1" (т), удовлетворяющая (4.1). Последовательность 1т~), элементы ю~ Е К" которой удовлетворяют неравенству (4.2), называют релаксационной. Численные методы, применяемые для построения такой последовательности, относят к классу методов спуска.
Это название можно связать с тем, что, например, при минимизации функции 11х1,и2) двух переменных уменьшение ее значения при переходе от точки (т1 ол2 ) к точке (и~,т~) означает спуск с линии уровня 1(т1ое2) = уй 1 на линию уровня .1 1а1~ с2) Хй ( Уй — ! . При анализе сходимости релаксационной последовательности удобно рассматривать невозрастающую последовательность ~,ой), где свй = 1й — 1„> 0 (при сей = 0 принимаем х* = х ).
Для оценки сходимости этой последовательности используют следующие утверждения*. 167 4Л. Релаксанноннан последонательность Ь-~ — Ь Чз~агас17'1х' 'Р' В итоге оценка (4.4) принимает вид 'Ро ~Рт = ут Ро ~ Ь-~ — Ь +,,2 с. ~6га,~~( и — ~)Р ь=1 ш е 1Ч. (4.6) Сумма в правой части полученной оценки имеет нулевое значение, если последовательность (Я постоянна.
Предположим, что эта последовательность не является постоянной и для некоторого номера ш выполнено неравенство 7"„ч 1 — 7",— > О. Тогда при ш > ш У--У У-- -У- .О ~8гас1Дха ")~2 ~8гас17'(хк ')~2 и, отбрасывая в знаменателе правой части (4.6) единицу, полу- чаем оценку 2 'Рт = 1т ~л ~~ с= Ь-~ -Ь (8гас17"1хк ')(2 ш > ш. (4.7) Оценку (4.7) легко вычислить, и ее использование в процессе численного решения задачи минимизации не вызывает затруднений. Лемма 4.2.
Если для элементов последовательности (~рь~ выполнены условия ~рь л — сок > ть~рь и сов ~ > О, ть > О,. АХЕИ, (4.8) с11ашХо = О(хо) = и конечен, то ~х~ 1 — х*~ < о, и поэтому в условиях теоремы 4.1 с учетом (4.5) имеем 168 4 ЧИСЛКННЫН Мятсды ннЗуолсвной минимизАции то справедлива оценка ~Р» < 1РОехр( —,1 т~ь~. т с И. 1с= 1 (4.9) < Из неравенств в (4.8) следует, что ть„. Е (О, 1) и 'Рт < (1 тт)'Рт-1 <- ФО П(1 1В).
Отсюда, учитывая., что 1 — ть < ехр( — тс), приходим к (4.9). ~ 0 < рн 1 = К 1 — 1". < (8гасЦ(х"' '),х" ' — х*) < < ~Кгас1У(хй )~~~хи ' — х*~, (4,10) Теорема 4.2. Пусть функция 1'(х) выпукла и дифференцируема в К", множество ХО = (х Е К": 1(х) < 1(х")) ограничено, а последовательность (хя) является релаксационной. Если т = '"-' ' Й.И Ч(8гас1 ~(х"' 1) ~ ' (4.11) где о = с11а1вХО -- диаметр множества ХО, то справедлива оценка (4.9). < Используя (4.10) и учитывая, что (х" 1 — х*~ < Н, находим (Ь-1 — Ь) Ря-1 'Рь-1 — 'РЬ = 1ь — 1 — 1ь ~ ~~ 11.( я 1) ~ ~ Уь-1 — ЬМ-1 т~~8гас11(х" 1)~ Согласно лемме 4.2, получаем оценку (4.9).
~ Пусть минимизируемая целевая функция 1(х) является выпуклой и дифференцируемой на множестве К" . Тогда, согласно теореме 3.11 и неравенству Коши Буняковского, для любого Й Е И получаем 169 4Л. Релансацноннал последовательность При выполнении условий теоремы 4.2 оценка (4.9) имеет вид Дх™) — 1(х*) ( 1 ~ т = '-' '" В~И та = 7 ) ай ~1хь 1) р (4.13) где 7 ппрлллетпо сильной выпуклости функции у(х), справедливы оценки (4.9) и ~х™ — х*~ < — ~рпп т Е И. 7 (4.14) ~ В силу теоремы 3.18 при й Е И имеем ря = ~а — 1, < — ~8гас1)'(х )~, ~х — х*( < 2 * = — ~рь. 1 я я ь., я уа — 1„2 7 7 7 Последнее неравенство равносильно оценке (4.14), а из первого неравенства вытекает, что Л-1 — Ь ~рь — 1 Фа = Б — 1 Б ~~ ь р'УРН вЂ” . '= тЮа Согласно лемме 4.2., получаем оценку (4.9).
~ Заменяя в оценке (4.9) величины тя их выражениями по формулам (4.13), а также величины сов = ~а — 1'„приходим к следующей оценке: <ех дхо) — у~ ) (е р~ — 7~ ~ Йд~хь 1)р, ЕИ. (41о) Теорема 4.3. Для сильно выпуклой и дифференцируемой в льп функции ~(х) при 170 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ Используя (4.14) и (4.9), а затем заменяя величины ть по формулам (4.13), получаем оценку Эти две оценки позволяют в процессе численного решения задачи минимизации накапливать информацию о приближении значений ~ь к значению ?„, а в случае сильно выпуклой минимизируемой функции — и о приближении точки х к искомой ь точке х' минимума этой функции. Практически можно задать некоторое число е > О, связанное с выбранной точностью вычислений, и проводить итерации до тех пор, пока не будет нарушено неравенство Ь-с — Ь ~3е, кЕИ, (4.17) а затем либо повысить точность вычислений, либо перейти к другому методу спуска.
Поиск точки х' обычно прекращают при выполнении на й-й итерации одного или обоих неравенств: ~х — х ~ ( см (?(х ) — ?(х )~ ( ез, (4.18) где ес и ез заданные достаточно малые положительные числа, называемые параметрами точности поиска. В случае минимизации дифференцируемой функции необходимым условием того, что х' е К" точка ее минимума, является равенство Егас1Т (х*) = О. При этом условием прекращения поиска на й-й итерации может быть выполнение неравенства (Егас?Д(х~ ')~ ( ез, ез > О.
Если при проведении итерапий к зна сонию ?, = ?'(х') сходится последовательность (Я значений )ь = ?(х ) минимизируемой функции ?(х)., то говорят о слабой сходимости применяемого метода (или соответствующего алгоритма), а если сходится к точке х* и последовательность (х ), то о сильной сходимосгаи этого метода (или алгоритма). 171 4.2, Методы спуска 4.2. Методы спуска Пусть существует точка х* Е К", в которой целевая функция 7(х) достигает минимума.
Процедуру поиска этой точки в методах спуска обычно описывают (после выбора начальной ттточни х") рекуррентным соотношением (4.20) х =х +альп, ЙЕИ,. где нь Е К" — единичный вектор, определяющий направление спуска на к-й итерации, а Д ) 0 длина плаза спусна, т.е. расстояние в этом направлении, отделяющее точку х~ от новой точки хь. Методы спуска различаются способами выбора направления и шага спуска. Если на к-й итерации выбран вектор нт', то один из способов выбора значения Д базируется на требовании, чтобы выполнялось неравенство* т(х~ ~+Кьн~) <(1 — Ль)7(х~ л)+Льштп т(х~ '+рн~), (421) где Ль Е (О, Ц.
Отметим, что выбор значения Д в соответствии с условием (4.21) обеспечивает выполнение неравенства (4.2), так что последовательносттть (х")., построонная в соответствии т: (4.20), будет релаксиционной. При Ль = 1 неравенство в (4.21) переходит в равенство, а значение Д соответствует минимальному знатеникт функции 1(х) при изменении х вдоль луча, исходящего из точки х в направлении вектора и ', т.е. на множестве 1х е К": х = х" ' + ~~и", )3 е К„). В этом случае для нахождения Д необходимо решить задачу одномерной минимизации (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
