2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему
 
 Шаг в методе наименьшего спуска
Сообщение06.08.2015, 17:24 


23/04/15
64
Добрый день!

В градиентном методе оптимизации наискорейшего спуска необходимо при каждой итерации выбирать шаг. Шаг - это безразмерный параметр, пропорционально которому мы сдвигаемся от текущей точки вдоль градиента. Нужно выяснить где первая производная целевой функции от безразмерного параметра равна нулю.
Однако моя программа так устроена, что система не может найти производную аналитически.

На странице http://futurewings.ru/works_lectures/1.htm описан практический пример использования - "Метод Коши (наискорейшего спуска или крутого восхождения)." Там есть формула для шага $h$ на $k$-ом шаге (**), и даже конкретный пример. Кто знает, где выводится эта формула с матрицей Гессе? Получается, что это ответ для шага, где производная равна нулю?
Спасибо.

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение06.08.2015, 18:00 
Заслуженный участник
Аватара пользователя


11/04/08
2531
Физтех
Пусть дана скалярная функция $f(x)$ нескольких переменных и точка $x_k$. Вектором $e_k$ будем обозначать направление вдоль градиента функции $f(x)$ в точке $x_k$. Ставится задача поиска шага $h$ такого, чтобы $$g(h) \equiv f(x_k + h \cdot e_k) \to \min.$$ Причем $h$ -- это скалярная переменная, а $g(h)$ -- скалярная функция одной переменной. Остается написать $g'(h)=0$ и найти отсюда $h$. На сайте формула неправильная, потому что в знаменателе вектор стоит, а должно число. Решите самостоятельно уравнение $g'(h)=0$ и получите верный ответ, это легко сделать.

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение07.08.2015, 09:23 


23/04/15
64
ShMaxG в сообщении #1043111 писал(а):
. На сайте формула неправильная, потому что в знаменателе вектор стоит, а должно число. Решите самостоятельно уравнение $g'(h)=0$ и получите верный ответ, это легко сделать.


Почему? Там же в самом примере матрица Гессе умножается слева и справа на строку и столбец соответственно и получается число. Разве что формула непонятно написана.

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение07.08.2015, 10:20 
Заслуженный участник
Аватара пользователя


11/04/08
2531
Физтех
Pumpov в сообщении #1043203 писал(а):
Разве что формула непонятно написана.

Ну так я про формулу и говорю, пример не смотрел.

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение07.08.2015, 14:06 


23/04/15
64
ShMaxG в сообщении #1043217 писал(а):
Pumpov в сообщении #1043203 писал(а):
Разве что формула непонятно написана.

Ну так я про формулу и говорю, пример не смотрел.


Из примера можно понять, какова формула в нормальной записи. Вот она верна? Откуда может быть получена?

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение07.08.2015, 16:03 
Заслуженный участник
Аватара пользователя


11/04/08
2531
Физтех
Pumpov в сообщении #1043274 писал(а):
Из примера можно понять, какова формула в нормальной записи. Вот она верна?

Не знаю какая там формула в примере, но если в формуле выше в знаменателе справа добавить вектор направления ($S^k$ который), то будет правильная.

Pumpov в сообщении #1043274 писал(а):
Откуда может быть получена?

Я вам ответил, откуда она получается. Раскладывайте $f(x_k+h\cdot e_k)$ по степеням $h$ до второго порядка включительно, дифференцируйте, приравнивайте нулю и выражайте $h$.

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение07.08.2015, 16:19 
Заслуженный участник


16/02/13
3538
Владивосток
Pumpov в сообщении #1043101 писал(а):
Кто знает, где выводится эта формула с матрицей Гессе?
Вы там ничего не напутали? Матрица Гессе относится к методу Ньютона, не к наискорейшему спуску. Вы в стартовом сообщении смешали два метода, а в названии темы написали вообще ерунду какую-то. Почему б вам не исправить как-то эту путаницу? Вроде б, ТС может править тему, не?

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение09.08.2015, 09:21 
Заслуженный участник
Аватара пользователя


11/03/08
6776
Москва
Формула, обозначенная по ссылке (**), правильная, но практически непригодная. Она показывает, что существует оптимальный шаг, и его можно даже найти, если знать матрицу Гессе. Но если мы её, МГ, знаем, то может воспользоваться методом Ньютона. То есть формула исключительно для "доказательства существования", а не для вычислений по ней.
Метод Коши (как и метод градиента) используется там, где вторые производные вычислить либо вовсе невозможно, либо слишком дорого, а первые производные нам доступны. Обычно их вычисление всё же существенно дороже, чем вычисление функции в точке, что и объясняет преимущество метода Коши над градиентным поиском. Найдя направление, рассматривают шаг h, как новый параметр оптимизации (одномерной) функции $f(x+hg)$, где x - точка, в которой искали градиент, g - градиент в этой точке. Оптимум по h ищут численно, используя, например, метод золотого сечения или же квадратичную оптимизацию.

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение10.08.2015, 10:39 
Заслуженный участник
Аватара пользователя


11/03/08
6776
Москва
Да, и касательно заглавия темы. Метод, конечно же, не "наименьшего спуска". Нам надо (при поиске минимума) спуститься как можно глубже. Он "наискорейшего спуска", когда мы, единожды определив направление, идём "по компасу" в этом направлении, не отвлекаясь на уточнение этого направления, покамест, идя так, мы не прекращаем спускаться, и лишь тогда ищем новое направление спуска. То есть "скорость" в том, чтобы идти, не отвлекаясь.

(Оффтоп)

Нечего думать, трясти надо!

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

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение13.08.2015, 10:22 


23/04/15
64
Прошу прощения, действительно метод наискорейшего, а не наименьшего спуска.

По поводу формулы (**) . У меня при ее выводе получилось то же самое, только в числителе еще стоит 2, т.к. при разложении по формуле Тейлора возникает коэффициент $\frac{1}{2}$ перед вторыми производными.
Если я правильно понял, то написав такое разложение 2-го порядка f(x) = f(x_0) + ... , мы приравниваем производную к нулю, т.е. f(x)-f(x_0)=0, и находим шаг. Но правильно ли я понимаю, что это не совсем точно? Ведь если разложить функцию до 3-х производных, то там возникнет уже квадратное уравнение относительно шага?
А если более высшие порядки рассматривать, то степень уравнения будет ещё больше?

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение13.08.2015, 10:37 
Заслуженный участник
Аватара пользователя


11/03/08
6776
Москва
Это выражение даёт оптимальный шаг, если целевая функция квадратична. То есть производные выше второго порядка принимаются нулями.

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение13.08.2015, 11:38 


23/04/15
64
Евгений Машеров в сообщении #1044930 писал(а):
Это выражение даёт оптимальный шаг, если целевая функция квадратична. То есть производные выше второго порядка принимаются нулями.


Тогда ясно. Спасибо.

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение13.08.2015, 12:11 
Заслуженный участник
Аватара пользователя


11/04/08
2531
Физтех
$$\[g\left( h \right) = f\left( {{x_k} + h \cdot {e_k}} \right) = f\left( {{x_k}} \right) + h \cdot \nabla f\left( {{x_k}} \right){e_k} + \frac{1}{2}{h^2} \cdot e_k^T{\nabla ^2}f\left( {{x_k}} \right){e_k}\]$$ $$\[g'\left( h \right) = \nabla f\left( {{x_k}} \right){e_k} + h \cdot e_k^T{\nabla ^2}f\left( {{x_k}} \right){e_k} = 0 \Rightarrow \]$$ $$\[h =  - \frac{{\nabla f\left( {{x_k}} \right){e_k}}}{{e_k^T{\nabla ^2}f\left( {{x_k}} \right){e_k}}}\]$$

А теперь привожу без изменений формулу (**): $$\[{h^k} =  - \frac{{{\nabla ^T}f\left( {{X_k}} \right){S^k}}}{{{{\left( {{S^k}} \right)}^T}*{\nabla ^2}f\left( {{X_k}} \right)}}\]$$

Pumpov в сообщении #1044929 писал(а):
По поводу формулы (**) . У меня при ее выводе получилось то же самое, только в числителе еще стоит 2
Евгений Машеров в сообщении #1043589 писал(а):
Формула, обозначенная по ссылке (**), правильная, но практически непригодная.
Объясните мне, пожалуйста, как это вы получаете, что (**) правильная, да еще и с двойкой в числителе?

 Профиль  
                  
 
 Re: Шаг в методе наименьшего спуска
Сообщение18.08.2015, 09:50 


23/04/15
64
Евгений Машеров в сообщении #1043589 писал(а):
Объясните мне, пожалуйста, как это вы получаете, что (**) правильная, да еще и с двойкой в числителе?


Я ошибся. Двойки не должно быть. Спасибо за вывод.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group