 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Метод градиентного спуска
В соответствии с основной идеей градиентного метода будем
строить элементы минимизирующей последовательности {Хк}
с помощью рекуррентной формулы (2.21), где в качестве направле
ния S выбирается направление антиградиента как направление
наискорейшего убывания функции ДАО в малой окрестности точ
ки X. Вычислительная схема метода градиентного спуска такова:
^'=*-акГ(Хк),к = 0, 1,2,... (2.22)
Величина шага выбирается так, чтобы выполнялось условие
АХш)</(Хк),к = 0,1,2,... (2.23)
fruZbl** (2-25)
11/(*)1|£е,, (2.26)
где г.- заданные параметры точности.
Опишем алгоритм рассмотренного метода градиентного спуска.
Шаг 0. Задать параметр точности г > 0, начальный шаг а > 0, параметр алгоритма Х.е(0;1), выбрать Х°еЕ", вычислить зна-чение/Х-Л"0), положить к = 0. ■
Шаг1. Найти градиент/' (X*) и проверить условие достижения заданной точности ||/' (Хк) || < s. Если оно выполняется, то перейти к шагу 4, иначе - к шагу 2.
Шаг 2. Найти новую точку в направлении антиградиента Х=Хк - <*/'(**) и вычислить/^- Если/(Х) <f(Xk), то положить Х*+> = Xk,f(Xk*') =f(Xk),k=k+\,n перейти к шагу 1, иначе- перейти к шагу 3.
Шаг 3. Положить а = аЛ, где 0 < А. < 1 и перейти к шагу 2.
Шаг 4. Завершить вычисления, положив Х"- Xk,f'=f(Xk).
Метод наискорейшего спуска
В этом варианте градиентного метода минимизирующая последовательность {Хк} также строится по правилу (2.22). Однако величина шага ак находится в результате решения вспомогательной задачи одномерной минимизации
min{q>t(a)|a>0}, (2.27)
где ф4(а) =/(#*- а /'(**))• Таким образом, на каждой итерации в направлении антиградиента S* = -/' (**) выполняется исчерпывающий спуск. Для решения задачи (2.27) можно воспользоваться одним из методов одномерного поиска, изложенных в разд. 1, например, методом поразрядного поиска или методом золотого
сечения.
Опишем алгоритм метода наискорейшего спуска.
| ШагО,Задать параметр точности е > 0, выбрать Х*еЕ\ по- Л0ЖИШаМ°Найти/' (X) и проверить условие достижения за- -------- ' м /• iv*\ ii <■ р Venn оно выполняется, то перейти данной точности ||/ (л)||<£. £сли они се к шагу 3, иначе - к шагу 2. Шаг 2 Решить задачу (2.27), т.е. найти а,. Найти очередную |
УТ^Х-а/ЧПположитьА ^1ипершагу1. Шаг 3. Завершить вычисления, положив л -л,/ /(.л;.
2.3.3. Типовой пример
Минимизировать функцию
f(X) = xf +4х22-6^-8^ +13. (2.28)
Вначале решим задачу классическим методом. Запишем систему уравнений, представляющих собой необходимые условия безусловного экстремума:
А»,
Решив ее, получим стационарную точку X *= (3; 1). Далее проверим выполнение достаточного условия, для чего найдем матрицу вторых производных:
Ч:)
Так как согласно критерию Сильвестра, эта матрица положительно определена при УХеЕ2, то найденная точка X* является точкой минимума функции/(А). Минимальное значение / =/(Х)=0. Таково точное решение задачи (2.28). ,-> лс В^полним ОД"У итерацию метода градиентного спуска для (2.28). Выберем начальную точку X" =(1; 0), зададим начальный шаг а = 1 и параметр X = 0,5. Вычислим/^0) = 8. 36
Найдем градиент функции Дл) в точке л"0:
(2.29)
Определим новую точку Х= Х°- а/'(Х°), вычислив ее координаты:
| | |
х. =х, -сс-
(2.30)
| . = х, -а- |
| дх, |
- = 0-а(-8) = 8а =
Вычислим/(Х) =f(X°- а/' (л"°)) =200. то выполняем дробление шага, полагая а = а\= 1 0,5 = 0,5. Снова вычисляем по формулам (2.30) х,=1+4а = 3; х = 8а = 4 и находим значение/(А) = 39. Так как опять/(л) >ДХ°), то еще уменьшаем величину шага, полагая а = аХ=0,5-0,5 = 0,25. Вычисляем новую точку с координатами х,=1+40,25=2; х2=8-0,25=2 и значение функции в этой точке/(л) = 5. Поскольку условие убыванияДА) <f{X°) выполнено, то считаем, что найдена очередная точка минимизирующей последовательности Xх = (2;2). Первая итерация градиентного спуска завершена.
Выполним одну итерацию по методу наискорейшего спуска для (2.28) с той же начальной точкой А"°= (Г, 0). Используя уже найденный градиент (2.29), находим
1 8аJ
и строим функцию Фо(а) =/(Х°- а/'(А°)) = (4а - 2)2+ 4(8а - I)2. Минимизируя ее с помощью необходимого условия Ф'о(а) = 8(4а - 2) + 64(8а - 1) = 0,
находим оптимальное значение величины шага ао=5/34.
Определяем точку минимизирующей последовательности
| '27 20 U7J |
1 + 4--
8-1
34 J
Первая итерация завершена. Подсчитав компоненты векто-ра/'СДГ1)
| 20 17 |
| 48. 17' |
24^
| дх. |
17'
можно убедиться, что скалярное произведение
т.е. что 1" - точка минимума функции (2.28).
Порядок выполнения лабораторной работы 1. Кратко описать изучаемые градиентные методы 1 геометРическУю иллюстрацию полученного индиви-
| комплекса |
асче™ГеннЬ - ИШОЛЬЗОВанием компьютерного
Задания для лабораторной работы
1. Минимизировать функцию /(Х)=л,2 +4л22 -4х, -8х, +5
из начальной точки Z°=(l; 2).
2. Минимизировать функцию f{x) = 4xf +x22 -16x, -2х2 +17
из начальной точки Х°= (0;0).
3. Минимизировать функцию f{X) = х,2 +4х22 -Юл:, -48х2 +
+ 169 из начальной точки Х"= (0;0).
4. Минимизировать функцию /(Аг) = 4х,2 +.х:2 -40х, -12х2 +
+ 136 из начальной точки Х°= (0;0).
5. Минимизировать функцию /(X) =.v,2 +4,r2 -6х, -8х2 +13
из начальной точки Х°= (0;0).
6. Минимизировать функцию f(X) = Ах2х + х\ - 24х, - 2л-2 + 37
из начальной точки X"— (2;0).
7. Минимизировать функцию f(X) = x* +9xj -4л:, -18jc2 +13
из начальной точки Ха= (1;0).
8. Минимизировать функцию f(X) = 9х,2 + л-2 - 36л, - 2х2 + 37
из начальной точки Х°= (2;0).
на итерационный процесс решен™ Пс1раметРов алгоритмов
отразить в работе. заДачи. Содержание отчета
3S
3. МЕТОДЫ ОПТИМИЗАЦИИ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ
Рассмотрим в общей постановке задачу нелинейного программирования, заключающуюся в отыскании минимума функции многих переменных при заданных ограничениях в виде равенств и неравенств.
Целевую функцию/W = /(*,, хг,..., х„) и функции h^X) -= hj(xlt xv..., х„), j =1,..., m; g,(X) = &(*„ xv..., xn), s = 1,..., p, задающие ограничения, будем рассматривать как функции, заданные в точках «-мерного евклидова пространства Е".
Изучим наиболее употребительные методы решения рассматриваемых задач вида
mm{f{X)\XeR}, (3.1)
где R допустимая область, задаваемая ограничениями типа равенств и неравенств
() г 0,s = 1,...,р). (3.2)
В случае гладких выпуклых функций f(X), h (X) g(X) поставленная задача (3.1) может быть решена применением необходимых и достаточных условий, устанавливаемых теоремами куна - 1 аккера. Однако для решения большинства практических задач используются приближенные численные методы. Рассмотрим некоторые из них, представляющие две группы методов. ^ГДИСПОЛЬЗУЮЩИе11рб
в рассмотрение вспомога-
тельных функций. Эти методы называют методами последовательной безусловной оптимизации.
2. Методы решения задачи условной оптимизации, основанные на движении из одной допустимой точки, где выполняются все ограничения, к другой допустимой точке с меньшим значением целевой функции. Таким методом является, например, метод возможных направлений.
Основная идея методов первой группы состоит в том, чтобы аппроксимировать исходную задачу условной оптимизации некоторой вспомогательной задачей, решение которой менее сложно. Очевидно, что ограничившись лишь одной вспомогательной задачей, можно получить лишь приближенное решение. Если же использовать надлежащим образом построенную последовательность задач без ограничений, то искомое решение исходной задачи может быть найдено с требуемой точностью как предел соответствующей последовательности приближенных решений.
Методы непосредственного решения задачи условной оптимизации, образующие вторую группу, позволяют построить для целевой функции минимизирующую последовательность допустимых точек, сходящуюся к искомому точному решению поставленной задачи.
3.1. Методы последовательной безусловной оптимизации
Поиск по сайту: