Алгоритм метода дробления шага

Шаг 0. Задать параметр точности , начальный шаг , выбрать

       х⁰ , вычислить f(x⁰).

Шаг 1. Найти  и проверить критерий останова: || ||< .

       Если он выполнен, то вычисления завершить, полагая

  x *= x ⁰, f *= f (x ⁰).

Шаг 2. Положить х¹=х⁰- α , вычислить f(x¹). Если f(x¹) < f(x⁰),

        то положить х⁰=х¹, f(x⁰) = f(x¹) и перейти к шагу 1.

Шаг 3. Положить  и перейти к шагу 2.

 

Пример 1. Решить задачу методом градиентного спуска.

Решение. .

Итерация 1.

2. Зададим x⁰=(0.5,1), f(x⁰)=1.5.  Выберем =0.01,  .

3. = (2, 2), || ||> .

4. Положим х¹=х⁰- =(0.5 -2, 1-2)=(-1.5,-1), f(x¹)=5,5, f(x¹) > f(x⁰).

5. Положим = 1/2 и перейдем к шагу 2.

6.  Положим х¹=х⁰- =(0.5 -1, 1-1)=(-0.5,0), f(x¹)=0.5. Так как f(x¹) < f(x⁰), то полагаем х⁰=х¹=(-0.5,0), f(x⁰) = f(x¹)=0.5 и переходим к шагу 1.

Итерация 2.

7. =(-2,0), || ||>

8. Положим х¹=х⁰- =(-0.5 +1, 0)=(0.5,0), f(x¹)=0.5, f(x¹) = f(x⁰).

9. Положим = 1/4 и перейдем к шагу 2.

10. Положим х¹=х⁰- =(-0.5 +0.5, 0)=(0,0), f(x¹)=0, f(x¹) < f(x⁰).

Полагаем х⁰=х¹=(0,0), f(x⁰) = f(x¹)=0 и переходим к шагу 1.

11. =(0,0), || ||=0 <  - останов, найдено точное решение.

 

Алгоритм метода наискорейшего спуска

Шаг 0. Задать параметр точности , выбрать х⁰ .

Шаг 1. Найти  и проверить критерий останова: || ||< .

       Если он выполнен, то вычисления завершить, полагая

       x *= x ⁰, f *= f (x ⁰).

Шаг 2. Решить задачу одномерной оптимизации

Ф(α)=f(х⁰- α )  , т.е. найти α *.

       Положить х⁰=х⁰- α* и перейти к шагу 1.

Пример 1.

Решить задачу  методом наискорейшего спуска.

Решение.  

Итерация 1.

0.Зададим x⁰=(4,5).  Выберем =0.01.

1. = (4, 8), || ||> .

2. Решим задачу одномерной минимизации по α:

α*=0.5. х⁰=х⁰- α* =(4-4·0.5, 5-8·0.5)=(2,1).

Итерация 2.

3. =(0,0), || ||=0<  - останов, найдено точное решение.

 

Графическая иллюстрация решения приведена на рисунке. В данном случае линии уровня являются концентрическими окружностями.

 

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

                x ⁰

 

Пример 2. Решить задачу методом наискорейшего спуска.

Решение.

Итерация 1

12. Зададим x⁰=(0.5,1), =0.4.

13. = (3, 2.5), || ||= 3.9 > .

3. Решим задачу одномерной минимизации по α:

Итерация 2.

            4. = (-0.48, 0.58), || ||= 0.752 > .

                                   5. Решим задачу одномерной минимизации.

 

α*=0.546, х⁰=х⁰- α *, = =(0.04, 0.08)                     

Итерация 3.

14. = (-0.24, 0.2), || ||= 0.312 < .

 

Заданная точность достигнута, однако оптимальное решения  за 2 итерации найдено не было. Из графической иллюстрации видно, что линиями уровня в данной задаче являются концентрические эллипсы и получаемые в ходе алгоритма направления не проходят через их центр.

Замечание 1.   Кроме рассмотренных методов выбора шага на практике часто применяются методы с изначально заданным шагом ( например, , где k – номер итерации) и метод выбора шага дроблением по Армихо (см., например, [6] в списке основной литературы, с. 237).

Замечание 2.   Даже для квадратичных функций сходимость градиентных методов за конечное число итераций не гарантирована. Однако если квадратичная функция n переменных приведена к виду суммы полных квадратов, то ее оптимум может быть найден в результате реализации n одномерных поисков по преобразованным координатным направлениям. Процедура преобразования квадратичной функции  к виду суммы полных квадратов эквивалентна нахождению такой матрицы преобразования Q, которая приводит матрицу квадратичной формы к диагональному виду. Таким образом, заданная квадратичная форма  путем преобразования x = zQ приводится к виду = , где D -диагональная матрица. Пусть j - тая строка матрицы Q. Тогда преобразование x= zQ позволяет записать каждый вектор x  в виде линейной комбинации векторов : x= zQ= . Другими словами, осуществляется переход к новой системе координат, задаваемой векторами  (заметим, что это преобразование не является единственным). Таким образом, с помощью преобразования переменных квадратичной функции строится новая система координат, совпадающих с главными осями квадратичной функции. Следовательно, одномерный поиск точки минимума в пространстве преобразованных переменных эквивалентен поиску вдоль каждой из главных осей квадратичной функции. Для полученной системы векторов будут выполняться равенства  

Определение. Система линейно независимых векторов , для которой выполняются равенства , называется системой H-сопряженных направлений.

Итак, если заданы любые n H-сопряженных направлений , то процедура  где =  ,  , позволяет найти минимум квадратичной функции.

Так как достаточно большой класс целевых функций может быть представлен в окрестности точки минимума своей квадратичной аппроксимацией, описанная идея применяется и для неквадратичных функций.

 Построение системы H- сопряженных направлений возможно различными способами. Рассмотрим некоторые из них.