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

[netang]

Здравствуйте. Мне нужно реализовать метод дробления шага для нахождения минимума двух функций. Я нашел информацию по методу градиентного спуска с дроблением шага, но я не уверен что это то, что мне нужно. Где можно почитать про этот метод? В чем суть метода?

[bot]

(Оффтоп)

netang в сообщении #951935 писал(а):

Мне нужно реализовать метод дробления шага для нахождения минимума двух функций.

Значица так. Дробим шаг пополам. На первой половине шага ищем минимум одной функции, а на второй - другой.

[netang]

Цитата:

для нахождения минимума двух функций

Вернее будет так: для нахождения минимума функции двух переменных

[bot]

Суть в том, что градиент указывает направление наибольшего возрастания. Если ищешь минимум - ходи против градиента. Проблема лишь в том, какими шагами ходить. От этого зависит (в конкретных условиях), как долго ходить и не будет ли это пустою забавою. Описания есть везде. Вот, к примеру
http://www.machinelearning.ru/wiki/inde ... 0.B3.D0.B0

[netang]

Спасибо, стало яснее Пойду попробую реализовать это дело

[netang]

Оставлю здесь. Может кому-нибудь пригодится.

#include <iostream>
using namespace std;
double f(double x, double y)
{
   return 3*x*x-6*x*y+4*y*y+12*x-18*y+21;
}
double gradX(double x, double y)
{
   return 6*x-6*y+12;
}
double gradY(double x, double y)
{
   return -6*x+8*y-18;
}
int main()
{
   double L = 1.0;
   double x = 4, y = -4;
   while(L > 0.005)
   {
      if( f(x - L*gradX(x, y), y - L*gradY(x, y)) <= (f(x, y) - 0.5*L*(gradX(x, y)*gradX(x, y) + gradY(x, y)*gradY(x, y))) )
      {
         x = x - L*gradX(x, y);
         y = y - L*gradY(x, y);
      }
      else
      {
         L = L * 0.5;
      }
   }
   cout << x << "   "  << y << endl;
   return 0;
}

[B@R5uk]

Очень нерационально производятся вычисления: по нескольку раз одно и то же считается. Компилятор может быть и соптимизирует, а может и нет. Лучше сразу сделать хорошо:

#include <iostream>
using namespace std;
double f(double x, double y)
{
   return 3*x*x-6*x*y+4*y*y+12*x-18*y+21;
}
double gradX(double x, double y)
{
   return 6*x-6*y+12;
}
double gradY(double x, double y)
{
   return -6*x+8*y-18;
}
int main()
{
   double L = 1.0;
   double x = 4, y = -4;
   double fv = f(x, y);
   while(L > 0.005)
   {
      double gx = gradX(x, y);
      double gy = gradY(x, y);
      double nx = x - L*gx;
      double ny = y - L*gy;
      double nf = f(nx, ny);
      if( nf <= (fv - 0.5*L*(gx*gx + gy*gy)) )
      {
         x = nx;
         y = ny;
         fv = nf;
      }
      else
      {
         L = L * 0.5;
      }
   }
   cout << x << "   "  << y << endl;
   return 0;
}

За одно и понятнее стало, что происходит. Можно и дальше соптимизировать: переносить в следующую итерацию старое значение функции, чтобы не считать его лишний раз. Не удержался, сделал сам. Это особенно полезно, если сама функция вычисляется неявным образом с помощью численной процедуры.

[netang]

Цитата:

Очень нерационально производятся вычисления

Я понимаю что гораздо лучше gradX(x, y) вычислить один раз (в каждом цикле) и занести данные в переменную, но я специально так написал, чтобы было наглядней как в формуле. Когда делал, я не гнался за оптимальностью, но с Вами полностью согласен.