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

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

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

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

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

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

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

С-1 1Ч. Если 1Ь(х~, еь)()еы то перейти к шагу Ч; иначе положить зь+1=з„1р, х" х/, Ь=Ь+1 и перейти к шагу П1. Ч. Используя алгоритм 3' (см. $ 5.3), вычислить такое число Лп что Ф+Л~Ь(х~, еь)ЕХ вЂ” Л~(1 — а)/!Ь(х!, еь)(«(~ь(хУ+Л~Ь(х', е„))+ + еьр' (х~ + Л;Ь (х1, е„)) — 1р (х1) — зьр' (х') ~ ( — Л,«х'1Ь(х/, е )1«. Ч1. Положить х~+' = х~+ Лг Ь (х', е„), положить 1 = 1+ 1 и перейти к шагу 1П. Теорема 2. Пусть выполнены предположения 1 и, кроме того: («) — функции гь 1 = 1, ..., т — непрерывно дифференцируемы; (И) — для всех х Е В" векторы 71, (х), ! Е 1.

(х), линейно независимы, еде 1. (х) = (1~ 7, (х) ~ О, 1 Р 1, т); (111) точка хл Р Х«и число е ) О выбраны так, что множеппво (х ~ 1«(х) ( 1« (хь) + ер' (хь)) компактно. Тогда предельные точка последовательности (хл)ь-ь. порожденной алгоритмом 2, допустимы и удовлетворяют необходимым условиям оптимальности задачи 1. Замечания 2. Достоинством методов внутренних штрафных функций (по сравнению с методами внешних штрафных функций) является то, что они порождают последовательности только допустимых точек, и, следовательно, могут быть использованы в реальном масштабе времени, имеют обычно производные достаточно высокого порядка и допускают управление вычислптельным процессом во «внутренностиэ множества Х.

Перечислим теперь их некоторые недостатки. Методы внутренних функций можно использовать лишь для ограниченного класса множеств Х (для множеств Х, содержащих внутренние точки). Процесс должен начинаться только из внутренней точки множества Х. Если множество Х имеет вид Х = (х3~~(х)(О, 1'=1, ..., т), то все члены штрафных функций типа (5.33) и (5.34) всегда дают ненулевой вклад в величину градиента штрафной функции. Это значительно увеличивает объем вычислений при отыскании направле1о 291 ния спуска (градиента внутренней штрафной функции).

В этом смысле методы внешних штрафных функций более предпочтитМьны. 3. Алгоритмы ииутреввеа точка и иримевевием О .фувквик 3 а д а ч а 3. Найти агй ппп го (х) для заданной функции кбх Ге: 11"->. Нг и заданного множества Х=(х)~,(х))0, (=1, ..., т, хЕВ"). Предположение 3. Функции 1!, 1 = О, 1, ..., т, непрерывны, а множество Хо!~(х!~,(х))0, 1 1, ..., т! — непустое. Главную роль в данном алгоритме играет характеристическое свойство функции, называемой (4-функцией и определенной следующим образом.

Определения. Пусть г = (г„г„..., г ) обозначает и + 1-мерный положительный вектор. Функция ~ (а) называется Я-функцией если: а) Я (х) непрерывна по г ) 0; б) !пп Я (г') = а ) Я (г), х ) 0 (до! > пускается а = оо), причем нижний предел беретея для такой бесконечной последовательности векторов (х), что г~ ) 0 для всех ! и )пп (г~) =* г, причем г~ = 0 для некоторого !.

В качестве примера Я-функции можно привести функцию Ю(/„(х') — ге(х), ~г(х)... °, Г' (х)) + ~ <„> . Алгоритмы внутренней точки с применением Я-функций составляют особый класа алгоритмов внутренней точки и обладают следующими свойствами: 1) не требуется выбирать строго убывающую последовательность (и,)~ о неотрицательных параметров, используемых в качестве весовых коэффициентов в ялучае обычной внутренней функции штрафа; 2) процеса минимизации на й-й итерации зависит только от значения нелевой функции в начальной точке х" ', т. е.

в точке безусловного минимума на (Й вЂ” 1)-й итерации; 3) членам последовательности внутренних допустимых точек соответствуют значения целевой функции ге (хе)> 1е (х'). " ге (х') образующие, начиная с исходной точки, строго убывающую последовательность. При обычных предположениях эта последовательность локально сходится. Алгоритпм 3 Н а ч а л о. 1.

Найти хе Е Х'. 292 П. Положить й = 1. О с н о в н о й ц и к л. Ш. Определить множество Х»= (х[[е(х)(7»(х» — '), х~Х'). 117. Положить [T(х)=Д( — ~»(х)+~е(х~'), ~,(х), ..., ~„(х)), где Я ( ) — Я-функция. Ч. Найти х» — какой-нибудь локальный минимум функции Я» (х) на множестве Х».

Ч[. Положить й = й + 1 и перейти к шагу П1. Теорема Ю. Пусть выполнены предположения д и: (») множество Х' локальных миниму»юв задачи д — непустое компактное изолированное множество; (»») Хе () Х' ~ 8. Тогда (»') — при Ха» Ф я существует точка х", являющаяся безусловным локальным минимумом 6)ункции (г» на Х»о, и любая предельная точка равномерно ограниченной последовательности (х»)а о есть локальный минимум функции 7";, (Л') — при Х» = 8 »-1 для некоторого конечного значения й точка х — локальный минимум функции )е.

Замечания 3. Алгоритмы с 9-функцией сохраняют для задач выпуклого программирования все преимущества алгоритмов внутренних штрафных функций, например такие, как глобальная схо. димость и возможность получения двойственных допустимых точек, дающих в пределе при я -ь оо решения двойственной выпуклой задачи. В (2601 было показано, что минимизирующей последовательности для Я-функций соответствует минимизирующая последовательность для метода внутренних штрафных функций, отвечающая некоторой специальной последовательности значений козффициентов штрафа.

Библиографические укавп«пя. При написании параграфа использовались работы [285, 536, 373, 464, 522, 5281. В работе [5261 предлагается метод сопряженных внутренних штрафных функций, позволяющий преодолеть трудности, возникающие вблизи границы допустимой области в обычных методах внутренних штрафных функций. б.б. Комбинированные методы штрафных функций 3 а д а ч а 1.

Найти агй ппп 7» (х) для заданной функции «ех 1»: 11" -ь »1» и заданного множества Х. Предположения 1. (») — функция 7» непрерывно дифференцируема; (»а) множество Х имеет вид Х = Х' [) Х", где Х' замкнуто, а Х" замкнуто и замыкание его внутренности Х ' совпадает с Х"; (з»») существует точка х ~ Х такая, что множество Х = (х [ 1» (х) ~( (~е(х)) компактно; (йи) — по крайней мере для одной точки хЯ ~ Х, являющейся оптимальным решением задачи 1, найдется такой открытый шар У, что х ~ У и пересечение внутренности множества Х" с множеством У' = У П Х' непусто. Комбинированные методы штрафных функций представляют собой простую комбинацию методов внешних и внутренних штрафных функций.

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

Построить функцию р» (х), принадлежащую последовательности внутренних штрафных функций для множества Х' (опреде. ление последовательности внутренних штрафных функций и спасо. бы их построения приведены в й 5А). И. Найти х» — какой-нибудь локальный минимум задачи оптимизации без ограничений: найти ага гп!п (1о (х) + Р, (х) + Р» (х)).

зех" о Ч. Положить й = й + 1 и перейти к шагу П. Творе»»а 1. Прстьвыполненыпредположения1 и суи[еспшует та",о каяточка х" Е Х ', что множество (х ) 1» (х) ~ ~1» (х ) + Ро (х ) + Ро (х )) компактно. Тогда каждая предельная точка последовательноапи (х»)»,.о, порожденной алгоритмом 1, является оптимальным Решением задачи 1. Библиографические указания. Параграф написан на основании работы [286[. В работе [5301 предлагается комбинация метода порождаюших столбцов и метода внешних штрафных функций, в работе [4311 — комбинировапкый метод множителей и штрафных функций.

5.6. Стокастнческий метод штрафов 3 ада ч а 1. Найти агдш)пЕР,(х, а), где «а.ь. 'л'=Х () (х)ЕР/(х, а)(0, 1 1, ..., т). Предположения 1. (1) — значения // (х) «»ЕР/ (х, в), / О, 1, ... ..., т, не вычисляются (или их практйческое вычисление слишком трудоемко), а значения Р/ (х, а), 1 = О, 1, ..., т и градиенты этих функций вычисляются с требуемой точностью; (и) — почти прн каж- дом значении состояния природы в функции Р1 (х, а),1 = О, 1, ... ..., т, непрерывно дифференцируемы по х; (и() — Х вЂ” выпуклое замкнутое ограниченное множество. Решение задачи 1 сводится к решению следующей задачи.

3 а д а ч а Г. Минимизировать по х функцию р(х, с) = 1,(х)+ ~ с/ф/(х))1/(х) 1 при ограничениях х ~ Х, где с = с (р) = (с, (р), ..., с,„0))); с/(р) = а, р)0, = О,р<О, 1=1,...,т, (6.34) здесь а — достаточно большое число. При достаточно большом конечном значении а решение задачи 1' будет решением задачи 1. Алгоритлг 1 Н а ч а л о. 1. Выбрать: произвольные начальные приближения х» ~ В" и гг Е В"; начальные значения шатовых множителей р, (0) и р, (0), удовлетворяющие условиям теоремы 1; выбрать «достаточ- но большое» число а ) О. 11.

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