5.4.3. Циклический координатный спуск

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

Пусть определены единичных координатных векторов-направлений Например, в

Метод циклического координатного спуска оптимизирует циклически в каждом из координатных направлений. Если дана точка то Точка получается из максимизацией в положительном и отрицательном направлениях Затем мы определяем максимизацией из используя как положительное, так и отрицательное направление

Определив используем положительное и отрицательное направления и получим Затем процедура повторяется, исходя из точки Под отрицательным направлением имеется в виду

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

Здесь для интервал , где — положительный скаляр. Такой выбор обеспечивает поиск как в положительном, так и в отрицательном направлениях.

Сходимость. На основе следствия 4.2.2 любое отображение замкнуто, так как — непрерывная функция, а — замкнутое отображение. По предположению все точки находятся в компактном множестве X. Следовательно, для любого

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

Чтобы доказать выполнение условия 2, предположим, что имеет непрерывные первые частные производные. Далее предположим, что для любого х и направления с существует единственное для которого

Предположение о единственности исключает наличие у функции «площадок», параллельных осям координат.

Пусть Назовем точку х подходящей, если

В такой точке, благодаря предположению о единственности,

Условие 2а выполняется, так как, если не является подходящей точкой, то

Значит, условия теоремы сходимости А выполнены, так как условие 1 предполагается.