Гл.4. Мепюды безусловной мтишиэации

Одно из наиболее интересных следствий этого результата состоит в том, что из него вытекает возможность получить сверхлинейную сходимость квазиньютоновского поиска даже тогда, когда сходимости jBft и G{x*) нет. Оказывается, условию (4.47) можно удовлетворить и в ее отсутствие. Прн некоторых предпапожениях это условие будет, в частности, выполнено для BFGS-, PSB- и DFP-формул.

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

Иитересио отметить, что поправочные матрицы в некоторых квазнньютоновских формулах представляют собой решения специфичных оптимизационных задач тнпа: найти для матрицы Ви поправку Uh минимальной нормы, обеспечивающую матрице Sft+A заданные свойства (такие, как подчинение квазиньютоновскому условию, симмегричность, положительная определенность н т. д.). Так, например, PSB-формуле отвечает задача вида

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

найти mm\Vfp = S .5! 4%

прн условиях USfy,, - Вд8д,

(4.48)

Здесь через \\U\p обозначена норма Фробеннуса матрицы U. Аналогичные задачи, но с иными нормами можно поставить в соответствие и другим квазиньютоновским формулам.

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

Первый квазиньнэтоноЕский метод был разработан Дэвидоном (1959). Автор назвал его методом «переменной метрики». В этом названии отражена интерпретация вектора рд из уравнения (4.28) как шага в точку минимума квадратичной модельной функции. Будучи положительно определенной, ее матрица Гессе С задает «метрику» по правилу, приведенному в разд. 4.3.2.2. Вектор рд, указывающий в точку минимума этой функции, есть направление наискорейшего спуска в данной метрике. Ну а поскольку штрица С от итерации к итерации меняется, можно говорить о наискорейшем спуске с пошаговым изменением метрики. Отсюда и название - «метод переменной метрики».

Метод Дэвидона был разрекламирован и усовершенствован Флетчером и Пауэллом (1963) (что объясняет термин «DFP-формула»). Они первыми показали, что для квадратичных функций при точной одномерной минимизации он дает решение за конечное число ша-

гов. Формулу BFGS независимо предложили Бройден (1970), Флет-чер (1970а), Гольдфарб (1970) и Шанно (1970).

Начиная с 1963 г. интерес к квазиньютоновскнм методам непрерывно возрастал. За время, прошедшее с тех пор, накопилась обширнейшая литература, в которой проанализированы всевозможные аспекты методов этого сорта. Хорошие обзоры с дополнительными ссылками читатель найдет в работах Авриеля (1976), Брод-ли (1977а), Денииса и Море (1977) и Флетчера (1980).

Квазиньютоновские методы очень близки к методам сопряженных градиентов (см. Назарет (1979) и разд. 4.8.3).

Идея применения факторизации Холесского в качестве средства, позволяющего получать численно устойчивые реализации квазиньютоновского поиска, принадлежит Гиллу и .Мюррею (1972) (см. также работы Флетчера и Пауэлла (1974), Гилла, Мюррея и Сондерса (1975) и Бродли (1977b)). Следующим шагом по повыше-иню устойчивости было бы устранение неоправданных потерь точности в ситуациях, когда норма квазиньютоновской поправки оказывается много меньше суммы норм составляющих ее простейших матриц. Например, любую модификацию ранга два можно было бы осуществлять по фюрмуле виде

где но = 0 (см. Гилл и Мюррей (1978с)).

Основные заслуги в исследовании сходиьюсти квазиньютоновских методов принадлежат Бройдену, Деннису, Море, Пауэллу и Стоеру (см. Бройден (1967, 1970), Бройден, Деннис и Море (1973), Пауэлл (1971, 1975, 1976с) и Стоер (1975, 1977)). Критерий (4.46) достижения сверхлиненной скорости квазиньютоновского поиска получен Деннисом и Море (1974). Обзор результатов по сходимости с хорошей библиографнен содержится в работах Денннса и Море (1977) и Бродли (1977b). Замечательный результат (4.38) о теоретической эквивалентности методом однопараметрического семейства (4.35) получен Диксоном (1972а, Ь). Экстремальные свойства квазиньютоновскнх поправок первым заметил Гринштвдт (1970). Читателя, желающего ознакомиться с этим аспектом квазиньютоновских формул поподробнее, мы отсылаем к работам Денннса и Море (1977), Денниса и Шнабеля (1979, 1980).

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

функции) оказываются реализации без точного одномерного 1юиска. Попытки истолковать это явление предпринимались несколькими авторами, в том числе и Флетчером (1970а). Заметив, что для любой формулы однопараметрического семейства (4.35) справедливо равенство

где Bfe и Bk-квазиньютоновские приближения матрицы Гессе, отвечающие BFGS- и DFP-формулам соответственно, он ввел выпуклый подкласс формул из (4.35), определенный условием ф€[0, I], и показал, что любая формула из этого подкласса для квадратичной функции F гарантирует монотонную сходимость собственных чисел матрицы

/?, = Gv.BfC/. (4.49)

к единице независимо от того, как выбираются шаги а..

Наряду с попытками формализации задачи о поиске оптимального метода велись и работы иного сорта, в которых неоднозначность выбора формулы пересчета квазиньютоновских приближений снималась на основе нек(Угорых «естественных» дополнительных требований. Например, Дэвидон (1975), Орен и Спедикато (1976) предложили подбирать очередную ква:и[Ньютоновскую матрицу так, чтобы оценка сверху числа ее обусловленности бь[ла минимальной. Тем самым опреде.г1ились и формулы пересчета. Орен и Ленбергер

(1974) тоже ориентировались на число обусловленности, но не самой квазиньютоновской матрицьг, а произведения (4.49). Ценой введения дополнительного параметра они построили метод, который для квадратичной функции при точном одномерном поиске гараширует, что это число будет монотонно убывать (см. также Орен (1974а, Ь)). В последнее время стали появляться также попытки конструировать формулы, обеспечивающие конечную сходимость квазнньютонов-ского поиска для функций более общих, чем квадратичные (см. Дэвидон (1979), Соренсен (1980b)). Дэвидон (1975) предложил класс методов, которые для квадратичных форм сходятся за конечное число итераций в отсутствие точного одномерного поиска. Спедикато

(1975) выделил семейство формул, инвариантных относительно некоторого нелинейного масштабирования.

4.6. МЕТОДЫ МИНИМИЗАЦИИ ГЛАДКИХ ФУНКЦИЙ

БЕЗ ВЫЧИСЛЕНИЙ ПРОИЗВОДНЫХ

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

модели, например имитационной. Бывает и так, что сначала вообще не ясно, является ли функция гладкой. Тогда нужно выяснить это, и здесь усилий жалеть не стоит. Конечно, в рассматриваеьюй ситуа-1ЩИ все равно придется гбратиться к методам без вычисления производных, но к каким именно методам, зависит от гладкости. Если производных не существует, прибегают к методам типа алгоритма многогранника из разд. 4.2.1, специально разработанным для негладких задач. Если же производные есть, но просто ие поддаются вычислению, эти методы применять не следует - слишком уж осторожно используется в них информация о значениях функции. Коль скоро известно, что функция гладкая, этой информацией можно оперировать н посмелее. Пример методов предыдущего раздела, использующих значения только первых производных н тем не менее правильно аппроксимирующих кривизну минимизируемой функции, а петому и весьма эффективных, показывает, что в этом есть смысл.

4.6.1. КОНЕЧНО-РАЗНОСТНАЯ АППРОКСИМАЦИЯ ПЕРВЫХ ПРОИЗВОДНЫХ Когда поставлена задача минимизации гладкой функции, точные значения производных которой недоступны, естественно возникает желание воспользоваться каким-нибудь из методов первого порядка, подменив истинный градиент g(x) его конечно-разностной аппроксимацией. Часто это и в салюы деле оказывается выходом из положения. Однако подобная адаптация методов первого порядка - проблема, к сожаленшо, нетривиальная, и это связано с их чувствительностью по отношению к ошибкам конечно-разностных приближений. Природа этих ошибок рассматривается в следующем разделе.

4.6.1.1. Ошибки при правой конечно-разностной аппроксимации.

Чтобы не загромождать изложения, мы ограничимся анализом ошибки, возникающей при численном оценивании первой производной дваждЬ! непрерывно дифференцируемой функции скалярного аргумента х. Чаще всего оценку вычисляют по правой конечно-разностной формуле (см. раз.ч. 2.3.5). В этом случае аналитическим приближением производной f (х) служит величина

Ф.(/. ft) = №lW. (4.50)

Численная аппроксимация значений f{x) по формуле (4.50) связана с ошибками трех типов.

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

4>F(f, h)-f (X) = Г т - Т,(h), (4.51)

где I - некоторая точка отрезка [х, x-hh] (см. разд. 2.3.4.).

Ошибка условий. При реализации формулы (4.50) на машине функция f будет вычисляться с ошибками. Это значит, что вместо f(x) и f(x + h) в правую часть (4.50) войдут величины f(x) и f (х + Л). связанные с истинными значениями f следующим образом:

f(x) = f(.x) + c. f(.x + h)f(x + h)-\-a„.

Здесь 1о, од - абсолютные ошибки вычисления / в точках х и x+h (см. разд. 2.1.6). Соответственно численной оценкой производной в отсутствие прочих ошибок будет величина, равная

?(Ar + ft)-f(jt)

Ее выражение через аналитическую оценку выглядит так;

Ф.(/. h)=t=m+4j(f, й)+с(ф„й).

Отклонение С (фк. Л) численной оценки от аналитической называют ошибкой условий (по классификации разд. 2.1.5 она относится к ошибкам компенсации). Справедливо равенство

С (срр, h) = SfFmaxllcl, I Oft I)

(4.52)

где lifrKl.

Если модуль 1Л не слишком мал, то о и Од можно выразить через относительные ошибки вычисления Д т. е. воспользоваться представлениями вида

о=е/(4, Oft=eJ(A:+ft),

где leliEn, lEftlER. Тогда выражение для ошибки условий преобразуется следующим образом:

C(4>f, А) = -еМ,е«. (4.53)

Здесь e,.Kl и Л1,.=тах{(х)1, \f(x+h)\].

Ошибки округления. Вычисление оценки фг по заданным }(х) и J{x+h) будег сопровождаться ошибками округления, неизбежными при машинном вычитании и делении. Однако эти ошибки, как правило, пренебрежимо малы в сравнении с рассмотренньши выше. Поэтому в дальнейшем они не упоминаются.

4.6.1.2. Выбор конечно-разностного интервала. Ошибка численного оценивания производной f {х) величиной фу (/, h) складывается из ошибок отбрасывания (4.51) и условий (4.52) (или (4.53)). Первая из них пропорциональна конечно-разностному интервалу А, а вторая - обратной ему величине. Таким образом, последствия варьирования h для них противоположны.

Пример 4.9. Рассмотрим результаты численного оценивания прн разных h производной функции

/W = (-l) + (y=r-iy (4.54)

в точке х=1. Они получены на машине IBM 370 с использованием одинарной точности вычислений М нимальная добавка, которая приведет к изменению единицы в операции сложения с плавающей запятой, равна машинной точности ej. Для IBM 370 этим порогом является ед,= 16-5я!0.95х 10"". Он и был взят в качестве первого значения h. Кроме того, расчеты выполнены еще для четырех значений. Каждое последующее было больше преды ущего в десять раз. Данные расчетов приведены в табл. 4а. Ее первые три колонки содержат пробные значения h н вычисляемые в точках .v=l н x-\-h значения функции (4.54). В четвертую колонку записаны модули \T(h)\ ошибок отбрасывания. Они найдены при разных h для аналитических оценок фр(Л), вьмисленных по точньш (подсчитанньтм с двойной точностью) значениям функции. В пятой колонке представлены модули ошибок условий, которые рассчитывались с использованием аналитических оценок фу. Наконец, шестая колонка содержит численные оценки фу(/, h). Истинная величина производной f{x) (округленная до шести значащих цифр) равна 0.954866 X 10.

В идеале конечно-разностный интервал h следовало бы выбрать так, чтобы уклонение оценки фу (/, h) от настоящей производной было минимально, т. е. нз решения задачи минимизации суммы ошибок условий и отбрасывания. В частности, для примера 4.9 иэ табл. 4а видно, что оптимальное значение h лежит между 100 и 1000 ejij. Однако в реальных процедурах оценивания производных таких таблиц не составляют, и величины, фигурирующие в (4.51) и (4.53), остаются неизвестными (так как если бы знать истинное

Таблица 4а. Ошибка условий и ошибка отбрасывания в tfp при Еуи =0.953674x10-"

значение производной и иметь возможность вычислений с повышенной точностью, как это было при построении табл. 4а, то заниматься подбором h было бы незачем). Поэтому отыскать значение h, доставляющее минимум содержащейся в Фу ошибке, не удается.

На практике конечно-разностный интервал подбирают из соображений минимизации вычислимой оценки суммарной ошибки.