Градиентный метод с дроблением шага

В методе градиентного спуска с дроблением шага величина шага a_к выбирается так, чтобы было выполнено неравенство:

f(x_k-a_k )-f(x_k)£-da_k|| ||²,

где 0<d<1 – произвольно выбранная постоянная (одна и та же для всех итераций). Это требование на выбор шага a_к более жесткое, чем условие убывания, но имеет тот же смысл: функция должна убывать от итерации к итерации. Однако при выполнении неравенства функция будет уменьшаться на гарантированную величину, определяемую правой частью неравенства.

Процесс выбора шага протекает следующим образом. Выбираем число a>0, одно и то же для всех итераций. На к-й итерации проверяем выполнение неравенства при a_к=a. Если оно выполнено, полагаем a_к=a и переходим к следующей итерации. Если нет, то шаг a_к дробим, например, уменьшаем каждый раз в два раза, до тех пор, пока оно не выполнится.

Схема алгоритма

Шаг 1.

Задаются х₀, e₃, d и начальное значение шага a. Вычисляется значение градиента – направление поиска. Присваивается к=0.

Шаг 2.

Проверяется условие:

f(x_k-a )£-da|| ||².

Если выполняется, то переходим к шагу 3, иначе дробим значение a (a=a/2) и повторяем шаг 2.

Шаг 3.

Определяется точка очередного эксперимента: х_к+1 = х_к - a .

Шаг 4.

Вычисляется значение градиента в точке х_к+1: .

Шаг 5.

Если || ||£e₃, то поиск заканчивается, при этом:

3. Метод наискорейшего спуска.

В градиентном методе с постоянным шагом величина шага, обеспечивающая убывание функции f(x) от итерации к итерации, оказывается очень малой, что приводит к необходимости проводить большое количество итерации для достижения точки минимума. Поэтому методы спуска с переменным шагом являются более экономными. Алгоритм, на каждой итерации которого шаг a_к выбирается из условия минимума функции

называется методом наискорейшего спуска. Разумеется, этот способ выбора a_к сложнее ранее рассмотренных вариантов.

Реализация метода наискорейшего спуска предполагает решение на каждой итерации довольно трудоемкой вспомогательной задачи одномерной минимизации. Как правило, метод наискорейшего спуска, тем не менее, дает выигрыш в числе машинных операций, поскольку обеспечивает движение с самым выгодным шагом, ибо решение задачи одномерной минимизации связано с дополнительными вычислениями только самой функции f(x), тогда как основное машинное время тратится на вычисление ее градиента .

Следует иметь в виду, что одномерную минимизацию можно производить любым методом одномерной оптимизации, что порождает различные варианты метода наискорейшего спуска.

Схема алгоритма

Шаг 1.

Задаются х₀, e₃. Вычисляется градиент , направление поиска.

Присваивается к=0.

Шаг 2.

Определяется точка очередного эксперимента:

х_к+1 = х_к - a_к ,

Шаг 3.

Вычисляется значение градиента в точке х_к+1: .

Шаг 4.

Иначе к=к+1 и переход к шагу 2.

Задание 1. Составить программы, реализующие методы многомерной безусловной минимизации: градиентный метод и метод наискорейшего спуска.

Задание 2. Найти точку минимума целевой функции f(x)=f(x₁, x₂) с заданной точностью e указанными методами. Начальное приближение x₀ и точность e приводятся в условие задачи. Сравнить результаты, полученные разными методами для одной и той же целевой функции (в частности, сравнить число вычислении целевой функции и её производных, понадобившихся для получения заданной точности).

Целевая функция f(x)=f(x₁, x₂) зависит от двух аргументов.

1) Функция f(x) следующего вида: f(x)=ax₁+bx₂+e ^{c x}₁^{+d x}₂

2) f(x)=18 x₁²+12х₁+15x₂²+17 x₂+10

Начальное приближение [5; 5], точность решения 0,001. Шаг алгоритма равен 0.001.

Поиск по сайту: