Методы покоординатного спуска

Методы безусловной минимизации

Методы покоординатного спуска

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

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

Здесь – j -тая координата вектора .

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

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

Метод случайного покоординатного спуска. В этом варианте метода номер изменяемой координаты выбирается из целых чисел от 1 до n случайным образом с равной вероятностью. При реализации метода используют генератор псевдослучайных чисел.

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

.

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

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

.

В заключение параграфа отметим, что существует большое количество различных модификаций покоординатных методов. Здесь можно выделить три направления: первое из них связано с различными способами регулировки шагового множителя, второе – с порядком выбора координатного направления итерационного перехода, и, наконец, третье направление предполагает использование базисов отличных от . Большинство таких модификаций но-сит характер эвристических приемов, которые для некоторых классов задач позволяют заметно повысить эффективность методов. Наилучших результатов можно добиться в рамках третьего направления модификаций. Здесь также можно выделить две группы методов. Одна из них предпо-лагает переход к новому базису после каждого цикла (состоящего в поочередном использовании базисных координат). Другая группа методов основана на адаптации базиса к свойствам минимизируемой функции. Методы сопряженных направлений, с которыми мы познакомимся в следующем параграфе, относятся к этой группе методов.