Главная » Просмотр файлов » XIV Аттетков и др. Методы оптимизации

XIV Аттетков и др. Методы оптимизации (1081420), страница 27

Файл №1081420 XIV Аттетков и др. Методы оптимизации (Зарубин В.С., Крищенко А.П. - Комплекс учебников из 21 выпуска) 27 страницаXIV Аттетков и др. Методы оптимизации (1081420) страница 272018-01-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 27)

~ ягас1 1 (х ) ~ -+ 0 при 7п — + ос. Замечание 4.1. Из теоремы 4.6 не следует сходимость метода градиентного спуска, в котором используется (4.40),.к какой-либо точке. Например, функция 1" (х) = 1Д1+ ~х~з) удовлетворяет условиям теоремы, но при любом выборе начальной точки х Е Ко имеем ~х ~ — ~ оо при й — ~ оо.

Приведенный пример показывает, что функция вообще может не достигать наименьшего значения. Однако если к условиям теоремы 4.6 добавить требование ограниченности множества Хо = (х Е К"; 1(х) ( 1(хо)1, то, согласно теореме 7.1 в случае Й = К", функция 1(х) будет достигать наименьшего значения. Можно показать, что при этом последовательность 1хк1 будет сходиться к какой-либо стационарной точке функции. Некоторые особенности рассматриваемого варианта метода градиентного спуска можно выявить, если допустить нарушение отдельных условий теоремы 4.6. Так, если функция 1'(х) не является ограниченной снизу, .то нельзя утверждать, что ~8тас11(х~)~ — ~ 0 при га — ~ оо. Действительно, для линейной функции ~(х) = (с, х) при с ~ 0 имеем ! ягаб11х) ( = )с! > О.

Если выбрать х > 2/Ь, то в процессе итераций минимизируемая функция может не убывать. В самом деле, для ограниченной снизу функции )'1х) = Ьхз/2., х Е К, выполнено условие (4.41), а (4.40) принимает вид х" = хк ' — ог1''(хк ') = (1 — осЬ)хк '., но при выборе тс > 2/А получим т.е. последовательность (х ) не является релаксационной. Наконец, рассмотрим последствия нарушения условия (4.41). Функция 1(х) = ~х~ш~, где д б (О, 1), имеет точку минимума 182 4. чйсд~Б11ы~ 1~1'с1дб1 Б~~гс'.1ООБг~Й атияйии~л14ии х* = О, дифференцируема в К", но ее градиент не удовлетворя- ет условию (4.41), поскольку ~рас1((х) — цгас1~(0)) 1+6 р ~~ О. Для этой функции Ф вЂ” 6 х~ 1 д и~ь = — дгадДх~ ') = — (1+б)~х~ '~~ „, = —,, х" Поэтому при достаточно малых значениях ~х~ ~ ~, соответству- ющих приближению к точке х* минимума, из (4.40) имеем ь~ ! й 1 ~'(1+4) ь ~ (1 н(1+4) ~ ь 1~ ~ й 1~ х — ~х — ~,зх — ~ — ~,з х >х и 1(х ) > у(х ), т.е.

последовательность ((х !) не сходится к нулю. Можно показать, что предел этой последовательности > 1+4~1 — 6 равен (и ) . Не удовлетворяет условию (4.41) и диффе- 2,) ренцируемая на К" функция 1(х) = ~х~з+', е > О, имеющая ту же точку х* = 0 минимума, .так как = (2+ е) ~х(- — ~ оо при ~х~ -+ оо. (х — 0( В этом случаешь = — (2+с))х~ '!'хв ~ и в соответствии с (4.40) находим ~хь~ = )х" ~ — и(2+с)~хь ~~ х~ ~( = (1 — х(2+с)~х~ ~! ( )х~ ~/ Отсюда видно, что последовательность (х~1 сходится лишь при условии ~1 — и(2+с)~х~ ~~'~ ( 1, те. если начальная точка хв удовлетворяет неравенству х(2+ с) ~х" ~' ( 2. Один из недостатков метода градиентного спуска с фиксированным значением х в (4.40) состоит в том, что в окрестности стационарной точки х дифференцируемой функции 1 (х) 4.3.

Метод градиентного спуска 183 шаг спуска на некоторой й-й итерации может оказаться больше расстояния х — щ, т.е. при этом алгоритм .,проскакивает' искомую точку. Более того, этот шаг может быть настолько большим., что 1"(в~) > 1(а" 1) и последовательность ~жа) перестанет быть релаксационной. Избежать такой ситуации позволяет выполнение условия (4.41), существенно ограничивающее класс рассматриваемых функций, а также выбор тки б (О, 2/Л) (см.

теорему 4.6), который порождает второй недостаток этого метода: по мере приближения к стационарной точке шаг спуска тс~8тас1~(ж )~ уменьшается, что сильно замедляет сходимость последовательности 1,в ) к этой точке. Из оценки (4.42) следует, что можно избежать „прогкакивания" искомой стационарной точки, если выбрать и = 1/Л из условия максимума выражения н(1 — тгЦ2).

Однако в прикладных задачах проверить выполнение условия (4.41) и найти константу 1' обычно не удается. Поэтому вместо (4.40) используют рекуррентное соотношение ж = ж + тсьтп = жь ' — тсь дгас1~(ж~ ), Й Е 14, (4.43) и подбирают значение иа > О на каждой 1с-й итерации из условия, которое в меньшей степени, чем (4.41), ограничивает класс минимизируемых функций. В случае ограниченной снизу функции 1'(ж) для обеспечения сходимости последовательности ~~ игаса г(вк) ~) к нулю достаточно, чтобы на каждой к-й итерации для некоторого числа ые > О выполнялись неравенства Дх ) — ~(ж ) > ме(и> ~ = ссз~дгас1~(х ')~, Й Е И (4.44) В самом деле, суммируя неравенства (4.44) для 1с = 1, ти, полу- чаем ~(ж ) — ~(х ) > ще~ ~8гас1~(х" ')~ .

ь=1 Поэтому знакоположительный ряд ~„~ ягас1 1(хь ) ~~ сходится, а=1 а в силу необходимого признака сходимости его общий член стремится к нулю, т.е. ~8гас11(;вк)~ — ~ О при к — > со. 184 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАНИИ Следовательно, условие (4.44) в сочетании с (4.43) можно использовать для выбора значения кь. Существуют разные способы такого выбора*. Ограничимся рассмотрением двух из них. Если функция ~(х) непрерывно дифференцируема в 2Р, то скалярное произведение (Егат1~(х), то~) = — (Егэл1 7(х), дгае1~(х~ 1)) ее градиента на антиградиент шн = — ягас1 ~(х ' ') является непрерывной функцией.

В точке хя ' оно равно — ~ше~г < О, причем равенство нулю возможно лишь в случае, когда х ь-1 стационарная точка. Ясно,что функция )'(х) убывает в направлении антиградиента до тех пор, пока это произведение остается отрицатольным. Поэтому один из способов выбора значения же на й-й итерации состоит в том, чтобы в (4.43) х~ была ближайшей к х"-1 точкой, в которой производная функции Дх) по направлению антиградиента обращается в нуль, т.е.

(даст~(хя), ш~) =О, к Е К (4 4б) Указанный способ называют исчерпывающим спуском (движение в направлении антиградиента щ происходит до тех пор, пока не будут исчерпаны „подряд идущие" отрицательные значения производной функции ~(х) по направлению этого вектора). "Смл Волин Э., а также: Лшенииный Б.Н., Данилин КЭ.М. Замечание 4.2.

Отметим, что точка х", найденная при помощи исчерпывэлощего спуска, может не совпадать с соответствующей точкой, найденной по мегаоду наискорейшего спуска. Показано (см. 4.4), что в случае квадратичной функиин эти точки совпадают на каждой итерации. Если функция Дх) строго выпукла в К", то в силу теоремы 3.7 функция 'еь(ж) = ~(х~ 1+ кто~) также строго выпукла. Поэтому, если стационарная точка функции фь(х) существует, то, согласно 185 4.3. Метод градиентного спуска теоремам 3.14 и 3.15, эта точка единственна и в ней функция достигает наименьшего значения.

Из (4.45) следует, что на (й+1)-й итерации новое направление исчерпывающего спуска, определяемое антиградиентом ш е = — 8гас11(ак), ортогонально предыдущему направлению. Так как 8гЫ 1(жй) коллинеарен вектору нормали в точке жй к поверхности (линии) уровня 1(а) = ~(ж ), то луч, исходящий из точки ж по направлению вектора ю = — 8гЫ 1(а ), вдоль которого на Й-й итерации происходит исчерпывающий спуск, лежит в плоскости, касательной к этой поверхности уровня в точке хй, т.е. луч касается поверхности уровня функции, проходящей через точку а~. Отметим,что если при переходе через эту точку производная по направлению йо не изменяет знак, то луч пересекает поверхность (линию) уровня ~(х) = = 1'(жй). Эти ситуации в плоском случае показаны на рис.

4.1 и 4.2. Рис. 4.2 Рис. 4гт Замечание 4.3. Покажем, что для функции, удовлетворяющей условиям теоремы 4.6, существует такое число ыо, что при исчерпывающем спуске на каждой итерации будут выполняться неравенства (4.44). Для этого используем формулу Тейлора с остаточным членом в форме Лагранжа зт( й) зт( й — 1) ( „а1У( й — 1 +Д( й й — ~)) й й — 1) 186 4.

ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ где с9 Е (О, 1). Отсюда, учитывая (4.43), получаем 9" (хь ') — 9" (х~) = — нь(бгас1Д1хь ~+с9(х~ — х~ ~)),. со~). Точка х~ 1+ д(х~ — хь 1) на прямой исчерпывающего спуска является промежуточной между х~ ~ и х~. Производная по направлению св в этой точке отрицательна, и поэтому (рас19(х +с9(х — х )), св ) = с = !се~/ (8гас1~(х~ '+д(хя — х~ ')), ) < О. Следовательно, выбор ьсо > — нь(бгас1~(х~ '+д(х~ — х~ '))...1 > О (сссс)2 р обеспечивает выполнение неравенства (4.44).

Характеристики

Тип файла
DJVU-файл
Размер
2,13 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Зарубин В.С., Крищенко А.П
Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6549
Авторов
на СтудИзбе
300
Средний доход
с одного платного файла
Обучение Подробнее