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

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

Файл №1121207 И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации) 62 страницаИ.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207) страница 622019-05-09СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Алгоритм 1' Н а ч а л о. 1. Выбрать начальное приближение хч р В". П. Выбрать константы 6, ) 0 и р ) О. П1. Положить й = О. Основной цикл. 1Ч. Положитьх=х". Ч. Положить 6 = 6,. Ч1 Найти множество индексов Оь(х) (шаг Ч1 алгоритма 1). ЧП. Найти вектор й (х) (шаг ЧП алгоритма 1). ЧП1. Если й (х) = О, то положить х*= х и прекратить вычие- ления; иначе перейти к шагу 1Х. 1Х. Вычислить следующее приближение х"+' = х+ рй(х). Х. Положить й = я + ! и перейти к шагу 1Ч. Теорема 1'. Пусть хь — решение задачи 1 и выполняются еле. дующие условия: (!) — для любого доспиипочно малого 6 ) 0 вспомо.

гат ель нал задача квадратичного программирования — найти агкш!п~(Ч1,(х), 6) -(- — '1й(~'~ при ограничениях (Ч1!(х), 6) -(- ~!(х)(0, )ЕОг(х), где аь(х) = Ц~~,(х)~вшах~,(х) — б, )~О), ~ИХ разрешима; (й) — функции ~1 — дважды непрерывно дифференцируе- мы и градиенты Ц~ (х"), 1 ~ аь (х*), где О,(")=(111,(*)=О, Ий), линейно независимы; ((и) — в точке х* выполняются необходимые условия минимума в форме Ч1ь (хФ) + ~ )~ь~7( (х~) = О /яя,ыи и Х1 ) О, 1 Е Иь (хь); (Юо) — выполняется достаточное условие ло- кального минимума, т. е. (й, "т(;„; "' й))О для всех й чь О и удовлетворяющих условию (Ь, Ч~~(х~)) = О, 1ЕИ,(х*), где ~Р(х, ь) = 1ь(х) + ~; Ч,(х); 1ЕХи о вектор У состоит из компонент Х;, 1 Е 21ь (х*). Тогда существуют такая окрестность У точки х* и константы б, ) О, а ) О, что бесконечная последовательность (хь)Г~, порожденная алгоритмом 1', сходится к точке хь с любого начального приближения х' Е У с геометрической скоростью, т.

е. существует такое число О ( о, < 1, юпо (~х" — хь)(()г(д,)", (3,<оь, для всех достаточно больших значений й. Теорема 1". Если выполнены все предположения теоремы 1' и, кроме того, число индексов в множестве Иь (х*) равно и (размерности пространства), то бесконечная последовательность (хь) ь=в, порожденная алгоритмом 1' при р = 1, сходится в некоторой окрестности точки х' с квадратичной скоростью, т, е.

~ хь+' — х*1((1, ~хь — хь(ь, р, < оь. а. Отааяячеиия типа равеяьчв 3 а Д а Ч а 2. НайтИ ата ПЦН 1ь (Х) ДЛЯ ЗаДаННОй ФУНКЦИИ счх 1ь: В" -+ В' и множества Х, задаваемого соотношением Х = [х~),(х) =О, 1=1, ..., т, хЕЛ"). Предположение 2. Функции /ь / = О, 1, ..., т — дважды не- прерывно дифференцируемы. Алгоритм 2 Н а ч а л о. 1. Выбрать начальное приближение х' и числа )!с, ! = 1, ..., т. о П.

Положить й = О. О с н о в н о й ц и к л. Ш. Если выполняются равенства Ч/.(")+ Ей'Р/(")=О' ! 1 /!(х")=О, о=1, ..., т, то положить х'= х» и прекратить вычисления; иначе перейти к шагу 1Ч. П/. Вычислить производную д!р(х', )»»)/дх функции Лагран- жа по формуле »! д<р (х", У)/дх = д/о (х»)/дх + ~; )»; д/! (х')/дх. »=! »/. Вычислить матрицу вторых производных д»!р(х', У)/дх» функции Лагранжа по формуле до<р (х», У)/дх» = д»/о (х»)/дх» + ~ )»!~д»/! (х")/дх'. ! ! 'Ч1. Найти вектор/!» и числа 6»,1 = 1, ..., т, удовлетворяющие рйвенствам "т~(' "1 й»+~6!» Ы.»)+ "~ х) =О, ! ! (ч/! (х"), /»») + /! (х») = О, ! = 1, ..., т.

'»/П. Вычислить следующее приближение х»+' =х»+/!». »/П1. Вычислить )!г+' А!+6!, ! 1, ..., т. 1Х. Положить й = й + 1 и перейти к шагу Ш. Теорема 2. Пусть выполнено предположение 2, а также следующие дополнительные предположения: (!) — вторые производные Функций //, / = О, 1, ..., т, удовлетворяют условию Липшица; (»1) — в точке х*, которая является решением задачи 2, градиенты 1/ /! (х~), / = 1, ..., т — линейно независимы, так что существуют множители Лагранжа Ц, !' = 1, ..., т, удовлетворяющие системе 77, (~*) + ~ Л,'Р/, (х*) = О; !-! /! (х») = О, 1 = 1, ..., т; зз! ٠— выполняются условия локального минимума, т.

е. д»р 1х', Л'1 У дх» У))0, если У~О; Щ,(х*), у)=0, 1=1, ..., т, здесь ~р(х, Л) = ~, (х) + 2', ЛД (х) . / ! Тогда, если начальное приближение х' и числа Ли 1 = 1, ..., т, е достаточно близки к х* и Л~, 1 = 1, ..., т, соответственно, то по- следовательность )х"; Л»п 1 = 1, ..., т)» о, порожденная алго- ритмом 2, сходится к (х', Л~, 1 = 1, ..., т) с квадратичной скоро- стью. 8. Ограиичеиии еиешаииого типа 3 а д а ч а 3. Найти агд ппп го (х) для заданной функции хех 1»: Л"- В' и множества Х =- )х)(~(х)(0, 1~8, хЕУ), где У вЂ” заданное выпуклое замкнутое множество; ~~ . Ь"-~ В' (1 ~ О) — заданные непрерывные функции. ЛРедположение 3.

(1) — фУнкции гн 1 Е Г () (О) — непРеРыв- но дифференцируемы, Алгоритм 3 Все шаги, за исключением 1 и Ч11, такие, как и в алгоритме 1. Шаг 1 в алгоритме 1 заменить на Г. Г. Выбрать начальное приближение х' ~ Г. Шаг Ч11 в алгоритме 1 заменить на Ч1Г. Ч1Г.

Найти решение Ь = Ь (х) задачи квадратичного програм- мирования: найти агй ппп '(Ч)е(х), Ь) + — ))Ь))т) прн ограничениях (Ч)~(х), Ь)+1»(х)~(0, )Ело(х), х+ЬЕК, Теорема 3. Если выполнены предположения 3 и существуют та- кие константы 6 ) 0 и а ~ О, что: (1И) — множество Х„= ) х ) Де (х) + а шах )~ (х) (1» (хе) + а шах ~~ (хе), х с )' ), гйу ИУ ограничено; (4о) — градиенты функций 1н 1 Е О () (0), в Х„удов- лепморяют условию Липшица, т. е. ))Чг»(х) — Ч~~(х))(Ч(х — х)), т(оо, х, хеХ„; (о) — задача квадратичного программирования найти агу пип ~(Ч)".е (х), Ь) + -и- ) Ь)~) 1 л 832 при ограничениях (Ч)(х), й)+1)(х)<0, 1Е~г(х), х+йб)', 1з.зз) разрешима относительно й при любых х Е Х„и существуют такие множители Лагранжа а) (х), 1 с Иь (х), что а)(х)(а; )е.угы) (ь() — среди функцийгп 1 Е О, имеется функция Гн равная тождественно нулю (1) (х) — 0), то любая предельная точка бесконечной последовательности (х"]е" е, порожденной алгоритмом 8, принадлежит множеству Х и в этой точке выполняются необходимые УсловиЯ минимдма фУнкЦии )е на множесп)ве Х и, кРоме то.

го, справедливо шах 1) (хе) — )- 0 при й -е- оо, Иу хе~)', й=О, 1, .... (Множители Лагранжа для задачи (6.62) — (5.63) — это такие неотрицательные числа, которые удовлетворяют неравенству (7)'е(х), й(х))+][й(х)1 + ~' к)(х)Щ)(х), й(х))+)')(х)]< /яуеы) ~((Ч]'е(х), й)+ (й(х), й)+ ~л к)(х) [(%7) (х), й)+))(х)] ) саввы) для всех й, удовлетворяющих условию х + й Е у и равенствам й,(х) [(%7,(х), й(х))+~,(х)] =О, )ЕОь(х)). 4. Метод лввеариаавии, правтичееви реалиауевыа ва ЭВМ 3 а д а ч а 4.

Найти агд ппп 1е (х) для заданной функции еех 1ь: В"-ь В' и множества Х = (х ] ~) (х) (~ О, 1 = 1, ..., т, х с В" ] П [х [) ) (х) = О, )=т+1, ..., т+1, хЕВ ], определенного с помощью заданных непрерывно дифференцируемых функций ]). В" -ь В'. Данный алгоритм не требует априорного знания констант а и 6, обеспечивающих сходимость алгоритма. Эти константы вычисляются в процессе счета. Для реализации данного алгоритма требуется эффективная стандартная подпрограмма решения зздачи квадратичного программирования. .Алгоритм 4 Н а ч а л о.

1. Выбрать произвольное начальное приближение хе ЕВ ° 333 11. Выбрать константы 6,) О, 0 < е ( 1, сс, (а, — достаточно большое число). 1И. Положить й = О. Основной цикл, 1У. Положить 6=6„х=х~, а= = аь. Ч. Вычислить ф(х) = шах (О, у,(х), ..., у„(х), (у»»(х)(, ..., (у +с(х)(). Ч1. Найти множество индексов да (х) = (у(у (х) ~ф(х) — 6, у = 1, ..., т); Оь(х) = (у(уу(х)~ф(х) — 6, у =т+1, ..., т+1).

ЧП. Если задача квадратичного программирования найти агдппп((Чу,(х), И) + — ((Ус((') при ограничениях (ЧУ*у(х), Ус)+У'у(х)(О, УЕВ (х); (Чу,(х),ус)+у,(х) =О, уЕОь(х), совместна, то найти ее решение Ус = й', множители Лагранжа Лу, у Е Ч7 (х) (( Ч1(х) и перейти к шагу 1Х; иначе перейти к шагу ЧП1. Ч111. Положить х"+' = х, аа» с = а, 6~»1 = 6У2 и перейти к шагу ХЧ1. 1Х. Положить з = О. Х. Вычислить р„= (1У,)'. Х1.

Если выполняется неравенство У~(х+ р~Ус~) + а$(х+ рьУсь)(У,(х) + аф(х) — ер„16" ((', то перейти к шагу ХП; иначе положить з = з + 1 н перейти к шагу Х. Х11. Вычислить следующее приближение ха+' = х+ раус". ХП1. Положить ба+1 = 6. Х1Ч. Если выполняется неравенство сс) ~ Лу+ ~", (Лу(, !ЕГд"гл уефа то положить аь»» = а и перейти к шагу ХЧ1; иначе перейти к шагу ХЧ.

ХЧ. Вычислить "~-ч х ~+ х Р~~) ~уята (м у~,т'~~(м ХЧ1. Положить Ус = й + 1 н перейти к шагу 1Ч. Для алгоритма 4 справедливы теоремы сходимостн, аналогичные теоремам пункта 1. Отметим, что начиная с некоторого значения й, величпны аа и 6„ не будут меняться. 334 а. Аналог метода линеариаапвв в детерминированных задачах минимваацив почтв двфферевцируемых функций 3 а д а ч а 5. Найти агй ш!иге (х) для заданной функции «ел ге: В" -~ В' и заданного множества Х с= В". Предположения 5.

(1) — функпия !е — почти дифференцируема; (В) — Х вЂ” выпуклое, ограниченное и замкнутое множество, образованное неравенствами )~(х) < 0. где ~~: В" — ~ Вт — выпуклые функции. Данные методы используют общую идею метода линеаризации и основаны на понятии почти градиента минимизируемой функции. Алгорин».н д Н ачало. 1.

Выбратьи начальное приближение хе ~ Х, начальное значение г' Е В", начальное значение щаговых множителей р„ае и величину смещения Ь„удовлетворяющие условиям теоремы 5. 11. Положить й = О. Основной цикл. 111. Вычислитьхь(=1, ...,а — независимые случайные величины, равномерно распределенные на отрезках х» — — х'+ — ~ 1 1 ... и. [ «»» е»" с з)> 1Ч. Вычислить вектор 0(х", й) — ~~~„[~е (хы ..., х~ + —, ..., х„) 1 ! Г-»» о» -»| где е', ! = 1, ..., а — 1-й орт. Ч. Вычислить вектор у» Е Х, удовлетворяющий условию (г", у») пп'п (г», х).

«ех Ч1.. Вычислить вектор х»+' х» — р, (х» — р»). ЧП. Вычислить вектор г»+' г'+ >х» (О (х", й) — г"). Ч!П. Найти значения щаговых множителей р»+ь а»+1 и значение смещения б»+ь удовлетворяющие условиям теоремы 5. 1Х. Положить'й ° й + 1 и перейти к шагу 111. Теорелси 6. Пусть выполнены предположения 6 и, кроме того, имеют место условия 0<р»(1 и б«)0 при 6 = 0„1, ...; ОО ~о р«= оо, р«/а«б«-» 0 при /с~со; »-о Ю Е (р»/6)'<"., Е и'<ж »-о «=о )6» — 6«+с(/р — О, б«-еО при й- оо, Тогда с вероятностью 1 предельные точки последовательности (х")ь о, порожденной алгоритмом 6, принадлежат множеству Х" решений задачи 6 и последовательность (/о (х"))«=о почти наверное сходится.

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

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

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