Главная » Просмотр файлов » Ф.П. Васильев - Методы оптимизации (2002)

Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 95

Файл №1158201 Ф.П. Васильев - Методы оптимизации (2002) (Ф.П. Васильев - Методы оптимизации (2002)) 95 страницаФ.П. Васильев - Методы оптимизации (2002) (1158201) страница 952019-09-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Кубы П,, = (х Е Е": !х — х„, ~ < 6/2) с центрамн х., Е П„покрывают весь йараллелепипед П. Это означает, что для любой точки х е П найдется куб П,, содержащий эту точку. Отсюда и из (2) имеем: /(х)>/(х,, ) — 7!х — х, ~ >Є— Š— =Р„' — е 'т'хеП. Переходя здесь к нижней грани по х е 13, приходим к оценке (3). Метод простого перебора предполагает, что в каждой точке сетки П„ вычислены значения функции /(х), которые в определенном порядке перебираются с целью определения величины Г>,.

Однако, как и в одномерном случае, нетрудно указать более эффективные способы определения величины У„', которые, вообще говоря, не предполагают вычисления значений функций /(х) во всех точках сетки П„ и перебора всех точек этой сетки. Опишсм один из таких методов последовательного перебора. На первом шаге выбирается произвольная точка о, Е П„, вычисляется значение /(е,) н полагается Г> = /(о,), Допустим, что в точках еп ию ..., о„ сетки П„ уже вычислены значения функции /(о,),..., /(»ь) и найдена величина Г = пцп /(о,.) =ш!пЯ ,; /(»„)), 6 > 2. Через ез обозначим ту из точек >ч>чь е„ ..., е„., в которой Р„' = /(ез ). Далее, возьмем любую из точек »„з, е П„ к торая в предыдущих шагах не исключалась из рассмотрения и в которой еще не вычислялось значение функции /(х).

Вычислим значение /(ее~,) о )и величину Уь„„, = ш(п(Гь; /(»„+>)) = ш!и /(е,.). Имеются две возможности: либо У; „, =/(»е+,) < Р„', либо Р,, = Г, < /(хь~,). В первом случае, когда Р „, (Г„полагаем ег =е,ь, и из дальнейшего перебора исключаем точку о, н вместе с нею все точки х,, Е П„, для которых ~ < Ре Рь.» (4) Заметим, что некоторые из этих точек могли оказаться исключенными из перебора уже на предыдущих шагах. Для нас важно лишь то, что среди исключенных точек заведомо нет таких, в которых значение функции /(х) было бы меньше, чем Рь~,.

В самом деле, /(х, ) = Г„> Гьь Р ДлЯ остальных исключенных точек х,,, не зная значения /(х,, ), можем сказать, что /(х,, ) — Р„„, =/(х, > ) — /(о, )+ее — Рь, > — 5~х„, — ез >!+à — Гь > )О в силу (2) и (4). Рассйотрим вторую возможность; Г... = Г, < /(ез ). Тогда полагаем ез = т>, и из дальнейшего перебора исключаем точку хе „, вместе с точками х,, Е П„, для которых (5) Нетрудно убедиться, что и в этом случае в исключенных точках значения функции не могут быть меньше Г, + >. В самом деле, здесь /(х,, )— — ~~, = /(х, .; ) — ~~ = /(х>, ) — /(е ) + Л ' + ) — Рь > — 7 ~*> — юь >~+/(»,~>) — Р ) 0 в силу (2) и (5).

Общий шаг метода описан. Так как на каждом шаге метода берется новая точка сетки П„, которая еще не исключалась из перебора и в которой значение функции /(х) еще не вычислялось, то ясно, что на каком-то шаге описанного процесса перебора такая новая точка не найдется и процесс закончится за А! шагов, Аг < тп, т, ... т„, перебором точек е„ ..., е сетки П„ и определением величины Г„ = пнп /(е,.) = ппп /(х, , ) = Г„.

В силу теоремы 1 величина >к кн ' п„ Рь довлетворяет неравенствам (3). П 'Г ак н в одномерном случае, нетрудно привести примеры, когда изложенный метод покрытий может превратиться в метод простого перебора точек сетки П>е В то же время ясно, что если величины Хь — Г„~„ /(»е~,) — Ре в (4), (5) достаточно большие, то многие точки сетки П„будут исключены из перебора без вычисления в них значения функции. Различные модификации метода покрытий на классе функций (2), обобщения этого метода на более сложные области, чем параллелепипед, на многокритериальные задачи, а также другие методы поиска глобального минимума читатель может найти, например, в 1286; 309; 493; 526; 590; 591; 661; 662; 671].

е 14. Метод модифицированных функций дагранжа 1 Рассмотрим задачу /(х) — !п1; хе Х=(хе Е": *е ХФ д (х) < О, >' = 1,..., т, д (х) = О, г = т + 1,..., е), (1) где /(х), д,(х),..., д„(х) — заданные функции на множестве Х . Пусть |„> > — оо, Х„фЯ. Для выпуклой задачи (1) при различных дополнительных 318 Гл. З.

МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ предположениях в 9 4.9 было установлено, что найдутся множители Ла-. гранжа Л" =(Л;,..., Л,*): Л" Е Лр = (Л Е Е'! Л, > О,, Л > 0) такие, что пара (х., Л*), где х, Е Х„, образует седловую точку функции Лагранжа Е(х, Л)=з(х)+ Я Лзд(х), хЕХр, Л ЕЛр, (2) «=! Х (х„, Л) < Ь(х„Л') = ~, < Е(х, Л*), х Е Хр, Л Е Лр, (3) Была также доказана справедливость обратного утверждения: если (х„Л*) е Хр х А является седловой точкой функции (2), то х. е Х,. Основываясь йа этих фактах, можно предложить различные методы решения задачи (1), сводящиеся к поиску седловой точки функции Лагранжа.

Например, здесь естественным образом напрашивается итерационный процесс, представляющий собой метод проекции градиента по каждой из переменных х и Л (спуск по переменной х и подъем — по Л): т. е х„„, = Р,,(хз — оз 7,(хю Л„)), (4) Лл+! = Рл,(Л» + сз йл(хл~ Л»)) = Рл»(Л» + сз»д(х»)), й =О, 1,... (5) где зл,. = шах(Л«, О), з = 1,, т, зз! = Лз, з = т+ 1,..., з. Вместо. (4) возможно использование других итерационных процессов, таких, как метод Ньютона и др. В тех случаях, когда задача минимизации функции (х, Л) по переменной х ~ Хр при каждом фиксированном Л ~ Л решается достаточно просто, можно предложить следующий итерационныи метод: Х,(х,»„Л)= ш1 з (х, Л„), Л„+,— — Р, (Лл+гз»д(х»»!)), й =0,1...

««Х« Однако, как оказалось, сходимость перечисленных методов удается доказать лишь при довольно жестких ограничениях на данные задачи (1). Приведем простейший пример выпуклой задачи, когда метод (4), (5) не сходится к седловой точке функции Лагранжа. Пример 1. Пусть 7(х)зеО, Х =(хя Е'.

д(х)= х=О). Тогда Г.=О, Х, =(О). Функция Лагранжа 5(х, Л) = 7(х)+Лд(х) аз Лх на Хр хЛр = Е! х х Е' имеет седловую точку (О, 0). Процесс (4), (5) здесь имеет вид хз «! = х» сзл Л л Л з» ! = Л з + а»*» Поскольку х„'„, + Л,'+, — — (х„'+ Л',)(1+ аз) > х„'+ Лз, й = О, 1,..., то ясно, что при любых (х, Лр) ф 0 и любом выборе длины шага зз, > 0 этот процесс расходится.

5„(хю Лз) =(Ь„,(х, Л),, Ь„.(х, Л)), Х л(х, Л = (Ьл (х, Л),..., Лл (х, Л)) = (д (х),..., д (х)) = д(х); длину шага ззл в (4), (5) можно выбирать из тех же соображений, как это делалось выше в 9 2. Заметим, что проекция любой точки Л Е Е' на множество Лр вычисляется просто по формулам Р„(Л) = (зз„..., зз,), где 4 14. МЕТОД МОДИФИЦИРОВАННЫХ ФУНКЦИЙ ЛАГРАНЖА 319 Анализ перечисленных методов показывает, что причина их расходимости заключается в том, что функция Лагранжа (2) по переменной Л не очень хорошо «устроена». Чтобы преодолеть возникающие здесь трудности, можно попытаться видоизменить функцию Лагранжа, строить так называемые модифицированные функции Лагранжа, которые имеют то же множество седловых точек, что и функция (2), и которые обладают лучшими свойствами, чем функция (2).

Такие функции, оказывается, существуют и могут быть использованы для поиска седловой точки функции (2) и для решения задачи (1). Следуя [24], мы рассмотрим один из возможных здесь подходов. 2. Будем рассматривать задачу ,7(х) — 1п1, хб Х =(х ЕЕ": х ЕХр, д(х) <0), (6) где у(х), д(х) = (д,(х),..., д (х)) — заданные функции из С'(Хр). Как и в гл. 3, векторное неравенство д = (д„..., д„) > 0 [д < О] здесь н ниже означает, что д«> 0 [д! < О] при всех з = 1,..., тп, а неравенство а> Ь для а, Ь е Е эквивалентно неравенству а- Ь > О.

Наряду с классической функцией Лагранжа задачи (6) 5(х, Л)=л'(х)+(д(х),Л), хЕХр, Л ЕЛ« — — (Л еЕ: Л >0)=Е (7) еще рассмотрим следующую модифицированную функцию Лагранжа; М(х, Л)=У(*)+ —,'„[(Л+Ад(х)) ]' — —,',]Л[' (8) переменных х е Х, Л е Лр, где А — произвольная фиксированная положи. тельная константа; в (8) принято обозначение а+=Рз.(а) =(а+,,..., а'„), а« =шах(а,;0), з=1,...,тп, (9) — проекция точки ае Е на положительный ортант Е„". Нетрудно видеть, что функция ~о(я) = (шах(з; 0))' = (х")з одной переменной непрерывно дифференцируема на всей числовой оси Е', причем Ф'(х) = 2 шах(зц 0) = 2х+. Отсюда следует, что при 7(х), д(х) Е С'(Хр) функция (8) непрерывно дифференцируема по х и Л, причем — = М.(*») = Г(х)+ (д'(х))'(Л + Ад(х))', рл — — Мл(х, Л) = А[(Л+ Ад(х)) — 'Л], хЕ Хр, Л 6Е где д'(х) — матрица порядка тп х и, у которой в з-й строке, т'-м столбце дсе(х) = ',, з = 1,..., тп, т' = 1,..., п, а матрица (д'(х))т получена трансДр,.

(х) понированйем д'(х). Далее, пользуясь теоремами 4.2.7, 4.2.8 и следствиями из них, нетрудно показать, что если Хр — выпуклое множество и функции 7'(х), д,.(х) выпуклы на Х, то функция М(х, Л) выпукла по переменной х на множестве Хр при лзобом фиксированном Л е Е . Отметим также, хотя это ниже явно йе будет использовано, что М(х, Л) является вогнутой по переменной Л на множестве Лр при любом фиксированном х е Хр — в этом проще всего убедиться, доказав неравенство (Мл(х, Л ) — М,(х, зз), Л вЂ” зл) < 0 для всех Л, И е Лр и затем обратившись к теореме 4.2.4. дк (23) у, ! ! Ф.П, Вгскльег 320 Гл.

5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Перейдем к описанию метода решения задачи (6), использующего фуницию М(х, Л). В качестве начального приближения возьмем любые точки хо е Хо, Ло Е Ло. Пусть ?с-е приближение хь е Хо, Ль ~ Л, уже известно. Составим функцию (ср. с $6) Ф„(х) = 2)х — хь!'+ стМ(х, Л„), х ш Хо, (11) где ст — некоторое положительное число, являющееся параметром метода. Предположим, что существует точка эь удовлетворяющая условиям эь е Х„Ф„(э,) = !п( Ф,(х). (12) В качестве следующего (В + 1)-го приближения возьмем точку хьч, такую, что х„„, Е Х„, Ф„(хь,) < !п1Фь(х)+6ьз/2, )д(хьч!) — д(эь)( < 6„, (13) '"а где 6„ > О, 1пп 6„ = О. В частности, если точка э„ из ( 1 2 ) известна, то ь-.

можно принять хь+, —— э,; в общем случае для определения хьт! из условий (13) нужно решать задачу (12) с помощью какого-либо сходящегося метода минимизации. Дальнейшее изложение не зависит от того, каким методом решается задача (12), поэтому здесь мы можем ограничиться предположением, что имеется какой-либо достаточно эффективный метод решения задачи (12), позволяющий за конечное число итераций найти точку х.ты которая удовлетворяет условиям (13). После определения хьч! точка Л„ находится по формуле Льт! =(Л„+ Ад(х,,))+.

(14) Правила получения (!с+ 1)-го приближения х. т ! е Х„Л, ч ! е Л изложены. Описанный метод кратко будем называть методом (13), (14). Для исследования сходимости метода (!3),(14) нам понадобятся некоторые свойства функции а", определенной равенства. ми (9). Из теоремы 4,4.2 следует, что (а+ — Ь+! < )а — Ь! уа, Ь Е Ет. Далее, система соотношений д<0< Л>0, Лчдг=О, ч=1,...,эч, (16) эквивалентна авенств Р у Л =(Л+Ад)+ (17) при любых постоянных А > О. В самом деле, если выполняются соотношения (!6), то либо д.

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

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

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

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