Метод градиентного спуска с постоянным шагом

Стратегия решения задачи состоит в построении последовательности точек , k=0, 1, 2, ... n таких, что , Метод градиентного спуска с постоянным шагом - student2.ru k=0,1,2,...n. Точки последовательности вычисляются по правилу: Метод градиентного спуска с постоянным шагом - student2.ru k=0,1,2,...В качестве начала итераций выбирается произвольная точка. Величина шага задается пользователем и остается постоянной до тех пор, пока функция убывает в точках последовательности, т.е. до тех пор, пока выполняется соотношение Метод градиентного спуска с постоянным шагом - student2.ru . Если это условие не выполняется, то производится коррекция длины шага, и опять проверяется выполнение неравенства. Процесс завершается в точке, для которой выполняется условие окончания - Метод градиентного спуска с постоянным шагом - student2.ru .

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

Градиентный спуск — метод нахождения локального минимума функции с помощью движения вдоль градиента. Для минимизации функции в направлении градиента используются методы одномерной оптимизации, например, метод золотого сечения. Стратегия решения задачи состоит в построении такой последовательности точек, что значение функции в каждой последующей точке меньше чем в предыдущей. Точки последовательности вычисляются по правилу Метод градиентного спуска с постоянным шагом - student2.ru где величина шага tk определяется для каждого значения k из условия

Метод градиентного спуска с постоянным шагом - student2.ru .

Аналитическое решение уравнений

Решим заданные уравнения аналитическим способом.

1) Метод градиентного спуска с постоянным шагом - student2.ru

Найдем первые частные производные:

Метод градиентного спуска с постоянным шагом - student2.ru ; Метод градиентного спуска с постоянным шагом - student2.ru

Прировняем полученные производные к нулю и найдем корни системы уравнений:

Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru

Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru

Искомое решение уравнения: Метод градиентного спуска с постоянным шагом - student2.ru ;

Значение функции в найденной точке: Метод градиентного спуска с постоянным шагом - student2.ru

2) Метод градиентного спуска с постоянным шагом - student2.ru

Найдем первые частные производные:

Метод градиентного спуска с постоянным шагом - student2.ru ; Метод градиентного спуска с постоянным шагом - student2.ru

Прировняем полученные производные к нулю и найдем корни уравнения:

Метод градиентного спуска с постоянным шагом - student2.ru
Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru 0 Метод градиентного спуска с постоянным шагом - student2.ru

Искомое решение уравнения: Метод градиентного спуска с постоянным шагом - student2.ru ;

Значение функции в найденной точке: Метод градиентного спуска с постоянным шагом - student2.ru

Исследование работы реализованных методов

Симплекс-метод

Рассмотрим работу программы при различных входных данных.

В качестве рассматриваемой функции выберем

Метод градиентного спуска с постоянным шагом - student2.ru ,

имеющую решение в точке Метод градиентного спуска с постоянным шагом - student2.ru .

Зададим исходные данные:

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,5 0,001

Окно программы при решении симплекс-методом с заданными параметрами – рисунок 3.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 2

Вариации с коэффициентом отражения Метод градиентного спуска с постоянным шагом - student2.ru

Увеличим коэффициент Метод градиентного спуска с постоянным шагом - student2.ru :

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,5 0,001

Решение при новых параметрах – рисунок 4.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 4

Уменьшим коэффициент Метод градиентного спуска с постоянным шагом - student2.ru :

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,5 0,5 0,001

Решение при новых параметрах – рисунок 5.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 5

Вариации с коэффициентом сжатия Метод градиентного спуска с постоянным шагом - student2.ru

Восстановим исходные параметры – рисунок 3.

Зададим коэффициент сжатия Метод градиентного спуска с постоянным шагом - student2.ru и повторим расчет.

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,8 0,001

Решение при новых параметрах – рисунок 6.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 6

Уменьшим коэффициент сжатия Метод градиентного спуска с постоянным шагом - student2.ru :

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,2 0,001

Решение при новых параметрах – рисунок 7.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 7

Вариации с коэффициентом растяжения Метод градиентного спуска с постоянным шагом - student2.ru

Восстановим исходные параметры – рисунок 3.

Зададим коэффициент растяжения Метод градиентного спуска с постоянным шагом - student2.ru и повторим расчет.

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,5 3,5 0,001

Решение при новых параметрах – рисунок 8.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 8

Уменьшим коэффициент растяжения Метод градиентного спуска с постоянным шагом - student2.ru :

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,5 2,5 0,001

Решение при новых параметрах – рисунок 9.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 9

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

1) Задать коэффициент отражения в диапазоне [1; 2];

2) Задать коэффициент сжатия в диапазоне [0,5; 0,9];

3) Задать коэффициент растяжения в диапазоне [1; 1,9];

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

1) Задать коэффициент отражения в диапазоне [0,8; 1];

2) Задать коэффициент сжатия в диапазоне [0,5; 0,8];

3) Задать коэффициент растяжения в диапазоне [1,8; 2;9]

.

В качестве рассматриваемой функции выберем

Метод градиентного спуска с постоянным шагом - student2.ru ,

имеющую решение в точке Метод градиентного спуска с постоянным шагом - student2.ru .

Зададим исходные данные:

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,5 0,001

Окно программы при решении симплекс-методом с заданными параметрами – рисунок 10.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 10

Вариации с коэффициентом отражения Метод градиентного спуска с постоянным шагом - student2.ru

Увеличим коэффициент Метод градиентного спуска с постоянным шагом - student2.ru :

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,5 0,001

Решение при новых параметрах – рисунок 11.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 11

Уменьшим коэффициент Метод градиентного спуска с постоянным шагом - student2.ru :

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,5 0,5 0,001

Решение при новых параметрах – рисунок 12.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 12

Вариации с коэффициентом сжатия Метод градиентного спуска с постоянным шагом - student2.ru

Восстановим исходные параметры – рисунок 10.

Зададим коэффициент сжатия Метод градиентного спуска с постоянным шагом - student2.ru и повторим расчет.

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,8 0,001

Решение при новых параметрах – рисунок 13.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 13

Уменьшим коэффициент сжатия Метод градиентного спуска с постоянным шагом - student2.ru :

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,2 0,001

Решение при новых параметрах – рисунок 14.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 14

Вариации с коэффициентом растяжения Метод градиентного спуска с постоянным шагом - student2.ru

Восстановим исходные параметры – рисунок 10.

Зададим коэффициент растяжения Метод градиентного спуска с постоянным шагом - student2.ru и повторим расчет.

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,5 3,5 0,001

Решение при новых параметрах – рисунок 15.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 15

Уменьшим коэффициент растяжения Метод градиентного спуска с постоянным шагом - student2.ru :

A B C Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru Метод градиентного спуска с постоянным шагом - student2.ru N
(9; 9) (6; 8) (9; 6) 0,5 2,5 0,001

Решение при новых параметрах – рисунок 16.

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 16

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

1) Задать коэффициент отражения в диапазоне [0,5; 1];

2) Задать коэффициент сжатия в диапазоне [0,5; 0,9];

3) Задать коэффициент растяжения в диапазоне [2,5; 3].

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

1) Задать коэффициент отражения в диапазоне [0,8; 1];

2) Задать коэффициент сжатия в диапазоне [0,1; 0,7];

3) Задать коэффициент растяжения в диапазоне [2; 3,4].

Если необходимо добиться максимальной точности от данного метода, то требуется в дополнение к условиям получения наиболее точного решения, которые описаны выше, добавить ещё одно – задать максимально маленьким число Метод градиентного спуска с постоянным шагом - student2.ru для остановки алгоритма.

1) При Метод градиентного спуска с постоянным шагом - student2.ru для функции Метод градиентного спуска с постоянным шагом - student2.ru получим результат (рисунок 17)

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 17

2) При Метод градиентного спуска с постоянным шагом - student2.ru для функции Метод градиентного спуска с постоянным шагом - student2.ru получим результат (рисунок 18).

Метод градиентного спуска с постоянным шагом - student2.ru

Рисунок 18


Наши рекомендации