Главная » Все файлы » Просмотр файлов из архивов » Файлы формата DJVU » И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации

И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации, страница 76

DJVU-файл И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации, страница 76 Алгоритмы оптимизации основанные на методе проб и ошибок (2638): Книга - 5 семестрИ.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации: Алгоритмы оптимизации основанные на методе проб и о2019-05-09СтудИзба

Описание файла

DJVU-файл из архива "И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации", который расположен в категории "". Всё это находится в предмете "алгоритмы оптимизации основанные на методе проб и ошибок" из 5 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр DJVU-файла онлайн

Распознанный текст из DJVU-файла, 76 - страница

а. Метод еопращенна неаавоп в вадачах етонаетачеепого нрограммарованна 3 ада ч а 3. Найти агя пни )е (х), где «ко Х'дзХ П (х(1 (х)(О, 1= 1, ..., т)1 ~;(х)1~ЕР;(х, Ф), /=О, 1, ..., и; Х с: В" — заданное множество; р;: В" х 11 - В' — заданные функции. Для функций )О 1'= О, 1, ..., т, и множества Х выполняются предположения 2. Алгоритм 8 Н а ч а л о. 1.

Выбрать произвольную начальную точку (хо, ие)ЕВ» Х В~ 11. Задать шаговый множитель р„нормирующий множитель у, и величину смешения Ь„удовлетворяющие условиям теоремы 3. 1П. Положить )е = О. Ос нов н ой ц и к л. 1Ч. Вычислить вектор и $д =Х Ф(хи+ аде~, ид, вдл) — Ф (х", ид, аде) г' ад т -где е»", ч = 0„1, ..., и — серия независимых по й наблюдений «состояния природы 4оо (в частности, можно взять»о»о= ы»л = ... — 4О»,о — Ы»). функция Ф (х, щ о») определяется по правилу а Ф(х, и, о) = с'о(х, о»)+ ~„и~р~(х, о»), !=1 здесь и = (и„..., и ); е-', 1 = 1, ..., и — 1-й орт, Условное математическое ожидание вектора $» равно ЕЯх», и') = 7„<р(х", и»)+ о»1»», где функция »о (х, и) »» ЕФ (х, и, о»); о" — некоторый вектор, для которого ) о») < сопз1, т.

е. вектор в» является стохастическим квазиградиентом функции у (х, и) в точке (х', и'). . Ч. Вычислить вектор х»+' = пх (х» — р»у»ь»). Ч1. Вычислить вектор и»-л по(и»+ р у»Р(х» юко)) где Р = (Р„..., Р ); множество У определено в пункте 2. Ч11. Вычислить шаговый множитель р»4 ы нормирующий множитель у»+1 и величину смещения по координатным осям Л»+ь удовлетворяющие условиям теоремы 3. ЧП1. Положить я = я + 1 и перейти к шагу 1Ч. Теорема 3. Пусть выполнены предположения 2 и, кроме того, функции )о 1 = О, 1, ..., т, имеют ограниченные в области Х вторые производные и 1,— строго выпуклая функция. Пусть: (1) — т)„— случайная величина, измеримая относительно о-подалгебры, индуцированной величинами (х', и'), ..., (х", и»), такая, что Е ( 1 В» '1« + 1 Р (х», о»» о) )3/(хо, ио), (х» и»)) " Чо < Р (Х) < 00 при 1/х /)+1и'!/<Х<оо, в=О, 1, ..., й (здесь р(К) и Х— ограниченные константы); (»1) — нормирующий»тожитель т» для некоторых чисел у'> у' удовлетворяет условию О < у' < у» (В» + т»1 х' ( ) < у" < оо, где т»= 1 при 1сР !! ) О, т»= О при 1 о» '1 = О; (1И) — шаговый множитель р» и величина смещения по координшпным осям Ь» детерминированные и такие, апо Ф Ю р»~вО, ~; р»= оо, ~'„(р»)Ь»)+рД<оо.

~о »=о 413 Тогда с вероятностью 1 одна из предельных точек последовательности (х»)Гс, порожденной алгоритмом 3, принадлежит Хе, т. е. поспи наверное 11ш (ш)п 1» (х»)) = ~, (хе), хе ~ Хе. еию св»<в 4. Гвбрвдвый стевеспсоесввй метод 3 ада ч а 4. Найти агд пип 1» для заданных множеств Х с «ехал ~ В" и А = (х(1(х) (О). Предположения 4. (о) — функция(о ( ) — непрерывна и выпук- ла вниз; (й) — множества Х и А — выпуклые и замкнутые; (йо)— А() ХФ8 Приводимый гибридный стохастический метод поиска экстре- мума функции 1» ( ) сочетает в себе идеи стохастического релакса- ционного метода для решения систем неравенств и стохастического ивазиградиентного метода для решения задач нелинейного про- .граммирования.

Алгоритм 4 Н а ч а л о. 1. Выбрать начальную точку хо ~ 11", для которой а)хо 11» < со. П. Задать последовательности щаговых множителей (б»)Г=»1 (р»)Г о. П1. Задать последовательности нормирующих множителей (()»)Г=»1 (7»)Г о 1Ч. Положить й = О. О с н о в н о й ц и к л. Ч. Вычислить случайный вектор $», условное математическое ожидание которого К (с»1хо, ..., х») = со»Ч1» (х») + 6», (5.10!) где ໠— неотрицательная случайная величина и о» вЂ” случайный вектор, измеримые относительно о-подалгебры Й„ индуцированной семейством случайных величин (хо, ..., х»); Чго (х») — вектор обобщенного градиента функции 1» в точке х". Ч!.

Вычислить случайный вектор Ь», условное математическое ожидание которого Е(г»1хо, ..., х») =),»д(х») + У, (0.102) где 1» — неотрицательная случайная величина и о(» — случайный вектор, измеримые относительно о-подалгебры Й»; я (х») — вектор, для которого полупространство, отвечающее неравенству (а(х), г — «)+1(х)((О> при х = х» содержит множество А, если х»~ А. 414 Ч11.

Найти вектор пх (х» — 6»р»Г (х") Ь» — р»уД»), 1(х») ) 0; ~ (' — р.ус'), 1(х») < О. Ч111. Положить й = й + 1 и перейти к шагу Ч. Теорема 4. Пусть имеют место предположения 4 и пусть з)» слу- чайная величина, измеримая относительно о-подалгебры Й», та- кая, ипо для любого числа со < оо найдется число с, для которого Е(~~»~з+ ~~»)з/»л, ..., х») <»1'- <с„ как только ~ х'1< со, в = О, 1, ..., А; для некоторых чисел, у, у нормирующие множители р» и у» удовлетворяют условиям Р~(1(х')(~ (й))х»~~+1)+ Ч~) = 11 у<у»(та(й)1х'1+»)»)<у, где т» (й) = 1, если!/ й» '1 ) О, т, (й) = О, если ( й» 1 = 0; т, (й) = 1, если ~ Ь" 1) О, т, (й) = О, если ~ Ь» ~ = 0; величины р„б», а», Л„и векторы Ь», й» такие, ело р»~0, 0<6»<2Л» — е», е» вО, а,) О, Л»; »0; Ю ~", Е(р,))Ь»)+ р'+ р»6„+ 6») й»))) с- оо.

Тогда случайная последовательность (х»)» о, порожденная алго- ритмом 4, является случайной квазифейеровской относительно мно- жества Х*. Если же, кроме того, с вероятностью 1 ~, '6,в» = оо; ~„р»а» = оо, »-о о=о то она сходшпся к некоторому злементу х*Е Х' почти наверное. Замечание 4. Если, например, ((х) = шах~,(х) й~им(х), где функции ), (х) — выпуклые вниз и непрерывно дифференци- руемые; 1(х) — индекс, на котором достигается гпах ~, (х) при за- данном х, то всктоР Е(х) = Ч)~ (х) ~; кю УдовлетвоРЯет неРа- венству (5.103).

Замечание 4'. Отметим, что на шаге Ч11 алгоритма 4 использует- ся стохастический релаксационный метод х"+' = пх (х» — 6»р»~ (х») ь») для решения системы неравенств ~;(х)<0, 1=1, ..., т; хсХ, где ~(х) = гпах ~, (х). 1<1<а Библиогрп4»з»еское упования. При написании параграфа использовались работы 1!49, 1531.

41$ 5.29. Комбинированный метод стохастнческих градиентов и штрафных функций 3 а д а ч а 1. Найти агя шах !» (х) для заданной функции гях Д»: В" » В' и заданного множества Х = (х)~,(х) 1»О, 1= 1, ..., т, хЕ!г). Предположения 1. (1) — функции 11 (х), 1 = О, 1, ..., т — непрерывны вместе со своими производными; (й) — функции П (х), 1 = О, 1, ..., т — вогнуты; (111) — У вЂ” выпуклый компакт из В".

В приводимом здесь методе определяются функции д,(х, а) =!»(х) — а ), р»)ппп(О, 1,(х)) )' 1 (здесь т) 1 — константа; а — коэффициенты штрафа, стремящиеся к бесконечности; р,, 1 = 1, ..., т — выбранные вероятности) и для отыскания их максимума применяется метод стохастического градиента. Алгорип»м 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение х'Е 1' П. Задать числа р„ 1 = 1, ..., т (р, ) О, ! = 1, ..., т; ~ р,= 1 = !), которые, соответственно, характеризуют требуемую относительную точность выполнения ограничений-неравенств в задаче 1 (обычно р, = !/т, 1= 1, ..., т). П1.

Выбрать параметр т) 1. 1Ч. Положить й = 1. Ос н о в но й ц и к л. Ч. Найти независимую реализацию 1» случайной величины 1, которая принимает значения из множества 9 = (1, ..., т), соответственно, с вероятностями р„..., р . Ч1. Найти значения шагового множителя р и коэффициента штрафа а», удовлетворяющие условиям теоремы 1.

ЧП. Вычислить стохастический градиент 6» функции у, (х, а») в точке х» й» = Ч), (х») + а»т ) ш)п (О, П (х')) )' ' Ч~,, (х"). ЧП1. Вычислить следующее приближение х"+' = пг (х" + рД»), 1Х. Положить й = й + 1 и перейти к шагу Ч. Теорема 1. Если выполняются предположения 1, множество Х— непусто и числовые последовательности (р»)» ь (а»)» ~ удовлетво- 416 ряют условици р >О, 1ппр„= О, р»+!(р», 2„' р» »-ко »-! кк а >О, 1ппа»= оо, а»+!,'~а», ~ (р»а„)а(со, » о »=! то для любого начального приближения х' последовательность (х»)» и порождаемая алгоритмом 1, с вероятностью 1 сходится к Ага шах ге (х) — множеству решений задачи 1.

ксХ Замечание 1. Алгоритм 1 в (3721 рекомендуется применять для решения задач математического программирования с большим числом ограничений (в особенности для тех задач, ограничения которых могут формироваться по мере надобности в ЭВМ) и для решения задач с блочной структурой. Библиографические указания.

При написании параграфа использовалась работа 1372!. 5.30. Методы усреднения направлений спуска к. Петерввнвровавваа задача 3 а д а ч а 1. Найти агд ш!п)е (х) для заданной функции «ах 7а ! Л"-э-11! и множества Х, заданного соотношением Х=Х, ПХю где Х,= (х~ 1! (х) (О, 1'= 1, ..., т, ХЕВ"); Ха — выпуклое, замкнутое, ограниченное множество.

Предположения 1. (1) — функции 71, 1 = О, 1, ..., т — выпуклы; (И) — множество Х, имеет иепустое пересечение о множеством внут. ренних точек множества Х,. Ниже приводятся два алгоритма усреднения направлений спус- ка, первый из которых требует вычисления субградиентов функ- ций Г„ / = 1, ..., т, а второй — лишь вычисления значений функ- Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение хе Е 1?". П. Выбрать произвольное натуральное число 1. П1.

Положить й = О. Ос но в н о й ц и к л. 1Ч. Вычислить шаговый множитель р», удовлетворяюший условиям теоремы 1. Ч. Если выполняется неравенство шах 7! (х») ( О, !н!<а то положить ч» = О и перейти к шагу ЧП, иначе перейти к шагу Ч!, 14 з.зл! 417 Ч1.

Вычислить индекс 1~ (1 ~ т), удовлетворяющий условию, 1,(х») = шах ~~(х»), ! <уел положить»» =1 и перейти к шагу НП. ЧП. Вычислить субградиент Ц»„(х») функции г» в точке х", ЧП1. Если й ~ 1, то вычислить вектор ь'= Е 71,,( ') н перейти к шагу 1Х; иначе вычислить вектор й" но формуле й» = ~„»1» (х») » о и перейти к шагу 1Х. 1Х. Вычислить следующее приближение х»+' = нх, (х» — р»й»), где пх, (х) — оператор проектирования на множество Х, точки хс В". Х. Положить й = й + 1 н перейти к шагу 1Ч. Теорема 1.

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