Первая лаба в виде буклетика (774587), страница 2
Текст из файла (страница 2)
В случае поиска минимума функции «(Х) выберем то (й) Л *, которос соответствует минимальному значению «(Х„") сре- ди значений «(Х,), т.е. при «(Х )= шш «(Х„) примем Р= 1,8 у()=Л ° и Х=Х (й) Р в случае поиска максимума функции «(Х) при «(Х *)= (й) (й) = шах «(Х„) примем у = Л. и Х=Х *. э=1,г 3. Если «(Х)>«(Х()) при поиске минимума «(Х) (или «(Х)~ «(Х ) при максимуме), то переходим к п, 1, иначе Х (й+ 1) 4.
Конец алгоритма. д. Метод е обучением В отличие от первых двух методов без обучения в данном методе учитывается опыт выбора удачного направления поиска экстремума на двух предыдущих итерациях. Алгоритм нахождения у() н Х( ) на Й-и итерации состоит (й+ 1) в следующем. 1. Вычисляем (й) Л (й) + И'(й) = ПЛ(й), В(й)Ц,' (й) 1,« (Х (й) ) ,(й) 1,«(Х(й) ) (1.8) а минимума где — )7«(Х ) называют антиградиентом. В обоих случаях используем постоянный п|аг в направлении поиска экстремума на всех итерациях й ) = й = сове( при любом Й, (й) (1.1Р) «(Х ) с «(Х ) при поиске минимума, (1 11) «(Х( + )) > «(Х( )) при поиске максимум».
В противном случае надо уменьшить значение Ь, иначе итерационный процесс может быть расходящимся или зацикливаться. В общем случае при невыполнении на (Й„+ 1)-й итерации (г = 1, 2, ... ) условия (1.11) выбираем шаг в направлении поиска экстремума на итерации Й следующим образом: Ь()= й= сопз1 при Й= 0,61, 6( ) = Ь = сопз1(г) й е при Й~+ 1 Йг+1 где 6> Ь,> Ь,+1 (е= 1,2...) и данные константы 6, выбираются (путем их уменьшения с ростом г) так, чтобы выполнялось условие (1.11).
На рис. 1.2 показан пример влияния выбора значения шага 6( ) па сходимость итерационного процесса нахождения миниму(й) ма функции «(х) = ах, а> О. При Ь= — происходит зацикли- 2 а ванне: х = — х, х = х (рис, 1.2, а). В случае (й + 1) (й) (й + 2) (й) где й необходимо выбирать достаточно малым положительным числом, чтобы процесс нахождения экстремума сходился. В общем случае в методе градиентного спуска (с фиксированным шагом 6) может не обеспечиваться сходимость итерационного процесса нахождения экстремума. На каждой итерации Й следует проверять выполнение условия: Х (Й + () Х (Й) + Й (ь) (Й) 5.
Рассчитываем )'(Х ) и дополнительно для градиент(Й+1) 1 ( + )) и его норму ~ ~ Ч((х~ ))~~ = — х (...( 6. Вели выполняется критерий завер!пения поиска экстремума, то переходим к п. 7, иначе принимаем Й= Й+.1 и переходим кп. 2. 7. Конец алгоритма. Критерием завершения поиска экстремума служит: 1) для градиентных методов ~ ~ Ч~(Х(А+1) ) ! ~ < (1.7) 2) для методов случайного поиска ~ у(Х("+") - у(Х(Й-г) ) ~ «е (.= О,1); последний критерий означает, что на протяжении трех итераций значение функции практически не изменяется.
Итерационные методы отличаются между собой тем, как выбираются направление у() и !паг Ь поиска экстремума. Особен(ь) (Й) ности этого выбора в шести перечисленных методах будут рассмотрены ниже. Метод градиентного спуска Направление градиента Ч7"(Х) есть направление наибыстрейшего возрастания функций ((Х) в точке Х.
Поэтому за направление поиска максимума на итерации Й принимаем — с обучением. Общий алгоритм решения задач безусловной оптимизации с помощью итерационных методов состоит в следующем: 1. Выбираем начальное приближение Х и точность реше(о) ния е, принимаем Й = О . 2. Определяем направление й'( поиска экстремума на итера- (Й) ции Й. 3.
Выбираем величину шага Й( ) в направлении поиска. (Й) 4. Вычисляем где Л вЂ” случаиныи вектор с известной функцией распределе- (ь) ния (часто используют равномерное распределение на отрезке [ — 1, 1) ); И' — детерминированный вектор, определяемый по ()!) формуле: )4,-(ь) ) ~,.(ь — () „ + б з ('7(Х(Й) ) у(х(ь О))(х(ь) Х(ь В ) с использованием знака «+» при 5 в случае поиска максимума фун при у> О, кции )'(Х) и «-» при минимуме )'(Х); зяп(у) = — 1 при у< О, О при у= О; (о) !Ф вЂ” О, )) — параметр запоминания; 5 — параметр обучения, р и Ь вЂ” малые положительные величины, которыми регулируют степень детерминированности и случайности направления Х() поиска экстремума. 2. Находим Х= Х(~)+ Й(~)А (~). 3.
Всли ~(Х) > ((ХОО) при поиске минимума ((Х) (или 7(Х) ~(Х ) при максимуме), то переходим к и. 1, иначе < ! (Й) ) Х (« + () Х 4. Конец алгоритма. ВАРИАНТЫ ЗАДАНИЯ Для каждого номера варианта У= 1,2О в табл. 1 1 задана целевая функция 7(Х) в задаче ее безусловной оптимизации ех1г 7(Х). х Целевая 2 2 2 !+ Х2+ Хз ! Х2+ ХЗ 2 2 2 2+ х,2+ х2+ 2 2 Окончание табл. 1.1 Номер 'варианта Ж Целевая функция 1'(Х) 2 х г + х зг+ х з 4 х1 — 3 хг 6 х з+ 5 4 ! 1.5 х1+ хг+ хз 1 хгхз Зхг+ 9хг+ 1 3 з1+ хг+ хг — Зх, — 2хг+ 2хз+ 2 х, + х 2+ Х '3 — 2 х, — 4 х 2 — 3 хз — 1 2 2 3 Х1+ хг+ Хз+ Х1хг+ Зхг Зхз+ 3 Х1+ хг+ Зхз+ х1хз Зхг 4 2 3 2 х, + ха+ хз+ х, хз+ бх, — Зхг+ 1 2 3 г х1+ ха+ хз — 2х1 — 3 ха — 4х3+ 3 3 2 ЗХ1+ х2+ хз+ х1хг- Зхз 5 2 3 х1+ х2+ 2 3+ 2х1 2х2 Зхз+ 7 хз+ 2х + х — Зх — 4х — 6х — 2 2 2 1 2 ' 3 1 2 3 Х, + Х 2+ Х 3+ Х, Хг+ 9 Хг — 3 Х 3+ 33 3.
Формируем систему уравнений относительно неизвестных Х1)= (х1) ... Х1) 1 и 71)= 111), ... 11)). 1 '"'' п 1 '"'' и "( в) ' — ",( ") -' — '( )' = и (, 1а)) ( ) — (Х1) ) 21)+ (Х1) ))А)+ + ( 1а) ),1ь) др,, „ар„, „, а„. а „ (Х. Сь) ) 4. Примем )2 = 0 . 5. Подставляем значение Х в систему (1.5) уравнений, в 1ь) результате чего она становится системой линейных алгебраических уравнении относительно неизвестных 11 ) (3= 1, я).
6. Решая данную систему, определяем Т1). 7. Находим Х = Х + Т (илн в координатной форме ()1+ 1) 1)') 1)1) х,'"'"= Х~1)+ 1(") (3= 1,п)) и,~(Х'"'"). л 8. Ксли ~ (11 ) > е, тогда примем Й= Й+ 1 и перехоч / 1Ь) ) 2 1= 1 дим к и, 5, иначе к и. 9. 9. Конец алгоритма, Общий алгоритм решения задач безусловной оптимизации с помощьзо итерационных методов поиска безусловного экстремума Существует две группы таких итерационных методов: 1) градиентные методы; 2) методы случайного поиска.
Основными в первой группе являются следующие методы: — градиентного спуска; — наискорейтего спуска; — сопряженных градиентов. Во второй группе выделяют сведующие основные методы: — с возвратом яа неудачном таге; -- наилучшей пробы; а 11( > О, А (Х)= (Х ) а„1(Х ) и отрицательно определенной, если Ь (Х ) < 0 при нечетных ) и Ь.(Х ) > 0 при четных ) (,)= 1,а).
Отсюда следует, что если все определители Ь.(Х*) > 0 (,1 = 1, и ), то Х вЂ” точка минимума„если знаки определителей чередуются, начиная с отрицательного, то Х вЂ” точка максимума. 1 у Отметим, что Ь =,,', а,ЬВ;Ь= ~~1, а,ЬВ~, й=1 1 1 (разложение по любой 1-й строке ((е 1,у) или любому а-му столбцу (йн $,д)), В,ь-— (- 1) М,ь, 1+1 где 012 — алгебраическое дополнение элемента а,.„; М,„— дополнительный минор, получающийся из определителя Ь вычеркиванием строки 1 и столбца Й .
Метод Ньютона В случае, когда точное решение системы уравнений (1,4) найти трудно, применяют приближенные численные методы ее решения, К ним относят метод Ньютона, который обеспечивает быструю сходимость, но имеет трудность выбора начального приближения, гарантирующего сходимость. Итерационный алгоритм нахождения стационарных точек по методу Ньютона состоит в следующем. д1' 1. Находим ср,.(Х)= (Х) (1= 1,а) 2. Выбираем начальную точку Х( ~= (х~1 ~....,х( ~) и точность решения е (малое положительное число, например е= 10 ), находим ДХ~ ~). ПОРЯДОК ВЫПОЛИЕИИЯ РАБОТЫ Для Вашего варианта задания необходимо: 1. Найти решение задачи безусловной оптимизации функции У(Х) с помощью следующих методов: 1) классического; 2) Ньютона; 3) градиентного спуска при заданном Ь= 0,2; 4) наискорейшего спуска. В трех итерационных методах выполнить вручную только по одной итерации, используя одинаковое значение Х( ~, компоненты которого должны отличаться от найденного по классическому методу экстремума на +1.
2. Провести сравнительный анализ полученных' на первой итерации результатов решения заданной задачи безусловной оптимизации функции с помощью трех итерационных методов, сформулировать выводы и показать полученные результаты преподавателю. 3. Выполнить на ЗВМ расчет безусловного экстремума функци.ч У(Х) с точностью е= 10 согласно методам: Ньютона и трем градиентным, включая метод сопряженных градиентов. 4.
Выполнить сравнительный анализ результатов решения одной и той же задачи безусловной оптимизации функции с помощью пяти используемых в работе методов и сформулировать выводы. ПРИМЕР где У(Х) = х1+ х2+ хз+ хзхз — Зх1+ бх2+ 2. 3 2 2 Вначале найдем решение данной- задачи по классическому методу. Согласно необходимому условию экстремума функции ~(Х) получаем (Х) = 3х1 — 3= О, 2 дх, дх2 ! дхз (Х) = 2х2 + хз+ 6= О, (Х) = 2 х з+ х 2 — — 0. Пусть номер варианта задания У= 20. Тогда задана следующая задача безусловной оптимизации: ех1г 1(Х), Х 1 0 2 1 О 1 2 Дз= 1+2 О 2 бх1 0 Ь2= О 2 = 12х1, Ь1= бх1 11(Х ) 12(Х ) 21(Х ) 22( й 2 (Х > О,... Решая данную систему уравнений, находим х1= + 1, х 2= — 4, хз — — 2, т.е. получили две стационарные точки: Х1= (1; — 4; 2), Х2= (- 1; — 4;2) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
