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

Будем на каждой итерации в качестве направления спуска-s_k выбирать направление вдоль одной из координатных осей. В этом разделе приводится схема, не обладающая достоинствами независимости выбора направления спуска от градиента функции, но зато имеющая оценки, гарантирующие сходимость процесса минимизации со скоростью порядка O(1/m). Эти оценки интересны тем, что показывают существенную зависимость скорости сходимости от размерности пространства Е_n. Пусть x_k уже известен, и пусть

Можно считать, что

так как в противном случае x_k = x^* и процесс минимизации оканчивается. Схема метода:

где

Выясним скорость сходимости метода, предполагая, го функция φ(x) удовлетворяет условиям, при которых справедлива теорема 9.4, а в случае сильной выпуклости-теорема 9.5. Так как

то из (9.9) получаем оценку

Таким образом, константа при величине 1/m в оценке скорости сходимости этого метода в п раз больше соответствующей константы в оценках метода градиентного

спуска.

В случае же сильной выпуклости функции φ(x) из (9.12) и (9.13) получаем оценки