Градиентный спуск — метод нахождения локального минимума (максимума) функции с помощью движения вдоль антиградиента (градиента). Для минимизации функции в направлении градиента используются методы одномерной оптимизации, например, метод золотого сечения. Также можно искать не наилучшую точку в направлении градиента, а какую-либо лучше текущей.
Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода.
Описание[]
Пусть целевая функция имеет вид:
- .
И задача оптимизации задана следующим образом:
Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом :
где выбирается
- постоянной, в этом случае метод может расходиться;
- дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
- наискорейшим спуском:
Алгоритм[]
- Задают начальное приближение и точность расчёта
- Рассчитывают , где
- Проверяют условие останова:
- Если , то и переход к шагу 2.
- Иначе и останов.
Пример[]
Применим градиентный метод к функции . Тогда последовательные приближения будут выглядеть так:
Упомянем, что метод наискорейшего спуска может иметь трудности в патологических случаях овражных функций, так, к примеру, в случае функции Розенброка.
Пример реализации[]
C++[]
//Программа демонстрирует поиск минимума функции нескольких переменных методом наискорейшего спуска
#include <iostream>
#include <cmath>
//Структура вектор
//Содержит количество переменных исходной функции
struct vector
{
double x,y;
};
//Исходная функция
double fx(vector x)
{
return 100*(x.x*x.x+x.y*x.y);
}
//Градиент исходной функции
//Также для нахождения градиента можно использовать численные методы
vector gradient(vector x)
{
vector grad;
grad.x=200*x.x;
grad.y=200*x.y;
return grad;
}
//Вычисление одномерной функции для нахождения шага методом золотого сечения
double MakeSimplefx(double x, vector grad, vector xj)
{
vector buffer;
buffer.x=xj.x-x*grad.x;
buffer.y=xj.y-x*grad.y;
return fx(buffer);
}
//Метод золотого сечения для нахождения шага (lambda)
double GoldenSelection(double a, double b, double eps, vector gradient, vector x)
{
const double fi=1.6180339887;
double x1,x2;
double y1,y2;
x1=b-((b-a)/fi);
x2=a+((b-a)/fi);
y1=MakeSimplefx(x1,gradient,x);
y2=MakeSimplefx(x2,gradient,x);
while (std::abs(b-a)>eps)
{
if (y1<=y2)
{
b=x2;
x2=x1;
x1=b-((b-a)/fi);
y2=y1;
y1=MakeSimplefx(x1,gradient,x);
}
else
{
a=x1;
x1=x2;
x2=a+((b-a)/fi);
y1=y2;
y2=MakeSimplefx(x2,gradient,x);
}
}
return (a+b)/2;
}
//Функция вычисления нового приближения
vector Calculate(vector x, vector gradient, double lambda)
{
vector buffer;
buffer.x=x.x-lambda*gradient.x;
buffer.y=x.y-lambda*gradient.y;
return buffer;
}
//Метод наискорейшего спуска
vector GradDown(vector x, double eps)
{
vector current=x;
vector last;
do
{
last=current; //Запоминаем предыдущее значение
vector grad=gradient(current); //Вычисляем градиент
double lambda=GoldenSelection(0,0.05,eps,grad,current); //Находим шаг вычислений методом золотого сечения
current=Calculate(current,grad,lambda); //Вычисляем новое приближение
}while(std::abs(fx(current)-fx(last))>eps); //Проверяем условие
return current; //Возвращаем результат
}
//Тело главной функции
int main()
{
vector x;
double eps;
std::cout<<"Введите через пробел начальное приближение x и y (например: -1 1): ";
std::cin>>x.x>>x.y;
std::cout<<"\nВведите точность вычислений (например 0.000001): ";
std::cin>>eps;
vector result=GradDown(x,eps);
std::cout<<"\nРезультат: x = "<<result.x<<" y = "<<result.y;
return 0;
};
Ссылки[]
- Mathematics Department at Cal State Fullerton
- Поиск глобального оптимума для задач оптимального проектирования систем или определения оптимальных законов управления.
Литература[]
- Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
- Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
- Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
- Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
- Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
- Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
См. также[]
Градиентные методы
Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Градиентный спуск. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .