Основы теории оптимизации (стр. 57 )

Следовательно, они являются корнями уравнений

(9)

Можно показать, что если

где ρ — любой корень уравнения (9).

Теперь мы можем воспользоваться теоремой о ло­кальной сходимости итерационных процессов вида (7), что дает возможность получить оценку (5). Вычисляя

находим приведенные в теореме оптимальные значенияа α*, β* и соответствующее им q*.

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

(10)

а для двухшагового

(11)

Для больших значений числа обусловленности

(12)

Поэтому, чтобы приблизиться к решению в е=2,7 ... раз, в одношаговом методе требуется порядка μ/2 итераций, в двух-шаговом — порядка Иными словами, для плохо обусловленных задач метод тяжелого шарика дает выигрыш в раз по сравнению с градиентным. Для больших μ эта разница весьма значительна. С вычислительной же точки зрения метод (2) немногим сложнее одношагового.

Правда, подбор оптимальных значений α и β в (2) не прост — формулами (6) непосредственно воспользоваться не удается, так как границы спектра (числа l и L) обычно неизвестны.

2. Метод сопряженных градиентов. Рассмотрим другой вари­ант двухшагового метода — метод сопряженных градиентов, в котором параметры находятся из решения двумерной задачи оптимизации:

(13) (14)

Для случая квадратичной функции

(15)

эта задача может быть решена явно:

(16)

Могло бы показаться, что соотношение методов (13), (14) и (2) такое же, как рассмотренных ранее методов, — если метод скорейшего спуска не дает, как мы видели, выигрыша в скоро­сти сходимости по сравнению с градиентным методом с постоян­ным оптимальным γ, то и от двухшагового варианта скорей­шего спуска (13), (14) трудно ждать существенного ускорения по сравнению с методом тяжелого шарика (2). Оказывается, ситуация здесь иная: так, в квадратичном случае метод (13), (14) (при специальном выборе р1) является конечным, т. е. дает точный минимум функции (15) за конечное число итераций.

Пусть начальное приближение х0 произвольно, а х1 полу­чено из него методом скорейшего спуска:

(17)

Лемма 1. Градиенты r0, r1, ... в методе (13), (16), (17) попарно ортогональны:

(ri, rk) = 0, i<k. (18)

Доказательство. Воспользуемся индукцией по k. Пусть (ri, rk) = 0 приОртогональность r0, r1, r2 следует непосредственно из определения метода. Тогда, умножая (13) слева на А, получаем

Из r1≠ 0 для i ≤ k следует, что αk ≠ 0. Поэтому Ark есть ли­нейная комбинацияаналогичноесть линейная комбинацияи в силу предположения ин­дукции Следовательно,

при i = 0, ..., k — 2.

Далее, непосредственно из формул (13), (16) следует, что

Наконец, из (13), заменяя k на k—1, имеем

Применяя это соотношение последовательно, полу­чаем, что рk есть линейная комбинацияпричем rk-1 входит с коэффициентом Поэтому из ,

следует, что

Итак, для всех i ≤ k будет (rk-1, ri) = 0.

Если rk обращается в 0, то хk —точка минимума f(x). Но в Rn не может существовать более п ортогональных ненулевых векторов, поэтому для некоторого k ≤ п будет rk=0. Итак, мы доказали следующий результат.

Теорема 2. Метод (13), (16), (17) дает точку минимума квадратичной функции f(x) вида (15) за число итераций, не превосходящее п.

Мы установим в дальнейшем, что если L — не­которое подпространство в Rn, f(x) - выпуклая дифференци­руемая функция, то условие

необходимо и достаточно для того, чтобы х* было минимумом f(x) на L. Отсюда и из леммы 1 следует, что xk — точка мини­мума квадратичной функции f(x) вида (5) на подпространстве, проходящем через х0 и порожденном r0, ..., rk-1. Этот несколь­ко неожиданный факт (мы ищем минимум k раз последова­тельно на 2-мерных подпространствах, а он оказывается мини­мумом на всем n-мерном подпространстве) является важнейшей особенностью метода сопряженных градиентов и объясняет его конечность.

Последовательные направления движения pk в методе со­пряженных градиентов удовлетворяют соотношению

(19)

Действительно, рi= хi — хi-1, поэтому

С другой стороны, мы уже отмечали, что рk есть

линейная комбинация Поэтому для

i > k имеемв силу леммы 1.

Векторы рi, связанные соотношением (19), называются со­пряженными или А-ортогональными (они ортогональны в ме­трике, задаваемой матрицей А). Это объясняет название ме­тода — в нем строятся линейные комбинации последовательных градиентов, являющиеся сопряженными.

Отметим, что знание произвольных сопряженных направле­ний позволяет без труда решить систему

(20)

Действительно, будем искать решение в виде

Тогда, подставляя это в (20), умножая скалярно на si и используя

A-ортогональность, имеем

(21)

Этому решению можно придать рекуррентную форму: зададимся произвольным х0 и построим где αk задаются

(21). Тогда хп = х* — решение (20). Поскольку αk в (21) мож­но определить иначе:

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