§ 2.12. Многошаговые алгоритмы оптимизации

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

Рис. 2.9.

Если функционал имеет несколько экстремумов, то одношаговые алгоритмы позволяют определить лишь локальные экстремумы. Для определения абсолютного, глобального экстремума можно попытаться применять многошаговые алгоритмы оптимизации, например алгоритмы вида

(2.36)

или

. (2.37)

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

; , (2.38)

которые вытекают из того условия, что при замене на должно выполняться равенство . Структурные схемы, реализующие алгоритмы (2.36) и (2.37), показаны на рис. 2.9 и 2.10.

Рис. 2.10.

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

, (2.39)

где принимается, что .

Тогда после подстановки (2.39) и (2.36) и (2.37) получим

(2.40)

. (2.41)

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

Из многошаговых алгоритмов при получаем уже знакомые нам одношаговые алгоритмы. Если в (2.36), (2.37) или (2.40), (2.41) заменить разделенной разностью из уравнения (2.20) или , то получим соответствующие многошаговые поисковые алгоритмы.

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

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