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

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

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

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

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

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

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

$3.12), определить, принадлежит ли начало координат многограннику 1,.а (хе), который является выпуклой оболочкой, натянутой на множество векторов н.я Если начало кооРдинат пРинадлежит многогРанникУ Ь,а (хе), то положить х,„= »" и прекратить вычисления; иначе перейти к шагу ЧП. ЧП. Используя алгоритм 1" (см. 5 3.12), вычислить точку г~а— ближайшую к началу координат точку многогранника Ьсв (»е). Положить бсв ( гса 1 ЧП1. Вычислить вектор й,в (хе) — направление (е, н)-наискорейшего спуска функции шах ф, (х) в точке хе по формуле ~6У пса (» ) — (1Яеа) гса.

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

е~ (Точка х,а р Х называется (е, р)-квазистационарной точкой функции гпах ф, (х) на множестве Х, если О Е Еед (хсд)). ~ея 4. Модпфппеппл второго метода последовательных прпблпжеапа Алгоритм 3 для нахождения (е, р)-квазистационарных точек используется в приводимом ниже алгоритме для отыскания стационарных точек функции гпах ф, (х) на множестве Х. ест Алгоритм 4 Н а ч а л о. 1. Выбрать начальное приближение хе Р Х. П.

Выбрать константы е, > О, р, > О, а, > О. П1. Положить в = О. О с н о в н о й ц и к л. 1Ч. Найти множества индексов чье (х') = (!! п1ах фс (х*) = фс (х') 1 Е о ); 'Е.т Яе(х') = Ц)/,(х*) = О, )ЕИ,). Ч. Вычислить множество векторов Н (х') = Н (х') () Нс(х'), где множества Не (х') = ( Чф, (х'), ! р 'в1 е (х')); Но(х*) = (%7!(х'), )ЕЯ»(х')). Ч1. Используя алгоритм 1' (см. 5 3.12), определить, принадлежит ли начало координат многограннику Еее (х'), который является выпуклой оболочкой, натянутой на множество векторов Йее (х'). Если начало координат принадлежит многограннику 443 ьое (х'), то положить хе= х' и прекратить вычисления; иначе перейти к шагу ЧП. Ч11. Используя алгоритм 3, в котором положить 3 и = 1ь„е = е„хо = х, найти первый индекс й, при котором выполняется неравенство 6„"„( а, и положить х'+' = х".

ЧП1. Положить в,», = е,/2, р,» ~ —— 14,12, а,»1 = а,/2. 1Х. Положить в = е+ 1 и перейти к шагу 1Ч. Теорема 4. Если выполнены все условия теоремы 2, то любая предельная точка бесконечной последовательности (х')„о, порожденной алгоритмом 4, являетея стационарной точкой функции шах и, (х) на множестве Х. гаУ Библиографические у«о«авил. При написание параграфе пспольеоввлпсь рабаты 1254, 127, 428, 480, 481, 5291. 6.2.

Обобшенный беснараметрнческий метод внешней точки решения дискретных минимаксных задач 3 ада ч а О. Найти агбгпш гпах); (х), где «ех 021ь 1 х~(х!йг(х)(0, )Е21, 11,(х) =О, 1ЕЕ, хЕВ"); йг . 'В" -«- В', 1 Е Р, Ь1 . В" -«11', 1Е ~; Р и Ь вЂ” конечные множества индексов. Предположения О. (1) — функции ~, (х), 1 = 1, ...„т, дг (х), 1 Е ЕГ«, Ь, (х), 1ŠŠ— непрерывно дифференцируемые в Н"; (11)— еуществует решение х' минимаксной задачи О. Обозначим 1е(х) шах 11(х); У(х) - (11й,(х) )О, ! ЕП). еенео1 1. Ооковвоа алгоритм На и-й итерации алгоритма вычисляется точка х" безусловного минимума некоторой вспомогательной функции и оценка снизу а, для значения Ге (х') такие, что 1 (х') 1.( ') аь -«1о (хе) пРи й -«оо; аь+~ ~аь, й = О, 1, ...; Цо(х*) «а„й = О, 1, ....

Для начала работы алгоритма необходима нижняя оценка ао значения 1о (х'). 444 Алгоритм 1 Н а чало. 1. Выбрать константу а»(~ь(х*) (т. е. нижнюю оценку а, оптимального значения 1» (х*) задачи О). И. Задать произвольные веса шп 1 ~ О и оь 1Е Е. 111. Для фиксированного числа а определить функцию ф(х, а) = ~„"[~,(х) — а]'+ ~ иь(у~(х))»+ ~ о,(Ь,(х))', !Яя (и !ау(о се» где Я(х) = [1[[,(х))а, 1=1, ..., т). 1Ч. Положить й = О. О с н о в н о й ц н к л. Ч. Найти точку х», удовлетворяющую условию ф(х», а») пип ф(х, а„), *ел" т.

е, решить задачу безусловной минимизации дифференцируемой по х функции ф (х, а»). Ч1. Вычислить а»чл = а» + [ф (х», а„)1т] ~'. (6.1) Ч11. Положить я = й + 1 н перейти к шагу Ч. Творе а 1. Пусть выполняются предположения О и пусть: (111)— 1» (х (и)) — непрерывная функция аргумента и в точке и = О, где х (и) является решением следующей задачи: найти агнппп шах ~,(х) т ~кима при ограничениях д~(х) < ир Ь, (х) = и,, 1Е 1., здесь ир 1' Е Р, иь 1 Е 1.

— компоненты вектоРа и. Тогда алгоритм 1 порождает последовательности (х»]ь.~, [а»)Г ~ такие, что а, ~, (х') при й 1 (х»)-».1 (хч) при й-» оо; ф(х», а»)-ч-0 при й-».оо. 2. Уекорьвимй варваит алгоритма В ускоренном варианте алгоритма на некоторых итерациях вычисление величины а»+~ проводится не по (6.1), а по формуле а„', = а' + ф(х", а„)1 ~ Ц,(х») — а'), <ЯЯ(х») при этом справедливо неравенство а»+, ~ а»+,, что обеспечивает ускорение сходимости (а»)» ~ к 1» (хч) по крайней мере прл а» близких к 1» (х'). 44~5 Алгоритм 2 Н а ч а л о.

1 — Ш. Шаги 1 — П1 такие, как н в алгоритме 1. 1Ч. Выбрать верхнюю оценку аа оптимального значения 1а (х') задачи О. Ч. Выбрать константу е~ ) О, характеризующую точность вычнслення га (х*), константу е, характеризующую близость значеннй функции ат (х, а) к нулю.

Ч1. Положить т, = а,. ЧП. Положить й = 1. Основ но й цн кл. Ч1П. Найти точку х', удовлетворяющую условию <р(ха, т,) = пп[п <р(х, т„). «аи" !Х. Вычислить значения 1, н 1„соответственно гг = та + [ф (ха, таУ т) 0; 1« = та+ (Р(ха, та)l ~; ((е(ха) — т,). ее рс олч Х. Если 1,( а„то положить та»1 = 1« н перейти к шагу Х1; иначе положйть та»~ = гт н перейти к шагу Х1. Х1. Положить т, = та»1 — та; аа = 1,; з = <р (ха, т„). ХП.

Положить й = й + 1 н перейти к шагу ХП1. ХП1. Найти точку ха, удовлетворяющую условию <р(ха, та) = пи!в <р(х, т„). «яи Х[Ч. Если а, — аа( егнлн т,( еь то прекратить вычисления (в этом случае находят прнблнженное значение для [а(х*), которое можно вычислить, например, по правилу /а (х«) ы (а,+ аа)/2); иначе перейти к шагу ХЧ. ХЧ. Если «Р (ха, та) ) О, то пеРейти к шагУ 1Х; если е( еа, то прекратить вычисления (в этом случае также находят прнблнженное значение для 1а (х«)); иначе положить а„= тан е = О, т„= = а, н перейти к шагу ХП1.

Замечание 2. Алгоритм 2 основан на том, что неравенство т ~ ~ 1а (х«) справедлива тогда н только тогда, когда [п1 ~р (х, т) = 0 «ран Библиографические ркоаинин. Параграф основан на рабате [4601. 6.3. Метод второго порядка решении задач дискретного минимакса 3 а д а ч а 1.

Найти агд пип шах ерс (х) для заданных функцнй «ех чая грс: 11" — ~ Ит, 1 Е Я н заданного множества Х = (х[1;(х)(0, [сй, хе«1"), где Я, й — конечные множества индексов. 440 Предположение /. (1) — функции <р, (х), 1 с '/1 и /, (х), / с Р— дважды непрерывно дифференцируемые в В". В приводимом методе используется квадратичная аппроксимация ~р; (х), /; (х) соответственно, функций ~р, (х), // (х) в точке х = = х", что приводит к сверхлинейной скорости сходимости с показателем, равным '/,. На каждой итерации алгоритма требуется решать (точно) некоторую вспомогательную минимаксную задачу. Алгоригем 1 Н а ч а л о.

1. Выбрать начальное приближение хг, принадлежащее достаточно малой окрестности множества Х. П. Выбрать произвольные константы 0 ( е ( 1, 6 ) О, р ) С (обычно е = гlм 6 Е 110 ~, 10 '1, Р Е 1!0-', 10 '1). П1. Выбрать достаточно большую константу а ) О. 1Ч. Положить lг = О. О с н о в н о й ц и к л. Ч. Вычислитыр, (х").

/; (х"), ЧЧ, (ха), Ч~~ (х"), Ч„„~р, (х~), Ч~,/, (х~) при всех 1Е К, / Е г/. Ч1. Вычислить множества индексов Х, - (1) ~р, (х"),в шах ч4 (х') — 6, 1~ Ж); ~зя О„= Ц)),(х")~шах/,(х") — р, /ЕО). %~ ЧП. Определить функции ~р~ (х),/у (х), (с Ж, / ~ О, соответственно <р,'(х) = <р,(х") + (Чй (х"), х — х') + — Ч,„ф,(х')(х — х')', /,".(Х) /',(х") + (Ч/,(х'), х — х') + ~ Ч',д/у(х')(х — х')'. Ч1П. Найти решение х" следующей вспомогательной задачи выпуклого программирования: найти агиш1п шах ~р",(х), «ах~, ~ея~ где множество Х, = (х(/,'(х)(0, /~О„, хЕН"). 1Х. Положить й" = х" — хь.

Если 1/г" ! = О, то прекратить вычисления (в атом случае х" — решение задачи 1); иначе перейти к шагу Х. Х. Положить р = 1. Х!. Определить функции ф(х) = гпах~р,(х); д(х) = шах (О, шах//(х)). 'ея КЯ ХП. Если выполняется неравенство »[г (х» + рй ) + ад (х' + р(г») ( $ (х») + си) (х») + + ер [шах гр," (х») — »]г (х») — ад (х»)], 8УГ, ' то положитьр, = р и перейти к шагу Х1Ч; иначе перейти к шагу Х П1.

Х1П. Положить р = р/2 и перейти к шагу ХП. Х!Ч. Вычислить следующее приближение х»+' = х» + р»й», положить й = й + 1 и перейти к шагу Н. Теорема 1. Пусть выполняется предположение 1 и, кроме того: (и) — для любых х, у Р Л", 1 Р Х, 1 Е сг, справедливо у,)х)]»((Ч„'„~р,(у)х, х)(у,)[х]', уг][хЦ'~(Ч'4(у)х, х)(у»йхИ', у,>у,)О; 1111) — для задачи 1 и вспомогательных задач (б.2] вьаюлняется условие Слейтера; (Ь) — множители Лагранжа ]Зг (х»), 1 Е О», вспомогательньгх задач (б.2), соотвегпствуюгцие ограничениям 1; (х) ( О, равномерно ограничены: рг (х») ( оц»ух» Е У,„~ (х] гпах ~р, (х) + ге.т» геЯ + а гпах (О, шах 1; (х) ) ( шах ег, (х') + !а.т гнус +ашах(О, шах1 (х»)), хСВ").

!6Я Тогда для последовательности (х»)» о, порожденной алгорит- мом 1, справедливы утверждения: 1) !пп х» = х"; » са 2) если матрица Ч'„гр, (х), Ч~„1, (х) при 1ЕЖ*Ь(г]гр,(х*) =шах~рг(х'), 1ЕЯ], гаХ 1'Еог'1»(1[Гг(х ) =шах1 (х»), 1ЕО] lср непрерывны в окрестности точки х", то начиная с некоторой ите- рации р» 1; ]пи ! 6» ] I ! Ь»-г ]] = О; »-~а 3) если, кроме пюго, матрицы Ч„гй (х), Ч„)г (х) при 1Е Я~, 1~ О*, удовлетворяют условию Липшица, то при я-» ао )]й» ([~ ( ч ][1»» г []Н где чг) Π— постоянная величина. Замечание 1.

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