Градиентный спуск
[ HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA&action=edit&section=0" \o "Править секцию: 0" править]
Материал из Википедии — свободной энциклопедии
HYPERLINK "http://ru.wikipedia.org/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9F%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B0_%D1%81%D1%82%D0%B0%D1%82%D0%B5%D0%B9/%D0%9F%D0%BE%D1%8F%D1%81%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B4%D0%BB%D1%8F_%D1%87%D0%B8%D1%82%D0%B0%D1%82%D0%B5%D0%BB%D0%B5%D0%B9" \o "Википедия:Проверка статей/Пояснение для читателей" Текущая версия (не проверялась)
Перейти к: HYPERLINK "http://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA" \l "column-one#column-one" навигация, HYPERLINK "http://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA" \l "searchInput#searchInput" поиск
Градиентный спуск — HYPERLINK "http://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B" \o "Градиентные методы" метод нахождения локального HYPERLINK "http://ru.wikipedia.org/wiki/%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D1%83%D0%BC" \o "Минимум" минимума ( HYPERLINK "http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D1%83%D0%BC" \o "Максимум" максимума) HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BB%D0%B5%D0%B2%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F" \o "Целевая функция" функции с помощью движения вдоль HYPERLINK "http://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82" \o "Градиент" градиента. Для минимизации функции в направлении градиента используются HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BE%D0%B4%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B9_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8&action=edit&redlink=1" \o "Методы одномерной оптимизации (страница отсутствует)" методы одномерной оптимизации, например, HYPERLINK "http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B7%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B3%D0%BE_%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D1%8F" \o "Метод золотого сечения" метод золотого сечения. Также можно искать не наилучшую точку в направлении градиента, а какую-либо лучше текущей.
HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A1%D1%85%D0%BE%D0%B4%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C" \o "Сходимость" Сходимость метода градиентного спуска зависит от отношения максимального и минимального HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D0%B1%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0" \o "Собственные числа" собственных чисел HYPERLINK "http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D1%81%D1%81%D0%B8%D0%B0%D0%BD_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8" \o "Гессиан функции" матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода.
[ HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA&action=edit&section=1" \o "Править секцию: Описание" править] Описание
HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Gradient_descent.png" INCLUDEPICTURE "http://upload.wikimedia.org/wikipedia/commons/thumb/7/79/Gradient_descent.png/400px-Gradient_descent.png" \* MERGEFORMATINET 
HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Gradient_descent.png" \o "Увеличить" INCLUDEPICTURE "http://bits.wikimedia.org/skins-1.5/common/images/magnify-clip.png" \* MERGEFORMATINET 
Иллюстрация последовательных приближений к точке экстремума в направлении наискорейшего спуска (красн.) в случае дробного шага. Синим отмечены HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%9B%D0%B8%D0%BD%D0%B8%D0%B8_%D1%83%D1%80%D0%BE%D0%B2%D0%BD%D1%8F&action=edit&redlink=1" \o "Линии уровня (страница отсутствует)" линии уровня.
Пусть HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BB%D0%B5%D0%B2%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F" \o "Целевая функция" целевая функция имеет вид:
INCLUDEPICTURE "http://upload.wikimedia.org/math/2/4/2/242a143ddcc39a988dda4e212b19d959.png" \* MERGEFORMATINET .
И HYPERLINK "http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8" \o "Задача оптимизации" задача оптимизации задана следующим образом:
INCLUDEPICTURE "http://upload.wikimedia.org/math/5/8/e/58e303468dcc0c0abe46be830a13fa78.png" \* MERGEFORMATINET
Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся анти HYPERLINK "http://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82" \o "Градиент" градиентом INCLUDEPICTURE "http://upload.wikimedia.org/math/d/1/3/d13b66b6bbd2732f199b1cbcc9402077.png" \* MERGEFORMATINET :
INCLUDEPICTURE "http://upload.wikimedia.org/math/9/9/5/995db8c1d4c6a934a121ac5fbcf522a0.png" \* MERGEFORMATINET
где ?[j] выбирается
постоянной, в этом случае метод может расходиться;
дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
наискорейшим спуском: INCLUDEPICTURE "http://upload.wikimedia.org/math/5/e/b/5eb20f0743d8433839751da0aeeed0a8.png" \* MERGEFORMATINET
[ HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA&action=edit&section=2" \o "Править секцию: Алгоритм" править] Алгоритм
Задают начальное приближение и точность расчёта INCLUDEPICTURE "http://upload.wikimedia.org/math/2/3/2/232457a8b512d2a1a8a2837f58d5b4c9.png" \* MERGEFORMATINET
Рассчитывают INCLUDEPICTURE "http://upload.wikimedia.org/math/9/9/5/995db8c1d4c6a934a121ac5fbcf522a0.png" \* MERGEFORMATINET , где INCLUDEPICTURE "http://upload.wikimedia.org/math/5/e/b/5eb20f0743d8433839751da0aeeed0a8.png" \* MERGEFORMATINET
Проверяют условие остановки:
Если INCLUDEPICTURE "http://upload.wikimedia.org/math/0/7/5/07573eb00648bfca89650dc2f01cc4be.png" \* MERGEFORMATINET , то j = j + 1 и переход к шагу 2.
Иначе INCLUDEPICTURE "http://upload.wikimedia.org/math/d/d/d/dddd2f43b0e579cc1c43cea783f73684.png" \* MERGEFORMATINET и останов.
[ HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA&action=edit&section=3" \o "Править секцию: Пример" править] Пример
Применим градиентный метод к функции INCLUDEPICTURE "http://upload.wikimedia.org/math/d/9/7/d97e3d082b0ff632b82a287a8413d73e.png" \* MERGEFORMATINET . Тогда последовательные приближения будут выглядеть так:
HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Gradient_ascent_(contour).png" \o "Градиентный метод в действии. Иллюстрация для линий равного уровня." INCLUDEPICTURE "http://upload.wikimedia.org/wikipedia/commons/thumb/d/db/Gradient_ascent_%28contour%29.png/350px-Gradient_ascent_%28contour%29.png" \* MERGEFORMATINET  HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Gradient_ascent_(surface).png" \o "Градиентный метод в действии. Иллюстрация для поверхности." INCLUDEPICTURE "http://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Gradient_ascent_%28surface%29.png/450px-Gradient_ascent_%28surface%29.png" \* MERGEFORMATINET 
Упомянем, что метод наискорейшего спуска может иметь трудности в патологических случаях HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%9E%D0%B2%D1%80%D0%B0%D0%B6%D0%BD%D1%8B%D0%B5_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8&action=edit&redlink=1" \o "Овражные функции (страница отсутствует)" овражных функций, так, к примеру, в случае HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%A0%D0%BE%D0%B7%D0%B5%D0%BD%D0%B1%D1%80%D0%BE%D0%BA%D0%B0&action=edit&redlink=1" \o "Функция Розенброка (страница отсутствует)" функции Розенброка.
[ HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA&action=edit&section=4" \o "Править секцию: Пример реализации" править] Пример реализации
[ HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA&action=edit&section=5" \o "Править секцию: C++" править] C++
#include <vector>
#include <iostream>
#include <math.h>
#include <string>
#include <sstream>

using namespace std;

typedef vector<double> DataList;

void InitData();
void GradSearch(DataList &p, double sigma,double epsilon);
void QMin(DataList &de_dxi, DataList &p, double epsilon, double sigma);
void getDfDx(DataList &de_dxi, DataList &p);
string CreateResultString(DataList &pMin,double yMin);
double getFunc(DataList &p);
string stringify(double x);

DataList p1;
DataList p2;
DataList pMin;
DataList de_dxi;

double yMin;
double err;
double z0;
double h;
int N;

int j;

int main()
{
N = 2;

InitData();

DataList p;
p.push_back(0.99);
p.push_back(1.01);
double sigma = 0.0000000001;
double epsilon = 0.0000000001;

GradSearch(p, sigma, epsilon);

return 0;
}

void GradSearch(DataList &p, double sigma,double epsilon)
{
int max = 60;
h = 1;
err = 1;
int count = 0;

while(count < max && (h>sigma ||err > epsilon))
{
getDfDx(de_dxi, p);
QMin(de_dxi, p, epsilon, sigma);

for(int i = 0; i<N; i++)
p.at(i) = pMin.at(i);

z0 = yMin;
count = count + j + 1;

string iterResult = CreateResultString(pMin, yMin);

cout<<CreateResultString(pMin, yMin)<<endl;
}
cout<<endl<<"Минимум функции: "<<"-4*x + x*x - y - x*y + y*y"<<endl;
cout<<CreateResultString(pMin, yMin)<<endl;
}

void QMin(DataList &de_dxi,DataList &p, double epsilon, double sigma)
{
int cond = 0;
int jmax = 60;

z0 = getFunc(p);

for(int i = 0; i<N; i++)
p1.at(i) = p.at(i) + h * de_dxi.at(i);

double y1 = getFunc(p1);

for(int i = 0; i<N; i++)
p2.at(i) = p.at(i) + 2 * h * de_dxi.at(i);

double y2 = getFunc(p2);

j = 0;

while (j<jmax && cond == 0)
{
if (z0<=y1)
{
for(int i = 0; i<N; i++)
p2.at(i) = p1.at(i);

y2 = y1;
h = h / 2;

for(int i = 0; i<N; i++)
p1.at(i) = p.at(i) + h * de_dxi.at(i);

y1 = getFunc(p1);
}
else if (y2 < y1)
{
for(int i = 0; i<N; i++)
p1.at(i) = p2.at(i);

y1 = y2;

h = h*2;

for(int i = 0; i<N; i++)
p2.at(i) = p.at(i) + 2 * h * de_dxi.at(i);

y2 = getFunc(p2);
}
else
{
cond = -1;
}

j = j+1;
if (h < sigma)
cond = 1;
}

double hMin = (h/2)* (4 * y1 - 3* z0 - y2) / (2* y1 - z0 - y2);

for (int i = 0; i< N; i++)
{
pMin.at(i) = p.at(i) + hMin * de_dxi.at(i);
}

yMin = getFunc(pMin);

double h0 = fabs(hMin);
double h1 = fabs(hMin - h);
double h2 = fabs(hMin - 2* h);

if (h0 < h)
h = h0;
if (h1 < h)
h = h1;
if (h2 < h)
h = h2;
if (h == 0)
h = hMin;
if (h < sigma)
cond = 1;
double e0 = fabs(z0 - yMin);
double e1 = fabs(y1 - yMin);
double e2 = fabs(y2 - yMin);

if (e0 != 0 && e0 < err)
err = e0;
if (e1 != 0 && e1 < err)
err = e1;
if (e2 != 0 && e2 < err)
err = e2;
if (e0 == 0 && e1 == 0 && e2 == 0)
err = 0;
if (err < epsilon)
cond = 2;
}

double getFunc(DataList &p)
{
double x = p.at(0);
double y = p.at(1);

double result = -4 * x + x*x - y - x * y + y * y;

return result;
}

void getDfDx(DataList & de_dxi, DataList &p)
{
double x = p.at(0);
double y = p.at(1);


double dfDx = -4+2*x-y;
double dfDy = -1-x+2*y;

double norm = sqrt(dfDx*dfDx + dfDy*dfDy);

dfDx = -dfDx/norm;
dfDy = -dfDy/norm;

de_dxi.at(0) = dfDx;
de_dxi.at(1) = dfDy;
}

void InitData()
{
for(int i = 0; i<N; i++)
{
p1.push_back(0);

p2.push_back(0);

pMin.push_back(0);

de_dxi.push_back(0);
}
}

string stringify(double x)
{
ostringstream o;
if (!(o << x))
return 0;
return o.str();
}

string CreateResultString(DataList &pMin,double yMin)
{
string resultStr = "f[";

for(int i = 0; i<N; i++)
{
if (i != 0)
resultStr += ",";
resultStr += stringify(pMin.at(i));
}

resultStr += "] = " + stringify(yMin);

return resultStr;
}
[ HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA&action=edit&section=6" \o "Править секцию: Ссылки" править] Ссылки
J. Mathews. HYPERLINK "http://math.fullerton.edu/mathews/n2003/GradientSearchMod.html" Module for Steepest Descent or Gradient Method.
[ HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA&action=edit&section=7" \o "Править секцию: Литература" править] Литература
Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.