§ 3. Методы спуска

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

Рассмотрим примеры методов спуска.

При исследовании сходимости метода Зейделя в случае системы уравнений при мы описали циклический метод покоординатного спуска минимизации функции : при заданном приближении отыскивается значение , при котором достигается , затем отыскивается значение , при котором достигается , и т.д. Процесс циклически повторяется.

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

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

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

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

Рис. 7.3.1

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

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

и соответствующая минимуму точка принимается за .

Иногда номер очередной координаты, по которой осуществляется спуск, выбирается недетерминированно. В этом случае говорят о случайном покоординатном спуске.

Другой вариант метода спуска — метод наискорейшего (градиентного) спуска. Следующее приближение отыскивается в виде

(рис. 7.3.2). Значение определяется из условия

т.е. этот алгоритм опять состоит в последовательной минимизации функции одной переменной .

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

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

Рис. 7.3.2

обладающей следующими свойствами.

Количество операций при отыскании одного значения и при одновременном отыскании всех значений , в той же точке одинаково; обозначим его через А. Количество операций при непосредственном отыскании значений и при одновременном отыскании всех значений , в той же точке одинаково. Обозначим его через обычно .

Тогда при решении задачи методом Ньютона целесообразно вычислять производные , пользуясь приближенной формулой

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

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

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

На прямой имеем

поэтому следующее приближение определяют из условия

Отметим, что в данном случае существен вопрос о разумном выборе в в формуле (2). (По этому поводу см. § 2.16.)

Задача минимизации функции при наличии ограничений, так называемая задача условной минимизации, формулируется следующим образом. Ищется величина

при условиях

При решении этой задачи возникают дополнительные трудности по сравнению с решением задачи отыскания безусловного минимума, в которой ищется

— нижняя грань по всему пространству .

Непосредственное использование многих из описанных выше методов становится невозможным, и возникает необходимость в их модификации.

В то же время задача минимизации функции при ограничениях типа (4), (5) является весьма актуальной для приложений. Например, существует целый раздел математики — линейное программирование, — занимающийся решением задачи в случае, когда — линейные функции аргументов .

Среди других методов, связанных с решением задачи (3) (5), упомянем метод штрафа. Строится последовательность функций , удовлетворяющая следующим условиям:

1) определена при всех ;

2) при ;

3) если существуют точки такие, что

то при .

Вместо решения исходной задачи решается задача отыскания минимума при достаточно больших .

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

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

Вводится некоторая невозрастающая функция , определенная при , такая, что . Например, можно взять

В качестве берется функция

Наличие слагаемого заставляет смещаться точку экстремума в область, где в то время как наличие слагаемого заставляет смещаться точку экстремума в область, где .

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

В связи с отмеченными недостатками метода штрафа разработано большое число других методов решения задачи условной минимизации (3)-(5).