Обоснование и алгоритм метода скорейшего спуска решения задачи многомерной минимизации.
Пусть выбрано некот нач-е приближение 
и на некоторой итерации построено очередное приближение 
и вычислены значения 
, 
. Рассм.луч, проходящий ч/з т в направлении антиградиента 
.В этом луче рассм. ф-ю, зависящую от альфа 
. Рассм. вспомогательную задачу одномерной минимизации 
(*).
И пусть решение этой задачи достигается в т 
: 
, тогда след. приближение вычисляется по ф-ле 
.
Итерационный процесс продолжается до тех пор, пока не будет выполнен критерий окончания счета.
В качестве критерия окончания счета могут использоваться нерав-ва:
; 
; 
,где 
, 
, 
–заданные числа, характеризующие точность счета
Если на некоторой итерации выполняется рав-во 
, то в т-ке хk выполн. необход. усл. Оптимальности и итерационный процесс заканчивается.
Если 
, то сущ.такое неотрицат. 
, что 
.
Если значения 
явл. решением задачи (*), то в этой т-ке должно быть выполнено необходимое усл. оптимальности, т.е. 
Вычислим эту производную в т-ке 
Получаем, что градиенты, вычисл. в соседних приближениях, постоенных методом скорейшего спуска ортогональны.
Зам. Величину можно выбирать из условия 
, в этом случае метод наз градиентным.
Алгоритмы метода условного градиента и метода проекции градиента решения задачи многомерной условной минимизации.
1)алгоритм метода условного градиента. Пусть задано начальное приближение 
и методом условного градиента вычислено 
Строим ф-цию 
и решаем задачу 
(1)
Пусть 
есть решение задачи. Заметим, что 
. Если 
, то 
уд. необходимому усл. и вычислительный процесс заканчивается. Если 
, то строим отрезок 
(2) на этом отрезке рассматриваем ф-цию 
и решаем задачу 
(3).
Тогда след.приближение находится по формуле 
где 
есть решение задачи (3).
Практическим критерием окончания счета выбираются нер-ва 
где 
согласованные числа, характеризующие точность счета.
Замеч1. Метод условного градиента эффективен когда вспомогат. задача (1) допускает простое решение.
Замеч2.Часто на практике задают некоторое значение 
, н/р, равное 1, проверяют усл. 
. Если оно не выполняется, то 
уменьшают, например, в два раза и т.д.
2)алгоритм метода проекции градиента. Пусть задано нач. приближение 
и методом проекции градиента вычислено 
. След.приближение ищется по формуле 
(4) В зависимости от выбора 
строятся различные варианты метода проекции градиента. Например, 
может находиться как решение задачи одномерной минимизации
(5), где 
(6)
В этом случае при 
метод проекции градиента превращается в метод скорейшего спуска.
Часто при практическом исп. метода (4) находят такое 
, что выполняется условие релаксационности 
При его нарушении полагают 
равным 
снова проверяют условие релаксационности и т. д.
В качестве критерия окончания счета выбираются неравенства 
, где 
— числа, характеризующие точность счета.
Замеч4. Главная сложность реализации метода проекции градиента заключается в решении задачи проектирования.
Дата добавления: 2019-07-15; просмотров: 665; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!