§ 10.2. Понятие о методах спуска. Покоординатный спуск

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

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

Опишем структуру типичной итерации метода спуска в предположении, что приближение к точке минимума уже найдено и

1°. Находят ненулевой вектор называемый направлением спуска. Этот вектор должен быть таким, чтобы при всех достаточно малых выполнялось неравенство

Если ввести функцию одной переменной а, имеющую вид

то неравенство (10.11) можно записать так:

2°. Вычисляют положительное число (шаг спуска), для которого выполняется неравенство

или, что то же самое, неравенство

3°. За очередное приближение к точке минимума принимают

4°. Проверяют выполнение критерия окончания итераций. Если критерий выполняется, то итерации прекращают и полагают . В противном случае итерации продолжают далее.

Последовательность точек генерируемую Методом спуска, иногда называют траекторией спуска.

2. Направление спуска.

Заметим, что вектор не может быть задан произвольно. В силу требования (10.11) функция определяемая формулой (10.12), должна убывать в точке Для того чтобы это условие выполнялось, достаточно потребовать выполнения неравенства Так как то вектор является направлением спуска, т. е. удовлетворяет условию (10.11), если

Можно показать, что для строго выпуклой функции это неравенство выполняется тогда и только тогда, когда вектор задает направление спуска.

Обычно именно способ выбора направления спуска конкретный численный метод, а различные варианты метода определяются далее алгоритмом вычисления шага спуска Например, выбор в качестве (антиградиента задает градиентный метод (см. § 10.3). В этом случае т. е. условие (10.14) выполняется.

3. Выбор шага спуска.

Следует иметь в виду, что шаг спуска определяет "истинную" величину шага но совпадает с ней только тогда, когда вектор имеет единичную длину.

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

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

За шаг спуска принимают где первый из номеров для которого выполнено условие

Здесь некоторый дополнительный параметр.

4. Критерии окончания итераций.

На практике часто используют следующие критерии окончания итераций:

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

Нередко вместо критериев (10.16), (10.17) применяют их аналоги, основанные на сочетании понятий относительной и абсолютной погрешностей:

а также другие критерии.

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

5. Покоординатный спуск.

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

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

Фактически решается задача минимизации функции одной переменной

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

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

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

На рис. 10.4 изображена геометрическая иллюстрация циклического покоординатного спуска.

Рис. 10.1.

Применим метод циклического покоординатного спуска для минимизации квадратичной функции (10.5). Так как на шаге очередного цикла значение координаты определяется из условия минимизации функции по направлению то необходимо, чтобы в точке производная обращалась в нуль. Учитывая формулу (10.7), получаем уравнение

откуда находим

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