шего спуска. Это позватяет строить на ее основе эффективные алгоритмы.

Располагая первыми и вторыми производ[1ымн целевой функции F, в качестве ее квадратичной модели можно взять сумму первых трех членов тейлоровского разложения F в о1фестности текущей точки кк, т. е. воспользоваться приближенным равенством вида

F(4 + P)=»Pk+gIP + pG. (4,15)

Минимум его правой части (если он существует) достигается на векторе р, доставляющем минимум квадратичной форме

a>(p) = gIp + ~PC,p.

(4.16)

Будучи стационарной точкой Ф(р), этот вектор должен (см, разд. 3.2.3) удовлетворять равенству

GftPft=-gt- (4.17)

Алгоритм минимизации, в котором направление рц определяется системой (4.17), называют методом Ньютона, а решение этой системы - ньютоновским направлением.

В задаче поиска минимума произвольной квадратичной функции с положительно определенной матрицей вторых производных метод Ньютона дает решение за одну итерацию, причем: независимо от выбора начальной точки (заметим, что шаг при этом надо взять единичным). Значит, мы вправе надеяться, что в случаях, когда матрицы Cft оказываются положительно определенными и модельные функции (4.15) хорошо приближают исходную, этот метод будет быстросходящимся. И в самом деле, если метод Ньютона применить к нелинейной функции F общего вида, то при определенных условиях он сойдется к искомой точке х* квадратично. Эти условия состоят в следующем: матрица Гессе минимизиpyeюй функции в точке X* должна быть положительно определенной, начальное приближение Хй должно лежать достаточно близко к х*, а последовательность шагов {Oft } должна сходиться к единице.

Высокая скорость локальной сходимости метода Ньютона делает его чрезвычайно привлекательным aлгopитюм безусловной минимизации. К тому же использование вторых производных позволяет организовать контроль соблюдения достаточных условий оптимальности (см, разд. 3.2.2). Короче говоря, метод Ныскгона считается чем-то вроде эталона, с которым надо сравнивать другие алгоритмы, и немало усилий потрачено на разработку процедур, приближающихся к нему по быстродействию. Однако, говоря о достоинствах, не следует забывать и недостатки. Метод Ньютона может работать плохо или даже отказать, еслн используемые в нем квадратичные приближения функции F будут неверно описывать поведение F вне малых окрестностей опорных точек Xf,.

Если матрица положительно определена, то система (4,17) разрешима единственным образом и определяет единственный минимум модельной функции (4,15). В данном случае гарантировано, что решением (4.17) будет направление спуска, так как gjpj = -gi; CiTg/i < 0. Прн этом косинус угла между градиентом gj н вектором Pt отличается от нуля не менее, чем на величину, обратную числу обусловленности G. Значит, если известно, что все матрицы G будут положительно определенными, а их числа обусловленности-равномерно ограниченными сверху, то можно утверждать, что применение ньютоновских направлений в комбинации с каким-нибудь методом выбора швга иа основе рассмотренных в разд. 4.3.2.1 критериев дает глобально сходящийся алгоритм. (Раньше метод Ньютона с регулировкой шага называли «релаксационным», но сейчас этот термин практически не употребляется.) Регулировка шага обязательна, поскольку единичный шаг вдоль ньютоновского направления может привести к увеличению F несмотря на то, что он приводит в точку минимума модельной функции. Важно, однако, подчеркнуть, что квадратичная сходимость метода Ньютона достижима лишь при условии, что длины шагов будут достаточно быстро сходиться к своему «естественному» значению, равному единице. Отметим одно интересное обстоятельство: ньютоновское направление можно рассматривать как направление «наискорейшего спуска», если норму в (4.11) определить по формуле р1 = (pGp)"".

Когда матрица G не является положительно определенной, квадратичная модельная функция может не иметь ни конечной точки минимума, нн какой-либо другой стационарной точки. Напомним (разд. 3.2.3), что Ф (р) наверняка будет неограниченной снизу, если у Gft есть сггрнцательные собственные числа, и что необходимым и достаточным условием наличия у Ф (р) единственной стационарной точки является невырожденность Gj. Если же С- вырожденная матрица, стационарные точки будут существовать только при условии, что градиент gt принадлежит подпространству, натянутому на столбцы Gh-

В настоящее время нет общепринятого определения «метода Ньютона» для расчета направления спуска при знаконеопределенной матрице G,,, поскольку среди специалистов нет согласия относительно того, как использовать локальную квадратичную аппроксимацию F в этом случае. Здесь мыслимы разные стратегии. Например, можно считать, что «лучшее» направление поиска следует искать среди направлений, вдоль которых квадратичная модельная функция неограниченна. Л1ожно рассуждать и по-другому. В общем есть много схем организации спуска, построенных иа базе метода Ньютона и работоспособных в отсутствие положительной определенности Gfc. Все эти схемы, по возможности использующие ньютоновские направления и уклоняющиеся от них только тогда, когда это

необходимо, принято называть модифицированными методами Ньютона.

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

4.4.2. СТРАТЕГИИ ДЛЯ ЗНАКОНЕОПРЕДЕЛЕННОЙ МАТРИЦЫ ГЕССЕ

Общий принцип работы большинства модифицированных методов Ньютона состоит в следующем: на каждой итерации сначала строится некоторая «связанная» с положительно определенная матрица Оц, а затем вьмисляется как решение системы

C = -gft. (4.18)

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

Формула (4.18) не применима, когда л;-седловая точка. В самом деле, в ней градиент равен нулю, и соответственно решение системы (4.18) тоже будет нулевым. Здесь в качестве pj надо взять какое-нибудь направление отрицательной кривизны - вектор, удовлетворяющий неравенству PkGg), < 0. В седловой точке, где матрица G не является знакоопределенной, такие векторы существуют, и при движении вдоль любого из них функция F будет убывать. Идти по направлению отрицательной кривизны рекомендуется и в том случае, когдв норма lgj не равна нулю, но «очень мала».

Если числа обусловленности матриц G ограничены равномерно по k, то комбинация формулы (4.18) для расчета направления спуска и любого из критериев выбора шага, приведенных в разд. 4.3.2.1, дает глобально сходящуюся модификацию метода Ньютона.

Итак, в модифицированных ньютоновских методах направление спуска находится из решения линейной системы (4.18), причем матрица Gj должна совпадать с Gj, если G является положительно определенной. Последнее предполагает, что на каждой итерации каким-то образом выясняется, все ли собственные числа матрицы Gft положительны (а это, за исключением особых случаев, по виду самой Cf, не определить). В обсуждаемых ниже модификациях метода Ньютона выяснение определенности Сц и построение G осуществляются параллельно в рамках одной процедуры. Это делается на основе некоторых матричных разложений, которые позволяют выявить знаки собственных чисел

и приспосабливаются для генерации G.

4.4.2.1. Методы, основанные иа спектральном разложении.

Для построения связанной с G положительно определенной матрицы можно использовать собственные числа и векторы Сц (см. разд. 2.2.5.4). Основой служит спектральное разложение Сц вида

(4.19)

где Л-диагональная матрица, а U-ортонормальная матрица, составленные из собственных чисел и собственных векторов соответственно. Из этого разложения следует, что линейное преобразование Cf, «делит» пространство своих аргументов на два взаимно ортогональных подпространства. Одно из них, натянуто на

собственные векторы ju,}, которым отвечают «существенно nojra-жительиые» собственные значения. Набранную из этих векторов матрицу обозначим через Второе. натянуто на остальные собственные векторы, образующие матрицу U . Заметим, что любая положительная ко11;бинация тех столбцов Г1;атрицы t/ , которым отвечают отрицательные собственные значения, будет направлением отрицательной кривизны.

Прн переходе от Gj к желательно не затрагивать структуры преобразования С в отношении векторов из Тогда для существенно положительно определенных G будет гарантировано равенство C, = Cf,, т. е. модификация будет осуществляться только тогда, когда она действительно необходима. Данное условие обеспечено, если строить матрицу в виде

C„ = UAU, (4.20)

где Л-положительная диагональная матрица с >.,, равными Я,-при всех i, для которых Я, существенно положительны. Что же касается тех диагональных элементов матрицы Л, которые отвечают столбцам и., то их можно выбирать разными способами

в зависимости от того, какие свойства требуются от С(. Заметим только, что подстановка вместо отрицательных X, положительных Xj во всяком случае означает, что последствия применения преобразований С/, и в соответствующей части 4t будут <(противоположными».

Для иллюстрации двух способов замены отрицательных собственных чисел возьмем следующий пример с диагональной матрицей Гессе.

Пример 4.6. Пусть матрица вторых производных G и градиент gi, выглядят так:

У такой матрицы Гессе (очевидно) есть одно отрицательное и одно положительное собственные значения, а ее собственными векторами являются столбцы единичной матрицы. Обычное ньютоновское направление, рассчитываемое как решение системы (4.17), в данном случае равно (-2, 1) и приводит в седловую точку модельной функции (4.15). Оно составляет острый угол с градиентом gj,, т. е. указывает в сторон> возрастания функции.

Первый из предлагаетх способов построения Ghcxoaht из естественного стремления использовать в качестве Gj «ближайшую» к Gj положительно определенную матрицу. Этот способ состоит в том, что каждое собственное значение Х, меньшее, чем некоторое малое число 6 > о, определяющее «порог существенной положительности», заменяется иа 6, В примере 4,6 результатом будет

При таком выборе решением системы (4.18) является вектор (-2, -5/6). Он явно тяготеет к подпространству Щ и имеет большую норму. И то и другое-характерные особенности рассматриваемого подхода. По сути дела, это своеобразное отражение того, что квадратичная модельная функция не ограничена снизу, и для ее «минимизации» надо сделать бесконечный шаг вдоль какого-нибудь направления отрицательной кривизны. Следует отметить, что большое значение нормы вектора вычислительных трудностей не порождает: во-первых, рц всегда можно перенормировать, а во-вторых, можно выставить подходящую верхнюю границу иа длину шага в процедуре одномерного поиска.

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

знаку к вектору, указывающему в точку максимума модельной функции в В примере 4.6 рассматриваемый способ модификации дает матрицу

Норма вектора р из (4,18) в данном случае равна норме обычного ньютоновского направления.

Матрицы Gft, вычисляемые по правилу (4.20), положительно определены, и их числа обусловленности при ограниченных максимальных собственных значениях матриц G также будут ограниченными. Различие между незнакоопределенной матрицей Gj и отвечающей ей Gj при любом из двух представленных способов выбора Х,- характеризуется неравенством [G-С(, <2Я.„,,„, где Х„1„-минимальное собственное чисчо G,,. Кривизна минимизируемой функции вдоль направления Рц, вычисленного по формулам (4.18) и (4.20), может быть и отрицательной, и положительной.

Расчет полной собственной системы G обычно требует от 2п» до 4/г арифметических операций. Таким образом, модификация G/, на основе спектрального разложения-довольно дорогая процедура. В настоящее время разработаны более эффективные способы построения G (как, например, метод, рассматриваемый в следующем ра:зделе). В них подпространства 4i+ и U описываются приближенно, и это позволяет существенно сократить необходимый объем вычислений.

*4.4.2.2. Методы, основанные на факторизации Холесского.

Любая симметричная положительно определе11иая матрица представима в виде произведения LDL, где L-единичная нижняя треугольная матрица, а D-по,ггожительная диагональная матрица (см. разд. 2.2.5.2). Это представление называют факторизацией (разложением) Холесского. Коль скоро столбцы матрицы L с номерами от 1-го по (/ - 1)-й известны, ее /-Й столбец вычисляется по формулам

d, = 8,j-dfi„ (4.21а)

.7 = («./-/ЛЛ.)- (4.21Ь)

Аналогичные формулы существуют и для построчной организации вычислений.

По аналогии с pacгJяoтpeниoй выше модификацией Gj на основе спектрального разложения, казалось бы, естественно предложить и такую процедуру построения G: формируется разло-