Навигация
1.2.2 Градиентные методы
Ненулевой антиградиент - Ñf(x0) указывает направление, небольшое перемещение вдоль которого из х0 приводит к значению функции f меньшему, чем f(x0). Это замечательное свойство лежит в основе градиентных методов, согласно которых на k-й итерации полагают pk = - Ñf(xk), т.е.
xk+1 = xk - akÑf(xk), ak > 0, k = 0, 1, 2, … .
Эти методы отличаются друг от друга способом выбора величины шага ak. Достаточно малый шаг ak обеспечивает убывание целевой функции
f(xk+1) = f(xk – ak Ñf(xk)) < f(xk), (1.4)
но может привести к слишком большому количеству итераций для достижения требуемой точности. С другой стороны, выбор большого шага может привести к нарушению неравенства 1.4.
На практике нередко в качестве величины шага выбирают некоторое а > 0, одинаковое для всех итераций. При этом если условие 1.4 (при ak =|a|) нарушится, то для текущей итерации величину а уменьшают до тех пор, пока указанное неравенство не станет выполнимым.
Часто величину ak рекомендуют выбирать так, чтобы имело место более жесткое условие убывания, чем 1.4:
f(xk) – f(xk – akÑf(xk)) >= eak || Ñf(xk) ||, (1.5)
где 0 < e <1 – некоторая фиксируемая константа. Здесь также сначала фиксируют некоторое ak = a > 0 (например, ak = 1), одинаковое для всех итераций, а затем при необходимости уменьшают его до тех пор, пока не будет выполнено неравенство 1.5.
При реализации градиентных методов в качестве критериев окончания счета используют условие вида || Ñf(xk) || <= e, где е > 0 –фиксированная точность вычислений.
Точный смысл сходимости градиентных методов раскрывает следующее утверждение.
Пусть функция f ограничена снизу, непрерывно дифференцируема на R и ее градиент Ñf(x) удовлетворяет условию Липшица:
|| Ñf(x) -Ñf(x’) || <= L || x – x’ || для всех x,x’ Î R,
где L >= 0 – некоторая фиксированная константа. Кроме того, пусть выбор величины шага ak производится на основе условия 1.5. Тогда, какова бы ни была начальная точка х0, оба градиентных метода приводят к построению последовательности {xk}, обладающей свойством lim || Ñf(xk) ||= 0. Если, кроме того, функция f дважды непрерывно дифференцируема и существует такие числа М >= m > 0 , что
m || y || ² <= (Ѳf(x)y,y) <= M || y || ² для всех x,y,
то для градиентных методов последовательность {xk} будет сходится к точке глобального минимума.
Первая часть утверждения гарантирует сходимость лишь в смысле lim || Ñf(xk) || = 0, т.е. сходимость по функции либо к точной нижней грани inf f(x), либо к значению функции f в некоторой стационарной точке х. При этом сама точка х не обязательно является точкой локального минимума; она может быть точкой седлового типа. Однако на практике подобная ситуация маловероятна и применение градиентных методов, как правило, позволяет получить приближенное значение минимума целевой функции (вообще говоря, локального).
Сравнивая рисунки 5 и 6, можно сделать вывод, что для целевой функции, линии уровня которой близки к окружностям, требуемая точность будет достигнута довольно быстро, тогда как если линии сильно вытянуты в окресности оптимальной точки, то градиентные методы приведут к медленному зигзагообразному продвижению в направлении на оптимальную точку. О функции, поверхность уровня которой сильно вытянуты , говорят, что она имеет «овражный» характер (в случаях двух переменных график такой функции действительно напоминает овраг).
 | |||||
 | |||||
| |||||
О степени «овражности» функции f можно получить представление, зная минимальное (m) и максимальное (M) собственные числа матрицы Гессе Ѳf, вычисленной в оптимальной точке: чем меньше отношение m/M, тем больше “овражность” данной функции. Применение градиентных методов к таким функциям приводит к спуску на «дно оврага», после чего, поскольку направление спуска почти перпендикулярно «линии дна», точки последовательности {xk} будут поочередно находится то на одном «склоне оврага», то на другом и продвижение к оптимальной точке сильно замедляется.
Похожие работы
... сети, позволяющая реализовать автоматическое изменение числа нейронов в зависимости от потребностей задачи, позволяет не только исследовать, но и контролировать процесс воспитания психологической интуиции искусственных нейронных сетей. - Впервые применена выборочная константа Липшица для оценки необходимой для решения конкретной задачи структуры нейронной сети. Практическая значимость ...
... работы со справочной системой работа практикума приостанавливается. 3. Организационно-экономическое обоснование проекта В ходе дипломного проекта был разработан компьютерный лабораторный практикум по курсу «Теория оптимизации и численные методы». В данном разделе рассмотрена экономическая сторона проекта. Рассмотрены следующие вопросы: 1) сетевая модель 2) расчёт ...
0 комментариев