§ 2.15. Сходимость и устойчивость
Алгоритмы оптимизации могут быть
реализованы, если они сходятся, т. е. если с течением времени 
в дискретных
алгоритмах и 
в
непрерывных алгоритмах стремятся к оптимальному значению вектора 
. В связи с этим
установление сходимости приобретает важное значение. Только при
гарантированной сходимости можно рассчитывать на применение алгоритмов
оптимизации.
Поскольку каждому алгоритму
оптимизации соответствует некоторая автономная система с обратной связью, то
сходимость алгоритма, а значит и его реализуемость, эквивалентна устойчивости
этой автономной системы.
Для исследования устойчивости
можно использовать методы, довольно хорошо развитые в механике и теории
автоматического управления.
Мы здесь схематически наметим
некоторые возможности исследования устойчивости замкнутых дискретных систем
особой структуры и, следовательно, сходимости алгоритмов оптимизации. Прежде
всего воспользуемся подходом, аналогичным принятому в теории нелинейных систем,
который можно трактовать как аналог метода Ляпунова для дискретных систем.
Составим уравнение в вариациях.
Обозначим
, (2.47)
где 
— отклонение от оптимального вектора.
Подставляя это значение в рекуррентную форму алгоритма оптимизации (2.4),
легко получить
. (2.48)
Это разностное уравнение имеет
тривиальное решение 
,
так как для оптимального вектора по определению 
. Устойчивость тривиального
решения уравнения (2.48) и соответствует сходимости алгоритма оптимизации
(2.4). Как известно, различают устойчивость в малом (когда все координаты
вектора малы)
и в целом (при любых ). Для исследования устойчивости в малом
нужно аппроксимировать 
линейным приближением и затем
рассмотреть устойчивость полученного линейного разностного уравнения. При 
, т. е. в стационарном
случае, эта задача сводится к определению условий, при которых корни
соответствующего характеристического уравнения находятся внутри круга
единичного радиуса. Поскольку линейное приближение справедливо при достаточно
малых значениях ,
то устойчивость в малом соответствует сходимости алгоритмов оптимизации при
условии, что начальные значения векторов 
принадлежат некоторой малой сфере с
неизвестным центром, что вряд ли полезно и интересно. Нас несоизмеримо больше
интересует устойчивость при любых начальных значениях , т. е. устойчивость в целом.
Исследование этого типа устойчивости основано на применении аналога второго
метода Ляпунова.
Выберем в качестве функции
Ляпунова норму вектора :
. (2.49)
Первая разность Ляпунова в силу
уравнений (2.48) равна
. (2.50)
Условие устойчивости в целом
требует, чтобы первая разность была отрицательна. После обычных и несложных
преобразований получаем
, (2.51)
где 
— единичная матрица, а
(2.52)
Фактически мы использовали здесь
принцип сжатых отображений, который применительно к уравнению в вариациях, т.
е. к случаю, когда неподвижная точка расположена в начале координат, тождествен
прямому методу Ляпунова.
Принцип сжатых отображений может
быть применен и непосредственно к алгоритму оптимизации в рекуррентной форме
(2.4), для которого неподвижная точка соответствует значению оптимального
вектора. Разумеется, при этом мы получим те же результаты, быть может, в несколько
иной форме. Полученные таким образом условия являются, вообще говоря, лишь
достаточными.
