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

[Alcohol_frei]

Доброе время суток!
Возможно, обращаюсь не по адресу, но как мне сказали сабжевый метод используется в вычислительной математике, я уже пару учебников проштудировал, но мало что понял.
Собственно, вопрос:
Пишу задание по летней практике, сам программист. Выдали тему "Сравнение методов поиска" и мне подтему "Градиентный спуск".
После прочтения доступной литературы я был удивлен многообразием различных применений данного метода и теперь теряюсь в догадках, что же именно мне в программе реализовать.
Используется и для определения координат точки, и для решения систем уравнений, в общем я в панике.
Просьба к знающим людям, вкратце объясните доступно в чем заключается данный метод (а то от общих рассуждений голова уже пухнет) и, если таковые имеются, алгоритмы, на псевдокоде хотя бы или примеры.
Спасибо заранее.

[PAV]

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

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

[Brukvalub]

Alcohol_frei писал(а):

Пишу задание по летней практике, сам программист. Выдали тему "Сравнение методов поиска" и мне подтему "Градиентный спуск".
После прочтения доступной литературы я был удивлен многообразием различных применений данного метода и теперь теряюсь в догадках, что же именно мне в программе реализовать.

Я бы сходил к руководителю практики и уточнил, какой имено алгоритм требуется реализовать. Мы-то про конкретику Вашей задачи знаем еще меньше Вашего

[ewert]

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

Непосредственная цель метода -- научиться находить минимум функции $F(\vec x)\equiv F(x_1,x_2,\dots,x_n)$ функции нескольких переменных. Берём некоторую точку $\vec x_0\equiv(x_{01},x_{02},\dots,x_{0n})$ в качестве начального приближения. И рассматриваем вспомогательную функцию одного переменного $\Phi(t)\equiv F(\vec x_0-t\cdot\vec\nabla F(\vec x_0))$ (здесь $\vec\nabla F(\vec x)$ -- это именно градиент, т.е. с ростом $t$ именно против него и сдвигаемся). И подбираем $t\equiv t_0$ так, чтобы эта самая $\Phi(t)$ приняла минимальное значение, после чего берём $x_1\equiv \vec x_0-t\cdot\vec\nabla F(\vec x_0)$. А потом зацикливаем: на каждом шаге $t\equiv t_k$ -- точка минимума и $x_{k+1}\equiv \vec x_k-t\cdot\vec\nabla F(\vec x_k)$.

Метод хорош своей надёжностью: на каждом шагу мы хоть чуть-чуть, да опускаемся, и при довольно широких условиях достижение минимума в пределе гарантировано. А плох своей трудоёмкостью. Мало того, что сходится со скоростью лишь геометрической прогрессии (тут уж ничего не поделаешь -- если с этим бороться, то потеряется универсальность). Но и даже поиск одномерного экстремума -- тоже, в общем, морока. Поэтому обычно метод модифицируют, добиваясь на каждом шаге не точной, а хоть какой-нибудь минимизации (общая скорость сходимости от этого не шибко страдает).

Ну и отдельная песня -- овражистые функции, там этот метод практически отказывает; но там откажут и вообще любые (неспециализированные) методы.

[Brukvalub]

ewert писал(а):

А потом зацикливаем...

Разве в алгоритмах не оговаривают условие остановки вычислений?

[ewert]

Brukvalub писал(а):

ewert писал(а):

А потом зацикливаем...

Разве в алгоритмах не оговаривают условие остановки вычислений?

хуже того: эти условия настолько подразумеваются автоматом, что о них не принято даже особо так задумываться.

Пусть иногда и напрасно.

А вот только сейчас припомнил: настолько не принято, что выжать из студента хоть какое-нибудь хоть сколько-то правдоподобное условие -- зачастую проблема...

[Brukvalub]

ewert писал(а):

А вот только сейчас припомнил: настолько не принято, что выжать из студента хоть какое-нибудь хоть сколько-то правдоподобное условие -- зачастую проблема...

Так сейчас мы получаем наглядный пример того, что не только студенты эти условия не пишут....

[ewert]

а Вы попробуйте выписать практически универсальное условие, а потом ехидничайте

[Brukvalub]

ewert писал(а):

а Вы попробуйте выписать практически универсальное условие, а потом ехидничайте

И не буду пытаться. Я попробовал дать более разумный совет:

Brukvalub писал(а):

Я бы сходил к руководителю практики и уточнил, какой имено алгоритм требуется реализовать. Мы-то про конкретику Вашей задачи знаем еще меньше Вашего

[ewert]

А руководитель заранее уточнил, и вполне конкретно: "дать обзор".

[Alcohol_frei]

Спасибо большое за развернутые ответы. Кажется, задача немного прояснилась.
К руководителю и так завтра собирался ехать, впопыхах когда брал задание ничего не спросил.
Посмотрим что он скажет.

Цитата:

А руководитель заранее уточнил, и вполне конкретно: "дать обзор".

Дело в том что "дать обзор" применительно к программе как-то ни к селу ни к городу.

[ewert]

Alcohol_frei писал(а):

Спасибо большое за развернутые ответы. Кажется, задача немного прояснилась.
К руководителю и так завтра собирался ехать, впопыхах когда брал задание ничего не спросил.
Посмотрим что он скажет.

Цитата:

А руководитель заранее уточнил, и вполне конкретно: "дать обзор".

Дело в том что "дать обзор" применительно к программе как-то ни к селу ни к городу.

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

Подход сугубо эмпирический, но -- вполне содержателен.

[Alcohol_frei]

Спасибо всем ответившим, хочу уточнить последний раз.
(задание узнал, оно стандартно - найти минимум и максимум функции)
Функция n переменных.
1. Берем любую точку X0 с n координатами и вычисляем в ней значение функции.
2. Находим частные производные функции (градиент в общем виде)
3. Подставляем в градиент значения X0.
4. Вычисляем новые координаты точки (разность между начальным значением и значением соотв. координаты в векторе градиента)
5. Вычисляем значение функции в полученной точке.
6. Сравниваем предыдущее и полученное значение, учитывая погрешность. Если разница меньше погрешности, останавливаемся. Если нет, то переходим к п. 3
Так?
Если все верно, единственная проблема - запрограммировать нахождение производных.

[Бодигрим]

ewert в сообщении #130687 писал(а):

а Вы попробуйте выписать практически универсальное условие, а потом ехидничайте

Нам на парах давали что-то в духе $\max\{ |x_n-x_{n-1}|, |f(x_n)-f(x_{n-1})|, |\grad f(x_n)|\}<\varepsilon$.

Добавлено спустя 10 минут 45 секунд:

Alcohol_frei в сообщении #143262 писал(а):

2. Находим частные производные функции (градиент в общем виде)

3. Подставляем в градиент значения X0.

На практике, когда исходная функция не задана в аналитической форме, - это единый шаг: численное нахождение производной в точке. ИМХО в учебной задаче так делать "честнее".

Alcohol_frei в сообщении #143262 писал(а):

4. Вычисляем новые координаты точки (разность между начальным значением и значением соотв. координаты в векторе градиента)

Нет, не так. Следующая точка находится как экстремум функции $f$ на прямой, проходящей через предыдущую точку и параллельной градиенту. Для этого пишется отдельная подпрограмма одномерной оптимизации. Впрочем, вам про это уже сказали выше. Там свои методы, можете ознакомиться в любом учебнике или в Википедии.[quote="Alcohol_frei
сообщении #143262"]Сравниваем предыдущее и полученное значение, учитывая погрешность.[/quote]
Проверять $|x_n-x_{n-1}|<\varepsilon$ недостаточно для хорошего результата алгоритма. Дело в том, что если у вас на некотором шаге перемещение было малым, на следующем оно может быть снова очень и очень большим. ИМХО лучше делать, как я писал выше.

[ewert]

Бодигрим писал(а):

ewert в сообщении #130687 писал(а):

а Вы попробуйте выписать практически универсальное условие, а потом ехидничайте

Нам на парах давали что-то в духе $\max\{ |x_n-x_{n-1}|, |f(x_n)-f(x_{n-1})|, |\grad f(x_n)|\}<\varepsilon$.

. . . . . . . . . . . . . . . . .

[quote="Alcohol_frei
сообщении #143262"]Сравниваем предыдущее и полученное значение, учитывая погрешность.

Проверять $|x_n-x_{n-1}|<\varepsilon$ недостаточно для хорошего результата алгоритма. Дело в том, что если у вас на некотором шаге перемещение было малым, на следующем оно может быть снова очень и очень большим. ИМХО лучше делать, как я писал выше.[/quote]
Так Ваш вышний рецепт как раз именно от этой-то проблемы и не спасает ( не говоря уж о том, что и выглядит странно -- совсем разного типа величины почему-то сравниваются с одной и той же; впрочем, это, видимо, из-за "что-то в духе").

Фактически достаточно отслеживать только $|x_n-x_{n-1}|$, но -- обязательно беря максимум по некоторой группе последних приближений. Например, по $n$ последним, где $n$ -- размерность задачи (после каждых $n$ шагов условия сходимости более-менее повторяются).

Но и это ещё не всё. Метод градиентного сходится спуска (усреднённо) со скоростью геометрической прогрессии, т.е. усреднённые разности соседних приближений убывают примерно как $q^n$. Беда в том, что $q$ запросто может оказаться очень близкой к единице (величина $(1-q)$ оценивается через отношение минимального и максимального собственных чисел матрицы вторых производных в окрестности экстремума). Поэтому сравнивать надо не просто с $\varepsilon$, а с $\varepsilon\cdot(1-q)$, т.е. с некоторым запасом. Причём на практике величина $q$ тоже неизвестна, и её нужно оценивать по мере вычислений через усреднённые отношения усреднённых же приращений.