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

Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода.

Описание

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

Пусть целевая функция имеет вид:

.

И задача оптимизации задана следующим образом:

Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом :

где выбирается

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

Алгоритм

  1. Задают начальное приближение и точность расчёта
  2. Рассчитывают , где
  3. Проверяют условие останова:
    • Если , то и переход к шагу 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;
};

Ссылки

Литература

  1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
  1. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
  1. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
  1. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
  1. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
  1. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.


См. также

Градиентные методы


Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Градиентный спуск. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .


Материалы сообщества доступны в соответствии с условиями лицензии CC-BY-SA, если не указано иное.