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

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

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

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

.

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

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

1)

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

;

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

Искомое решение уравнения: ;

Значение функции в найденной точке:

2)

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

;

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

0

Искомое решение уравнения: ;

Значение функции в найденной точке:

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

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

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

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

,

имеющую решение в точке .

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

A	B	C					N
(9; 9)	(6; 8)	(9; 6)		0,5		0,001

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

Рисунок 2

Вариации с коэффициентом отражения

Увеличим коэффициент :

A	B	C					N
(9; 9)	(6; 8)	(9; 6)		0,5		0,001

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

Рисунок 4

Уменьшим коэффициент :

A	B	C					N
(9; 9)	(6; 8)	(9; 6)	0,5	0,5		0,001

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

Рисунок 5

Вариации с коэффициентом сжатия

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

Зададим коэффициент сжатия и повторим расчет.

A	B	C					N
(9; 9)	(6; 8)	(9; 6)		0,8		0,001

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

Рисунок 6

Уменьшим коэффициент сжатия :

A	B	C					N
(9; 9)	(6; 8)	(9; 6)		0,2		0,001

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

Рисунок 7

Вариации с коэффициентом растяжения

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

Зададим коэффициент растяжения и повторим расчет.

A	B	C					N
(9; 9)	(6; 8)	(9; 6)		0,5	3,5	0,001

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

Рисунок 8

Уменьшим коэффициент растяжения :

A	B	C					N
(9; 9)	(6; 8)	(9; 6)		0,5	2,5	0,001

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

Рисунок 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]

.

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

,

имеющую решение в точке .

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

A	B	C					N
(9; 9)	(6; 8)	(9; 6)		0,5		0,001

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

Рисунок 10

Вариации с коэффициентом отражения

Увеличим коэффициент :

A	B	C					N
(9; 9)	(6; 8)	(9; 6)		0,5		0,001

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

Рисунок 11

Уменьшим коэффициент :

A	B	C					N
(9; 9)	(6; 8)	(9; 6)	0,5	0,5		0,001

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

Рисунок 12

Вариации с коэффициентом сжатия

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

Зададим коэффициент сжатия и повторим расчет.

A	B	C					N
(9; 9)	(6; 8)	(9; 6)		0,8		0,001

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

Рисунок 13

Уменьшим коэффициент сжатия :

A	B	C					N
(9; 9)	(6; 8)	(9; 6)		0,2		0,001

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

Рисунок 14

Вариации с коэффициентом растяжения

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

Зададим коэффициент растяжения и повторим расчет.

A	B	C					N
(9; 9)	(6; 8)	(9; 6)		0,5	3,5	0,001

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

Рисунок 15

Уменьшим коэффициент растяжения :

A	B	C					N
(9; 9)	(6; 8)	(9; 6)		0,5	2,5	0,001

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

Рисунок 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].

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

1) При для функции получим результат (рисунок 17)

Рисунок 17

2) При для функции получим результат (рисунок 18).

Рисунок 18