костью процедуры вычисления а. Заметим кстати, что неравенство (4.7) ие допускает «слишком малых» шагов.

Вычисление и,, на основе критерия (4.7) о «малым» ц называют «аккуратным одномерным поиском»; если же г]=0, то говорят о «точном одномерном поиске».

Неравенство (4.7) не содержит изменения функции, и поэтому оно, вообще говоря, не гарантирует существенного убывания F. Чтобы обеспечить такое убывание, (4.7) обычно дополняют условием вида

F(Xi,)-F(Xt + ap)>-[xagPi„ (4.8)

где 0<pV2- Оно означает, что Кд будет выбираться из того диапазона, в котором график функции F {Xi,-i-ap) лежит не выше прямой Ца) = Р {Xi,)-i-[iaglpi,.

Множество значений и, удовлетворяющих (4.7) и (4.8), обозначим через Г(г], р). Можно показать, что прн рг] это множество не пусто.

Основное достоинство условия (4.7) как критерия приемлемости шага состоит в том, что оно хороию согласуется с эффективными процедурами одномерной минимизации. В частности, его удобно использовать в комбинации с регуляризованными методами одномерного поиска на основе полиномиальной интерполяции. Для большинства функций соответствующие алгорн-пяы вычисления шага работают очень быстро. Надо отметить также, что при малых р (скажем, р=10-") любой шаг а, удовлетворяющий (4.7), будет, как правило, автоматически удовлетворять (4.8).

Среди разнообразных методов выбора выделяется класс эффективных процедур, работающих по принципу генерирования последовательности {/;} вложенных интервалов, содержащих множество Г(11, ц). Для построения таких последовательностей используются рассмотренные в разд. 4.1.2 регуляризованные схемы одномерного поиска с полиномиальной интерполяцией. При этом вычисления прерываются, как только точка минимума интерполирующего полинома попадает в множество Г(т), р). Ее н принимают в качестве искомого aft.

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

0<6<арЛ<Д. (4.9)

где 6 есть минимальное разрешенное расстояние между xrj+i и Лл, а А - оценка сверху расстояния от хи до точки минимума F вдоль ph. Корректные значения параметров б и А, вообще говоря, зависят от Xft и F. По смыслу Б аналогичен параметру разделения точек на итерациях регуляризованных процедур поиска нуля (см. разд. 4.1.1.5). Он должен отражать точность, с коюрой удается вычислять значения F (подробности см. в разд. 8.5). Что же касается

параметра А, то о его величине в общем случае ничего конкретного сказать нельзя. Библиотечные программы безусловной минимизации обычно предполагают, что он будет задан пользователем (см. разд. 8.1.3.4). Ситуация упрощается, если задача поиска безусловного минимума в действительности решается как подзадача в методе минимизации при линейных ограничениях (см. разд. 5.2). Тогда в качестве А можно брать максимальный шаг, не нарушающий ограничений.

Подобно алгоритмам на основе правила Гольдштейна - Армийо, регуляризованные методы вычисления шага с полиномиальной интерполяцией требуют задания исходной оценки «", причем хорошая оценка, как правило, сокращает объем вычислений. К сожалению, как показано в разд. 4.4.2.1, бывают случаи, в которых разумную оценку а"" дать невозможно. В этих случаях выбор в (4.9) верхней границы для llapftll приобретает особое значение, так как становится единственным средством избежать бессмысленных расчетов в процессе одномерной минимизации.

Выше неявно предполагалось, что работа процедуры выбора шага «л сопровождается вычислениями градиента функции F в каждой пробной точке. Соответственно ни о каких трудностях контроля соблюдения неравенств (4.7) речи не было. Однако если расчет градиента g(x) - относительно дорогое удовольствие, то имеет смысл воспользоваться другим критерием приемлемости шага и взять для одномерной минимизации алгоритм, которому не нужны значения производных. В частности, (4.7) можно заменить неравенством

(4.10)

1де -v - некоторое число из диапазона 0<vsga. Это неравенство не допускает слишком малых шагов и вместе с (4.8) обеспечивает существенное убывание F иа каждой итерации.

4.3.2.2. Вычисление направления поиска. Для конкретизации модельной схемы поиска безусловного минимума кроме алгоритма вычисления шага надо определить, как будет выбираться «хорошее» направление р. В отличие от одномерного случая, когда возможны только два движения - «вперед» и «назад», уже в двумерной задаче множество приемлемых направлений бесконечно. Таким образом, проблема выбора Pft действительно существует. Вся оставшаяся часть данной главы посвящена описанию различных способов (с указанием соответствующих мотивировок) ее решения. Надо сказать, что именно способ задания р «определяет лицо алгоритма» минимизации. Поэтому названия алгоритмам обычно дают по реализованным в них правилам вычисления направлений спуска, а к вычислению шага принято относиться как к некой отдельной процедуре.

Гл. 4. Методы безусизтоймшшмизащш.

Рассмотрим линейную аппроксимацию функции F, основанную на ее тейлоровском разложении в окрестности точки х: F(x,, + p)fsFt + glp.

Если ориентироваться на эту аппроксимацию и предполагать, что шаг вдоль р будет единичным, то представляется разумным стремиться к такому направлению р, которому отвечает большая по модулю отрицательная величина glp. Это вроде бы сулит значительное уменьшение F. Ясно, что в данном случае необходима какая-то нормировка сравниваемых векторов. Иначе по любому р, такому, что gftP<0, можно было бы построить вектор р. доставляющий величине gjp любое отрицательное значение: достаточно было бы взять в качестве р произведение р на соответствующее положительное число. Тем самым сравнение потеряло бы всякий смысл. Итак, можно выбирать р из соображений минимизации величины gfp на множестве всех векторов р, нормализованных подходящим образом. Это означает, что р будет решением аадачи вида

найти rain (4.11)

реч"

где II II-некоторая норма.

Решение задачи (4,11) целиком определяется выбором нормы, фигурирующей в ее постановке. Если эта норма задается симметричной положительно определенной матрицей С, т.е. р=" = (рСр)", то решением (4.11) будет

P.= -C-gft. (4.12)

В частности, еслн взять евклидову норму, т. е. р = (рр)", вектор Pt оказывается антиградиентом:

Рм=-а. (4.13)

Поскольку он является решением задачи (4.11) с нормой типа обычной длины, его называют напршлением наискорейшего спуска. Соответственно и реализацию модельной схемы с вычислением р» по формуле (4.13) называют методом наискорейшего спуска.

Если градиент не равен нулю, направление наискорейшего спуска, безусловно, будет направлением убывания F (так как в этом случае gPj, = -gfeft<0), причем угол между ним и градиентом всегда далек от прямого. Значит, комбинация любого из рассмотренных ранее правил выбора шага с вычислением Pft по формуле (4.13) дает глобально сходящийся алгоритм безусловной минимизации.

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

4.3. Методы для гладких функщй многих переменных

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

Пусть F (х)-квадратичная форма вида сх:--72л:Сх:, где вектор с и матрица С не зависят от х, причем С симметрична н положительно определена. Если для поиска минимума такой функции F (х) воспользоваться методом наискорейшего спуска с вычислением шага путем точного одномерного поиска, то ои сгенерирует последовательность приближений, линейно сходящуюся к решению. Обозначив через Х„„ и максимальное и минимальное собственные числа матрицы С, можно показать, что при этом будет справедлива оценка

f (x,,j-f (X.) «[t°:;w<w-"))-

где и есть cond (С) - спектральное число обусловленности матрицы G.

Представленный результат обескураживает тем, что допускает значения параметра асимптотической ошибки, сколь угодно близкие к единице, т. е. процентное сокращение ошибки на одной итерации может быть сколь угодно малым. Например, уже при к=100 (что считается неплохой обусловленностью) оценка параметра ошибки оказывается равной (99/101):=в0.96, так что ожидаемый выигрыш за счет одного шага очень невелик. И в самом деле, даже для небольшого улучшения оценки решения по методу наискорейшего спуска обычно требуются сотни итераций. Это относится к квадратичным задачам и тем более к задачам с функциями общего вида.

На рис. 4j изображена «траектория движения» метода наискорейшего спуска в задаче минимизации функции Розенброка (пример 4.2). Гладкие кривые - это линии уровня функции, отрезки ломаной соответствуют шагам спуска на отдельных итерациях. Шагн определялись аккуратным одномерным поиском. Алгоритм начал работать с точки (-1.2, 1.0) и мог бы надолго «засгряты> в окрестности точки (0.3, O.I)"", если бы не помогла счастливая случайность - на одной из итераций процедура одномерного поиска неожиданно нашла второй минимум по направлению. После этого было выполнено еще несколько сотен итераций, но ощутимого изменения целевой функции это не дало. Счет был прерван после 1000 итераций вдали от искомого решения. Этот конкретный пример с умеренно плохо обусловленной функцией еще раз подтверждает, что существование доказательства формальной сходимости метода и отсутсгвие его реальной сходимости (т. е. сходимости за приемлемое число шагов) вполне совместимы.

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

Рис. 4j. Траектория поиска минимума функции Розенброка методом наискорейшего спуска.

для линейно сходящихся алгоритмов часто оказывается очень малым. Последующие разделы этой главы посвящены методам со сверхлинейной сходимостью.

Замечания и библиография к разделу 4.3

В качестве источника, содержащего строгое математическое толкование термина «существенное убывание функции» и многие фундаментальные теоремы сходимости, мы рекомендуем книгу Орте-гн и Рейнболдта (1970). Подробное обсуждение процедур выбора шага на основе регуляризованных методов с полиномиальной интерполяцией читатель найдет в статье Гнлла и Мюррея (1974е). Алгоритмы, основанные на применении условия (4.6), предлагались Гольдштейном и Прайсом (1967) и Флетчером (1970а). Вулф (1969) и Пауэлл (1976а) использовали вместо (4.7) неравенство

g(4 + <Pi,VPi>>ySlPk, (4.14)

где 0<т<1. Оно не допускает слишком малых «ь, но в отлнчие от (4.7) всегда позволяет делать сколь угодно большие шаги. Л1етод одномерного поиска на основе (4.14) и (4.8) с »р>р описан в статье Шанно и Фуа (1976).

Для некоторых алгоритмов (таких, как метод сопряженных градиентов нз разд. 4.8.3.3) теоретически важно, чтобы задача одномерной минга1шзацнн решалась очень точно, и поэтому прн их реализации возникает желание взять ii меньшим чем р. Надо, однако, иметь в виду, что в данном случае удовлетворить парам условий типа (4.7) (или (4.10)) и (4.8) будет нелегко, а то и просто невозможно. Например, множество Г(11, р) может оказаться пустым. Правда, это бывает редко, но все же бывает, и в особенности на начальных итерациях работы алгоритма, когда норма HgH велика нли когда функция F плохо от»1асштабнрована (как, например, штрафные и барьерные функции, рассматриваемые в разд. 6.2.1). Исчерпывающее обсуждение общего случая, в котором может принимать любое значение из (о, 11, выходит за рамки данной книги. Отметим только, что всегда най/цтся шаги, обеспечивающие существенное убывание F{x) и удовлетворяющие неравенствам (4.7) или (4.10) при каком-то значении у\ из этого диапазона. За дальнейшими подробностями мы отсылаем читателя к работе Гилла, Мюррея, Сондерса и Райт (1979).

Идея использования направления наискорейшего спуска для построения алгоритма многомерной минимизации восходит к Koi[ih (1847) и послужила предметом обширного исследования. Детальный анализ скорости сходимости метода наискорейшего спуска дан в книгах Канторовича и Акилова (1964) и Ленбергера (1973).

Существует довольно много методов безусловной минимизации, логика функционирования которых несколько отличается от изложенной в модельной схеме разд. 4.3.1. В частности, в них длина шага ttft всегда берется равной единице, так что новое приближение определяется по формуле Xk.i=Xff-\-pj,. В данном случае, чтобы найти подходящее направление р, обеспечивающее соблюдение условия спуска, может понадобиться перебрать несколько пробных векторов. Методы указанного типа часто называют методами доверительной окрестности (в противовес методам с регулировкой шага, о которых речь шла выше). Краткий обзор таких методов приводится в замечаниях к разд. 4.4. Кроме того, один из методов доверительной окрестности, предназначенный для решения нелинейных задач о наименьших квадратах, будет разобран в разд. 4.7.3.

4.4. МЕТОДЫ ВТОРОГО ПОРЯДКА

4.4.1. МЕТОД НЬЮТОНА

Алгоритм, который нам предстоит рассмотреть в этом разделе, исторически является первым из методов, основанных на квадратичной аппроксимации минимизируемой функции F. Такая аппроксимация, оставаясь достаточно простой, в то же время намного точнее, чем линейная, используемая в классическом методе наискорей-