Дискретный метод Ньютона обычно сходится «квадратично» 1 вплоть до того момента, когда достигается предельная точность решения (т. е. получено приближение, которое из-за погрешностей машинной арифметики нельзя было бы улучшить и в том случае, если бы была известна точная матрица Гессе). Детальное обсуждение пределов точности читатель найдет в разд. 8.2.2.

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

Итак, если говорить о достоинствах дискретных ньютоновских методов, то они те же, что и у обычных методов ньютоновского типа,- высокая скорость сходимости и способность «ощущать» приближение седловой точки и уходить от нее. К недостаткам же следует отнести необходимость вычисления иа каждой итерации и значений градиента, которые требуются для построения п столбцов аппроксимации матрицы Гессе, когда в качестве конечно-разностных направлений используются столбцы единичной матрицы. Поэтому при ft>*10 или около того дискретные ньютоновские методы нередко начинают проигрывать другим методам первого порядка, представленным ниже. Однако они могут сохранять первенство ц при больших и, если матрица Гессе разрежена и известная структура расположения ее ненулей позволяет экономно организовать процедуру построения конечно-разностной аппроксимации (см. разд. 4.8.1).

4.Б.2. КВАЗИНЬЮТОНОВСКИЕ МЕТОДЫ

4.5.2.1. Теория. Залогом эффективности методов ньютоновского типа, рассмотренных в разд. 4.4 и 4.5.1, является учет информации о кривизне минимизируемой функции, содержащейся в матрице Гессе и позволяющей строить локально точные квадратичные модели F. Кеазиньютоноеские методы тоже ориентированы на квадратичные модели, но данные относительно кривизны F накапливаются в них на основе наблюдения за изменением градиента g во время итераций спуска. Последнее принципиально отличает эти методы от ньютоновских, в которых сведения о свойствах F всегда относятся к одной точке. Теория квазиньютоновских методов опирается на возможность аппроксимации кривизны нелинейной функции без явного формирования ее матрицы Гессе.

Обозначим через s,, шаг из точки х„ и рассмотрим разложение градиента в ряд Тейлора в окрестности хд «по степеням» Sj,

В силу этого разложения линейная оценка кривизны F вдоль т. е. произведения £Сд8», задается формулой вида

slQt4"(g(x„-h)-Si,ys„. (4.27)

Равенство станет точным, если отнести его к квадратичной функции из (4.15). формула (4.27) лежит в основе всех квазинькугоновских методов первого порядка.

К началу очередной k-v. итерации квазиньютоновского поиска известна некоторая аппроксимация Bj матрицы Гессе минимизируемой функции. Матрица Вд служит средством отображения информации о кривизне, накопленной па предыдущих итерациях. Используя ее Б качестве матрицы Гессе моденьной квадратичной формы, очередное направление р,, квазиньютоновского поиска определяют как решение аналогичной (4.17) системы уравнений:

BhPh=~gh- (4.28)

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

После того как определится новая точка л:д+,, приближение Вд матрицы Гессе обновляется с учетом вновь полученной информации о кривизне, т. е. совершается переход err матрицы Вд к матрице Bft+i. Он задается формулой пересчета типа

Впг-=В„ + и„, (4.29)

где t/j-некоторая поправочная матрица. Обозначим через % вектор, равный изменению аргумента х иа k-й итерация (s = -i:*+i-Хдгяадрд), а через у,, соответствующее приращение градиента (Уй = 6)1+1-gk)- Тогда основное свойство всех квазиньютоновских правил пересчета (4.29) выразится равенством

B),+ .St = fo. (4.30)

В силу (4.27) оно означает, что B+i будет правильно отражать кривизну F вдоль Sj. Это равенство принято называть квазиньютоновским условием.

Один шаг дает информацию о кривизне F вдоль одного-един-ствеииого направления, поэтому мы вправе надеяться, что в формуле (4.29) удастся обойтись поправкой (/д малого ранга. Так оно и есть: квазиньютоновскому условию можно удовлетворить и не одним способом, даже если искать f д среди матриц ранга один, т. е. подбирать Вд.,., в форме

B„i = B„-\.uv, (4.31)

где U и в - некоторые векторы. В данном случае условие (4.30) принимает вид равенства

Вд+,8д=(Вд-)-иИ-)8д = 4/д,

откуда следует, что

< № 2еВ4

Гл. 4. Метуды Оезусловной тишгшзации

Таким образом, независимо от выбора v вектор и должен быть параллелен разности -Bs, причем мы полагаем, что она не равна нулю (т. е. сама матрица Bf квазиньютоновскому условию ие удовлетворяет). Когда некоторый не ортогональный вектор V задан, в качестве и в соответствии с последним равенством надо взять (l/fSft) (j/ft-BftSj, и при этом

Вб+1 = -е*+,-д>:(й--еА)1.-.

(4.32)

Даже поправки раита один определяются квазииыотоновским условием с точностью до вектора v, т. е. неоднозначно. Те.м более неоднозначно определены поправки высших рангов. Как они могут выглядеть, подсказывает следующее соображение. Для любого ортогонального Sj вектора ш и любого г произведение матрицы ранга один zw на равно нулю. Значит, выполнив условие (4.30) при некоторой Bft+i, мы не нарушим его, если добавим к В+, любое число матриц типа zw (хотя сама матрица Bft+i, конечно, изменится). Итак, в выборе на основе квазиньютоновского условия (4.30) есть большая свобода. Эту свободу используют для того, чтобы обеспечить матрице Bi различные дополнительные свойства.

Симметрия. Поскольку сама матрица Гессе симметрична, представляется естественным позаботиться о том, чтобы таковыми были и ее квазиньютоновские приближения. Для этого надо строить формулы пересчета, которые гарантировали бы сохранение симметрии, т. е. обеспечивали бы симметричность Bi при симметричной В. В случае с поправками ранга один это требование определяет Ut. однозначно. Чтобы пересчет по формуле (4.31) сохранял симметрию, вектор V должен быть коллинеарен и. При этом формула (4.32) преобразуется к виду

где у-В,, и {y-BsySt предполагаются ненулевыми. Эту формулу пересчета называют симжтринной формулой ранга один.

Поскольку среди формул единичного ранга симметрию сохраняет только одна, для того, чтобы найти другие симметричные формулы, надо обратиться к поправкам ранга два. Конструировать их можно, например, так: имея симметричную матрицу Bj, положим В"=Вь и вычислим матрицу В" по формуле (4.32), т. е. возьмем

B« = BS + -y-Bsv, Л,=0.

Полученная матрица удовлетворяет квазииьютоновскому условию, ио, вообще говоря, несшиметрична. Симметризуем ее, т. е. построим матрицу B" вида

В«> = 1. + 1)Г).

4.5. Методы первого порядка

Теперь мы получили симметричную матрицу, но оиа не удовлетворяет квазипыотоновскому условию. Снова воспользуемся пересчетом (4.32) и т. д. В ре.чультате определится последовательность матриц {BJ, для которых при / = 0, 1, ...

B*"By + -(y,-B"J>s,)vr,

Эта последовательность имеет предел Bj+i, вычисляемый по формуле

= В. -Ь ((й-ад + V {y,-BA)T)-=il±T,

(4.33)

Поправка к 6,, в этой формуле, вообще говоря, имеет ранг два и определена для любого вектора v, не ортогонального Sj. В классе правил пересчета, получающихся из (4.33) при различных v, содержится, в частности, и симметричная формула ранга один. Она отвечает выбору в (4.33) вектора ВtSj. Если же взять o=s,,

то получится хорошо известиая симметричная формула Пауэлла - Бройдена (PSB-формула). Еще одна распространенная форму.па пересчета квазиньютоновских матриц получается из (4.33), если v положить равным j/j. Она называется формулой Дэвидона - Флет-чера - Паэулла (DFP) и выглядит следующим образом:

Непосредственной подстановкой легко проверить, что вектор ортогонален Значит, добавив к В+, матрицу ранга один, кратную EJjKJf, мы не нарушим ни квазиньютоновского усповия, ни симметрии. Эго соображение приводит к однопараметриче-скому семейству формул пересчета вида

й<-Ьч>«(5В4%)и)еК

(4.35)

где скалярная величина может зависеть от у,, и Щз. Коль скоро фд можно выбирать, естествеиио возникает вопрос о том, как делать это наилучшим образом. Данному вопросу было посвящено немало исследований. Однако в большинстве своем они иосили чисто теоретический характер, и приводить их обзора мы не будем. Ограничимся выводом! в настоящее время принята точка зрения, что самой эффективной в классе формул (4.35)

является простейшая из них, отвечающая выбору iPfSsO. Эта формула пересчета, известная под названием формулы Бройде-на-Флетчера-Гольдфарба-Шанно (BFGS-формулы), выглядит так:

-ВА4Вк+УнУ1

(4.36)

Все представленные выше формулы нересчета выведены независимо от того, как определяется вектор Sft. Если же в действительности получается в результате шага пд вдоль направления рд, найденного из решения уравнения (4.28), то формулы можно упростить, используя равенство Вй5й=-agt. Например, BFGS-формула будет выглядеть так:

Bi,ti = Bt +

-УлУк-

(4.37)

Когда шаги Од определяются в результате точной одномерной минимизации, между различными формулами из однопараметри-ческого семейства (4.35) устанавливается очень специфичная связь. Пусть f(x)-дважды непрерывно дифференцируемая функция н зафиксированы некоторые х„ и В. Пусть далее через jxj}, {В„\, {pff и {%} обозначены последовательности, генерируемые квазиньютоновским поиском с BFGS-формулой, а через {х\, {Ffi\, \pt) и \а.\-последовательности, соответствующие какой-нибудь другой формуле пересчета из семейства (4.35). Тогда оказывается, что если а,, и а); выбираются как точки одномерных локальных минимумов, ближайших к а = 0, то, начиная с ft = 0 и до тех пор, пока матрицы В, Bf определены, будут выполнены соотношения

xS = x,. B, = B+(-t-)g,gr (4.38)

Таким образом, при оговоренных условиях все методы семейстш (4.35) генерируют одинаковые последовательности точек. Второе равенство в (4,38), кроме того, показывает, что элементы квазиньютоновской аппроксимации матрицы Гессе вовсе не обязательно будут приближаться к соответствующим э.тементам оригинала. Как видно из (4.38), матрицы Вд и BJ, вообще говоря, значительно отличаются друг от друга на всех итерациях, и если для одной из них отклонение от матрицы Гессе окажется «малым», то для другой оно наверняка будет «большим».

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

одномерного поиска скорее всего окажутся существенно различными. Это связано с тем, что величина первого пробного шага в процедуре поиска для разных BJ будет разной. В одном случае оиа окажется хорошей оценкой искомого Ид, в другом - плохой. Соответственно и вся процедура вычисления в одном случае проработает быстрее, а в другом-медленнее.

Положительная определенность. Конечная цель квазиньютоновского поиска состоит в том, чтобы найти точку х*. в которой реализуется локальный минимум функции F. В большинстве случаев этот минимум будет сильным, а матрица Гессе в х*- положительно определенной. Соответственно хотелось бы, чтобы матрицы {Bft} тоже были положительно определенньми. Кроме того, что более существенно, при положительно определенной Bj локальная квадратичная модель имеет единственный минимум, и направление Рл, найденное нз (4.28), оказывается направлением спуска. Короче говоря, принято требовать, чтобы формула пересчета квазиньюто-иовских матриц обеспечивала сохранение положительной опреде-.аенности, т. е. гарантировала бы наличие этого свойства у Вд если им обладает В„.

Анализ условий сохранения положительной определенности для разных формул пересчета проводится по-разному; мы выведем такие условия для BFGS-формулы. Когда матрица Вд положительно определенна, существует невырожденная матрица Fi, такая, что B„ = RR. Используя это разложение, (4.36) можно переписать в виде

В»+1 = «"Й7«, (4.39)

где W вычисляется по формуле

-ss-Ь:

(4.40)

в которой s = RSt и y = (R-yk. Из (4.39) следует, что матрица Вд.,, будет положительно определенной в том и только том случае, если положительно опредепена W. При этом, так как W отличается от единичной матрицы лишь добавкой ранга два, п~2 ее собственных значений (для п>3) совпадают с единицей. Таким образом, все зависит от двух оставшихся собственных значений. Мы обозначим их через Я, и Х,. Можно пока.зать, что отвечающие им собственные векторы должны быть линейными комбинациями от s и у. Имея это в виду, непосредственной подстановкой легко установить, что числа Я и X, связаны соотношениями вида

Поскольку величина ss положительна, из полученных равенств вытекает, что Xj и Я будут больше нуля тогда и только