Общая схема методов спуска

Будем рассматривать задачу безусловной минимизации, т.е. задачу минимизации целевой функции f на всем пространстве R. Сущность всех методов приближенного решения этой задачи состоит в построении последовательности точек х1, х2, х3, …, хk, …, монотонно уменьшающих значение целевой функции:

f(x0) >= f(x1) >= f(x3) >= … >= f(xk) >= … (1.3)

Такие методы (алгоритмы) называют методами спуска. При использовании этих методов применяют следующую схему.

Пусть на k-й итерации имеется точка хk. Тогда выбирают направление спуска pk Î R и длину шага вдоль этого направления ak > 0. Следующую точку последовательности вычисляют по формуле:

xk+1 = xk + ak*pk, k = 0, 1, 2, …

Согласно этой формуле, величина продвижения из точки xk в xk+1 зависит от как ak, так и от pk. Однако ak традиционно называют длиной шага.

Формально различают методы спуска отличные друг от друга способом выбора числа ak и вектора pk. Если для определения ak и pk требуется вычислять только значения целевой функции, соответствующий метод называют методом нулевого порядка или методами поиска. Методы первого порядка требуют, кроме того, вычисления первых производных целевой функции. Если же метод предполагает использование и вторых производных, то его называют методом второго порядка и т.д.

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

Важнейшей характеристикой любых методов спуска является их сходимость. Сходимость здесь понимается в том смысле, что последовательность {xk} должна сходиться к точке глобального (локального) минимума. Однако точки минимума могут составлять целое множество и многие алгоритмы позволяют построить последовательность {xk}, которая сама не является сходящейся, но любая ее сходящаяся последовательность имеет в качестве предельной некоторую точку минимум (см. рис. 3).

В этом случае говорят, что каждая предельная точка последовательности {xk} является точкой минимума. С помощью подобных алгоритмов можно строить последовательности точек, сколь угодно близко приближающихся ко множеству точек минимума.

Возможен случай, когда ничего определенного сказать и о сходимости последовательностей нельзя, однако известно, что соответствующая последовательность значений при {f(xk)} сходится к точке минимального значения (локальный или глобальный минимум). Тогда говорят, что последовательность {xk} сходится к минимуму по функции (см. рис. 4). Кроме того, существуют еще более слабые типы сходимости, когда, например, последовательность {xk} (каждая ее последовательность) имеет в качестве предельной стационарную точку (т.е. точку, в которой градиент равен нулевому вектору), являющуюся лишь «подозрительной» на оптимальную.

Как правило, тип сходимости одного и того же метода зависит от конкретного вида целевой функции, т.е. в разных задачах метод может сходится по-разному. При достаточно жестких требованиях к функции f с помощью метода можно строить последовательность, сходящуюся в точке глобального минимума. Если же этот метод применить к функциям, не удовлетворяющим элементарным требованиям, то может быть получена последовательность, сходящаяся только по функции, либо последовательность, не являющаяся сходящейся ни в каком смысле.

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

Градиентные методы

Ненулевой антиградиент - Ñ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, можно сделать вывод, что для целевой функции, линии уровня которой близки к окружностям, требуемая точность будет достигнута довольно быстро, тогда как если линии сильно вытянуты в окресности оптимальной точки, то градиентные методы приведут к медленному зигзагообразному продвижению в направлении на оптимальную точку. О функции, поверхность уровня которой сильно вытянуты, говорят, что она имеет «овражный» характер (в случаях двух переменных график такой функции действительно напоминает овраг).

		Рисунок 6 Линии уровня (вытянутые)

О степени «овражности» функции f можно получить представление, зная минимальное (m) и максимальное (M) собственные числа матрицы Гессе Ѳf, вычисленной в оптимальной точке: чем меньше отношение m/M, тем больше “овражность” данной функции. Применение градиентных методов к таким функциям приводит к спуску на «дно оврага», после чего, поскольку направление спуска почти перпендикулярно «линии дна», точки последовательности {xk} будут поочередно находится то на одном «склоне оврага», то на другом и продвижение к оптимальной точке сильно замедляется.