И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 9
Текст из файла (страница 9)
и (в редких случаях) производных более высоких порядков. Эта информация позволяет выбирать правдоподобные гипотезы о возможной конфигурации функции 1 (в окрестности точки х") и затем, на основе принятой гипотезы, определить такое значение х"+', для которого ожидается выполнение неравенства 7' (х"+') (1 (х") — С„ (0.24) с возможно большим значением числа С„ ) О. Выбор различных гипотез приводит к различным методам оптимизации. Если функция 1 непрерывно дифференцируема, то, как известно, ~(х) = ~(х")+ (Ч1(х"), х — х")+ о(~х — х" /!).
(0.26) Отсюда видим, что направление наибыстрейшего убывания функции 7 совпадает с вектором — ЧГ (х") и поэтому можем при малых Л„ вычислять х"+' по формуле: х"+' = х" — Л„Ц (х"). (0.26) Метод (0.26) называют методом градиентного спуска, или градиентным методом. Различные модификации градиентных методов основаны на том, что функция Р, (х) ам) (х") + (Ч/ (х"), х — х") (а значит и непре. рывно дифференцируемая функция Д убывает не только в направ. ленин — Чг (х"), но и по всем направлениям г", удовлетворяющим неравенству (г", Ч1 (хс))(б(0 (О. 27) (действительно, г", (х" + г") = 7" (хс) -(- (Ч7 (х ) ха 1 га хе) = р~ (х") + (П (х"), г") ( г, (х")).
Поэтому х"+' можем вычислять также и по формуле х"+' = х" + Л„г'. (0.28) Методы (0.27), (0.28) относятся к методам возможных направлений. 1. О способах выбора шатовых мпожвтелей в задачах беаусловпой оптпмвааппп Если значение.Л„выбирать из условия 7 (хч + Л„г") (1 (х"), (0.29) то сходимость (0.2!) н даже сходимость (0.23) может отсутствовать. Например, для минимизируемой функции 7 (х) — = (х+ 1)', после- 2 хпм 33 довательность хл= 1/и удовлетворяет условию (0.29) и тем не менее не сходится к решению хл= — 1. Чтобы обеспечить сходимость (0.23), можно в качестве Лл выбирать решение Лл следующей вспомогательной задачи одномерной оптимизации: Лл = ага т!п Г (хл + Лгл).
(о.зо! Хьо Однако данный способ применяется лишь а редких случаях (например, в случае квадратичной функции!), так как обычно задача (0.30) чрезмерно трудоемкая. Поэтому, либо вместо задачи (0.30) решают задачу минимизации некоторой более простой функции Р (Л), аппроксимирующей функцию 1 (х" + Лгл) (например, в качестве Р (Л) часто выбирают параболу а«Л' + Ь«Л + с, проходяшую чеРез точки 1(хл), 1 (хл+ Лл, гл) и ! (х" + 2'Лл, гл), если 1(хл + Л„,гл) (! (х"), то р = 1, иначе р = — 1), либо вместо условий (0.29) проверяют некоторые более сильные условия, например, условия вида (28): ~(х" -1- Ллгл) (1(хл) — БЛ (о.з!) В последнем случае используется следующий алгоритм 1: для произвольно выбранных чисел з) О, з, ) 2, Л,= 1 полагаем Л„= = 2 «з,Л« и где Йл — минимальное натуральное число, при котором выполняется неравенство (0.31).
Лемма 1. Если Лл выбирать таким образом, чтобы обеспечивалось выполнение неравенства Сл ~ <р (ал) (0.32) аля некоторой неубываюшей положительной при ал) 0 функции ~р (где Сл — число из неРавенства (0.24)), то пРи !п(1 (х) ) — оо в слУ- чае а„) Ц (хл) ) будет обеспечена сходимость (0.23), в случае а„! х" — х* ) — сходимость (0.22), а в случае ал = 1 (х")— (й! ~ (х) — будет обеспечена сходимость (0.21). « Действительно, если предположить, что 1!тп а„~ О, то из пел «« равенств (0.24), (0.32) получаем неравенство 1пп )".(х'мл) = Нш (1(х"+') — ~(хл) + 1(хл) — 1(х"-') + л-и л-«а л + " ° + ~ (х') — ~ (х') + 1(х')) (1пп ~„'( — ~р (а,)) + ) (х') = — оо, л«««! ! которое противоречит неравенству !п!1 (х) ) — оо.
Сл едст в и е 1. Если для функции ! сушествует такая иеубываюшая функция ~р (а) ) 0 при а ) О, что ) т! (х) )! ~ ~р Д (х)— — !п!1(х)), то сходимость (0.23) влечет сходимссть (0.21), если « м ~7 (х) ( ~ ~р ( ) х — хл 9, то сходимость (0.23) влечет сходимость (0.22). Теорема 1. Если Ч! (х) удовлетворяет на множестве (х ! 7 (х) «,:, = 7 (х')) условию Липшица с константой 1„то для алгоритма 1 с (0.27) суи(ествует функция !р, удовлетворяюи(ая условию (0.32) при а„= ! Ч(' (х") !. Такой функцией является !р (а) = ш(п ~в Л„!/2, а 2((.+г) ~ ' Таким образом, в условиях теоремы 1 при !п1 7" (х) ) — оо алгок ритм 1 обеспечивает сходимость (0.23).
Методы вычисления Л„, в которых используются значения 7' (х"+!), 7' (х"), ..., называют адаптивными. Поэтому все упомянутые выше методы являются адаптивными методами. В неадаптивных методах всю последовательность Л„Л„... задают до начала вычисления последовательности х', х', ... и она не зависит от будущих значений 7 (х'), 1 (х'), ..., При этом, естественно, процесс вычислений хт, х', ... упрощается.
Однако здесь не учитываются особенности конкретной минимизируемой функции 7 и в итоге такой способ выбора Л„может оказаться менее эффективным, чем в адаптивных алгоритмах. Один класс неадаптивных способов выбора Л„, обеспечивающих сходимость (0.23) для метода (0.26), дает теорема 2 и ее следствие. Теорема 2. Если градиент Ч( (х) удовлетворяет условию Липшица с константой Е и !п1((х) — оо, то метод (0.28) удовк летворяет неравенству « л ш(п ! Ч~ (х!) !)( Д (х!) — !пЦ (х) — 2 'Е. ~ Л,'.)/б ~; Лр (о.зз) /=1,л к Неравенство (0.33) можно получить из неравенств ! (х"+') ~ ( Р (х") — Л„б)) Ч('(х") !!+ 2-' ЕЛ, справедливых для всех и, С л е д с т в и е 1. Если выбранная последовательность Л„ Лл, ... удовлетворяет условиям Ф Л )О, ~Л =, ~„Л((~,Л =О, (0.34) /=1 ! 1 ! ! то в предположениях теоремы 2 1ип ~! Ч(' (х") !! = О. «со Действительно, при условиях (0.34) из неравенства !п17 (х) ) к ) — оо и неравенства (0.33) получаем Иш ~ Ч ( (х") ~ = О.
«« ~ Для выпуклой функции 7 выбор Л„упрощается (183, 404): Теоремами. Если 7" — выпуклая функция с минимальным значением ! (х~), то при выполнении условий ),„) О, Л„-э О, 2„),„= оо, з" -! Ч) (х") (о.зз) для метода (0.28) выполняется равенство Ип! !' (х") = )' (х*). о -н Действительно, из очевидного равенства х"-!.! — х' = х" — хо+ + Л„г" получаем неравенство )! х"+' — хе !!' ( ( х' — х* )(!— 2' зз — ~ ((Ч/ (х'), х' — х*) — (Ч/ (х') — г1, х' — х') — Л,), которое ! 1 при условиях (0.35) влечет равенство 1нп (Ч/ (х'), х' — х*) = О. Поэтому с учетом неравенства / (х') — / (х*) ( (Ч/ (х!), х' — хе) (справедливого для выпуклой функции /) получаем 11ш / (х') = / (х*).
Очевидно условиеЛ„-о 0 практически невозможно реализовать на ЭВМ с конечной разрядной сеткой. Поэтому на практике часто используют методы как с постоянным шаговым множителем Лл лл = Л, так и некоторые промежуточные м~'кду адаптивными и не- адаптивными [29, 321. Теорема 4. Для метода (0.28) при Л„=— Л в условиях теоремы 2 выполняется неравенство ш!п !) %7 (х') 1( (/ (х') — !и! / (х))/6Лп + Ш26. !о.зв> 1=!,л /(ействительно, неравенство (0.36) следует из неравенства (0.33) при Лл лл Л. С л еде т в и е 1. За /!/, /Ч ( Д (х') — 1п1/(х))/Лв, итераций по л методу (0.28) при Л„= Л найдем точку х' (! ( /Ч), удовлетворяющую неравенству (~ Ч/ (х!) ~ ( Л (Л + /./2)/6.
Поэтому постоянное значение Л можно сохранять до момента естабилизации» значения гп!и ) Ч/(х') !!(или значения ппп /(х!)). |=л — дл ! л — »л Затем Л уменьшаем и опять сохраняем его постоянным до следующего момента стабилизации. 2. О методах второго порядка Чем сильнее отличается функция / (при удалении х от хл) от линейной функции Р,, тем меньше эффективность градиентного метода (0.2б), так как в таких случаях неравенству (0.24) обычно можно удовлетворить лишь при слишком малых (близких к нулю) значениях Сл.
Это вынуждает усложнять вычислительный процесс, привлекая более точные и более сложные аппроксимации для функции /. Например, если функция / достаточно хорошо аппроксимируется в окрестности хл функцией Р„ Р, (х) = / (хл) + (Ч/ (х"), х — хл) + — (х — хл)" Ч~,/ (хл) (х — хл), го в качестве х"+! целесообразно выбрать точку х", доставляющую наименьшее значение функции Р. Так как в случае невырожденного положительного гессиана Ч„„/ (хл) искомая точка хл должна являться решением системы ЧР,(хл)=Ч/(хл) +ЧД(х")(хл — х ) = О, !о зт) то получаем х"+' = х" = — (~7'„,7 (х")] ' Х7 7 (х ). (о.зв) Такой метод называют методом Ньютона — Канторовича. Если в окрестности решения хч гессиан ч~„( (х) невырожден и начальное приближение х' выбрано достаточно близко к хч, то метод (0.38) имеет квадратичную скорость сходимости в отличие от геометрической скорости сходимости градиентных методов.
Однако из-за необходимости решать систему (0.37), трудоемкость вычисления х"+' по методу (0.38) значительно превышает трудоемкость вычисления х"+' по методу (0.26). другая трудность реализации метода (0.38) связана с необходимостью выбирать начальное приближение х' достаточно близкое к х*, чтобы точка х"+' не оказалась слишком далеко от х", где вследствие нарушения близости функции 7 и ее локальной квадратичной аппроксимации р, можетоказаться ( (х"+')) ~7(х") вместо требуемого 7'(х"+')(7'(х"). Чтобы обеспечить сходимость к решению при любом выборе х', предлагается вычислять х"+' по формуле Хп+! = Х" + Х„(Хл — Хч) (0.30) ().„можно вычислять, например, с помощью алгоритма 1).
Чтобы обойти трудности, связанные с решением системы (0.37), предложено ряд модификаций метода (0.38). В одних случаях предлагается вычислять гессиан не во всех точках, а лишь в некоторых точках х"~ и оставлять его без изменений на промежуточных итерациях при и; ( и ( пс(.п В других случаях предлагается гессиан вообще не вычислять и рассчитывать х"+' по формулам х"+' = х" — Х„В„Ц(х"), (0.40) где (В„) — некоторая последовательность матриц, удовлетворяющая условию В„- (7~„( (х").
Найдены довольно аффективные формулы для пересчета ) „, В„, при которых метод (0.40) сохраняет хорошее свойство метода (0.38) (т. е. имеет квадратичную скорость сходнмости) и в то же время является менее трудоемким. Такие методы названы кеазиньюгпоноескими, илн методами с переменной метрикой (ввиду того, что операторы В„можно интерпретировать как преобразование метрики в пространстве градиентов). Различные алгоритмы реализации квазиньютоновских методов разработаны также и для тех практически важных задач оптимизации, когда в силу отсутствия аналитического выражения для Функции ( (или по другим причинам) градиенты 7( (х") не вычисляются и в расчетных формулах используются лишь вычисленные в предыдущих точках значения ) (х"), 7 (х" — '), ....
В основе таких методов лежат те или иные способы аппроксимации неизвестных градиентов и гессианов с помощью конечных разностей. Эффективные способы построения матриц В„предложены в методах оптимизации с растяжением пространства и в близком к ним методе эллипсоидов. В этих методах на и-й итерации осуществляют «растяжение» пространства в некотором направлении г", совпадающим с Ч! (х") илн с разностью двух последовательных градиентов, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
