§ 2.15. Сходимость и устойчивость

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

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

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

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

Составим уравнение в вариациях. Обозначим

,                                         (2.47)

где  — отклонение от оптимального вектора. Подставляя это значение в рекуррентную форму алгоритма оптимизации (2.4), легко получить

.                      (2.48)

Это разностное уравнение имеет тривиальное решение , так как для оптимального вектора  по определению . Устойчивость тривиального решения уравнения (2.48) и соответствует сходимости алгоритма оптимизации (2.4). Как известно, различают устойчивость в малом (когда все координаты вектора  малы) и в целом (при любых ). Для исследования устойчивости в малом нужно аппроксимировать  линейным приближением и затем рассмотреть устойчивость полученного линейного разностного уравнения. При , т. е. в стационарном случае, эта задача сводится к определению условий, при которых корни соответствующего характеристического уравнения находятся внутри круга единичного радиуса. Поскольку линейное приближение справедливо при достаточно малых значениях , то устойчивость в малом соответствует сходимости алгоритмов оптимизации при условии, что начальные значения векторов  принадлежат некоторой малой сфере с неизвестным центром, что вряд ли полезно и интересно. Нас несоизмеримо больше интересует устойчивость при любых начальных значениях , т. е. устойчивость в целом. Исследование этого типа устойчивости основано на применении аналога второго метода Ляпунова.

Выберем в качестве функции Ляпунова норму вектора :

.                                  (2.49)

Первая разность Ляпунова в силу уравнений (2.48) равна

.   (2.50)

Условие устойчивости в целом требует, чтобы первая разность была отрицательна. После обычных и несложных преобразований получаем

,                                                             (2.51)

где  — единичная матрица, а

                                  (2.52)

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

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