Главная  Методы условной оптимизации 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [ 30 ] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

будет

(.LA+i+Mt+i)s» = </ft.

Здесь 8 = хд+,-и yt = JLih+i-Jkfk- Заметим, что матрица /Ид+, зависит от

Процедуру вычисления матриц можно строить на основе любой из формул пересчета, рассмотренных в разд. 4.5.2, В частности, если исходить из BFGS-формулы (4.36), получим

= М,--W,s,slW,+ -4- уЛ. (4.66)

где W, = yLA., + Wt.

Если матрица Jl+iJk+i + M положительно определена, то при вычислении Мд+, по формуле (4.66) матрица тоже будет положительно определенной. Это свойство (4.66) полезно в асимптотическом плане. Оно означает, что на поздних итерациях метода, когда J и Уд мало отличаются друг от друга, сохранность положительной определенности матрицы системы для расчета направления поиска обеспечена. Однако в начале счета, пока до решения далеко, матрица JlJ--M может получаться знаконеопределенной, и соответственно должны быть предусмотрены какие-то корректировки, которые гарактировали бы, что всегда будет найдено направление спуска.

Некоторые из методов с квазиньютоновской аппроксимацией матрицы Q{x), как и их универсальные прототипы, теоретически сходятся сверхлинейно. Однако свойсшами сохранения положительной определенности и п-шаговой сходимости в квадратичном случае эти методы не обладают. Причина - использование квазнньютоновской техники только для одной составляющей матрицы Гессе. Трудности увязки точной и приближенной информации о кривизне объясняют также, почему алгоритмы с квазинькетонов-ской аппроксимацией Q(x) на практике почти никогда не сходятся так быстро, как их универсальные аналоги.

*4.7.5. СКОРРЕКТИРОВАННЫЙ МЕТОД ГАУССА - НЬЮТОНА

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

Рассмотрим разложение матрицы по особым числам;

Здесь S = diag(Oi, щ.....о„)-матрица, диагональные элементы

которой упорядочены таким образом, чтоо,-а,-+ (1/«-1); и-ортонормальная mxm-матрица; V-ортонормальная пхп-матрица. Подставив это выражение для Уд в ньютоновскую систему (4.60) и сократив полученное равенство на невырожденную матрицу V, мы придем к системе вида

(4.67)

где через / обозначен вектор, составленный из первых п компонент т-мерного вектора У/д. Уравнение Гаусса-Ньютона (4.61) получится, если пренебречь в левой части (4.67) матрицей VQV. Таким образом, вектор Рдд, будет удовлетворять равенству

Если матрица S невырождена, отсюда следует, что Po, = -VS-l

Трудности с методом Гаусса-Ньютона возникают тогда, когда матрица Сд «существенна», например когда матрица /д имеет дефект ранга (т. е. S вырождена) или в задачах с большой невязкой. Чтобы избежать нх, не надо пренебрегать матрицей (Зд в тех скалярных уравнениях ньютоновской системы, где составляющая УУд не доминирует. На этом принципе и строится скорректированный метод Гаусса-Ньютона. В нем на каждой итерации определяется целочисленный параметр г (Огп), который, грубо говоря, равен количеству скалярных уравнений из (4.67) с «доминирующими» особыми числами. Таковыми, естественно, считаются первые г иэ них (поскольку особые числа упорядочены по убыванию), т. е. система (4.67) разбивается на первые г и последние п-г уравнений. В соответствии с данным разбиением каждый из объектов в (4.67) тоже распадается на две части: матрица V-на матрицу (состоящую из первых г столбцов V) и на матрицу (состоящую из последних п-г столбцов); матрица S-на диагональную матрицу S, равную diag(a„ ..., о, (где а,. > 0), и на матрицу diag (o,+i, ...,о„); вектор /-на fi и f, состоящие нз первых г и последних п-г компонент /.

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

Р« = .Р1 + Л- (4-68)

Подставив это выражение для р, в первые г скалярных уравнений из (4.64), получим

(Sl-i-VIQ,V\) р, + V[ (Зд1/,р, = -



Если предположить, что все коэффициенты данной системы, связанные с Сд, имеют порядок 0(e), где е - малое число, то, пренебрегая ими, мы придем к системе, определяющей приближение вектора pi с точностью до 0(е). Ее решением является

Pi = -Sr7i.

Отвечающий ему вектор У.р, называют направлением Гаусса - Ньютона в подпространстве, порождаемом V.

Подставим теперь выражение (4.68) в последние п-л скалир-ных уравнений из (4.67). Результатом будет система вида

VIQkViPxJ- {Si + VTQ.V,) р, = - S/,. Замена в ней р, на Pi приводит к векторному уравнению для расчета приближения р„ аппроксимирующего р с точностью до 0(e). Это уравнение выглядит так:

{Si + VIQ,V,) р, = - Sj- ПСдКй. (4.69)

Его решение р, в.месте с р определяет вектор

именуемый скорректированным направлением Гаусса - Ньютона. При г=0 этот вектор есть не что иное, как обычное ньютоновское направление (4.68), а при г=п он будет обычным направлением Гаусса - Ньютона. Стало быть, в общем случае Рс есть нечто промежуточное между ньютоновским направлением и направлением Гаусса - Ньютона.

В скорректированном методе Гаусса - Ньютона параметр г обновляется на каждой итерации. Выбор его очередного значения связывается с тем, удалось ли на предыдущем шаге спуска получить удовлетворительное уменьшение функции. Правила пересчета могут быть разными, но в основу всегда закладывается тенденция к увеличению г. Выбор г существенно определяет р и в то же время достаточно произволен, т. е., казалось бы, здесь возникают теже проблемы, что и с оценкой ранга в методе Гаусса - Ньютона. Аналогия действительно есть, но благодаря реальной возможности подстройки значений г по результатам спуска вопрос о назначении г в скорректированном методе Гаусса- Ньютона стоит далеко не так остро, как вопрос об оценке ранга матрицы /д в обычном методе.

Возможны три разновидности скорректированного метода Гаусса - Ньютона. Во-первых, если доступны аналитические значения вторых производных, можно использовать в расчетах сами матрицы (Эд; во-вторых, можно отказаться от вычисления аналитических вторых производных и применять конечно-разностные приближения матриц QitVz, конструируемые по приращениям градиента вдоль столбцов V,; в-третьих, можно вместо матриц (Зд брать их квазнньютоноБСкие приближения. В любом случае решение сис-

темы (4.69) (или (4.67), если г=0) следует искать каким-нибудь алгоритмом типа модифицированной факторизации Холесского (см. разд. 4.4.2.2), который позволял бы при необходимости «подправлять» его, с тем чтобы в результате получалось направление спуска.

4.7.6. НЕЛИНЕЙНЫЕ УРАВНЕНИЯ

Задача о наименьших квадратах (как и любая задача безусловной минимизации) очень близка к задаче поиска корня системы нелинейных уравнений, т. е. точки х*, в которой некоторая п-мер-нан векторная функция f{x) обращается в нуль:

f{x*)=0. (4.70)

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

Решение произвольной нелинейной системы (4.70) можно искать методом Ньютона, который для векторного случая строится Б точности по той же схеме, что н для скалярного (см. разд. 4.1.1.2). Из тейлоровского разложения функции / в окрестности текущего приближения Хд мы получаем ее линейную аппроксимацию. Последняя удовлетворяет в искомой точке х* приближенному равенству

/(х*)«:/(Хд)-Ь/(хд) (х*-хд). (4.71)

Отсюда и выводим правило расчета ньютоновского шага р,. Он представляет собой оценку разности х*-Хд, получающуюся приравниванием правой части (4.71) к нулю. Таким образом, р„ будет решением аналогичной (4.1) и (4.17) системы уравнений вида

J(Xk)PN=-f{Xh), (4.72)

а очередным приближением в методе Ньютона для решения (4.70) будет Xд.l=Xд-fP.V. При обычных предположених относительно невырожденности матрицы J{x*) и близости начального приближения Хо и X* последовательность {хд}, генерируемая описанным способом, квадратично сойдется к х*.

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

Задача поиска решения системы нелинейных уравнений - это классическая задача вычислительной математики, а для нее разработано большое число специальных алгоритмов. Многие среди них опираются на ньютоновское уравнение (4.72). Однако для решения (4.70) можно использовать и методы минимизации суммы квадратов - ведь ясно, что х* из (4.70) является точкой минимума

t М 2вв4



функции (4.58). Правда, если матрица J{x) может вырождаттл-я, ие исключено, что оптимизационный метод сойдется в точку х локального минимума функции (4.58), где ее градиент J{xYf(x) равен нулю, но значение f(x) окажется ненулевым. Поэтому без нужды обращаться к такому методу не следует. И все же в ряде случаев оптимизационный подход предпочтительнее, например, когда есть риск, что определение нелинейной системы (4.70) содержит погрешности, из-за которых у нее, возможно, не будет точного решения, хотя минимальная невязка заведомо мала. Что же касается выбора среди оптимизационных методов, то здесь надо учтггывать два фактора - эффективность метода при m=n и наличие в нем средств, позволяющих избежать трудностей, связанных с «квадратичным» ухудшением обусловленности при переходе от (4.72) к (4.61).

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

Обишй обзор мегодов решения нелинейных задач о наименьших квадратах читатель найдет в работах Денниса (1977), Рэмзина и Ведина (1977).

Метод Гаусса - Ньютона подробно рассматривался многими авторами, в том числе Бен-Израэлсм (1967), Флетчером (1968) и Ведином (1974). О его недостатках писали Пауэлл (1972), Гшш и Мюррей (1976а). Идея применения (ЗК-факторизации для решения линейных задач о наименьших квадратах принадлежит Бузингеру и Голубу (1965). Связь между задачей о наименьших квадратах и псевдообратными матрицами обсуждается в статье Петерса и Уилкинсона (1970). Основные сведения относительно разложений матриц по особым значениям можно почерпнуть из работ Голуба и Райнха (1971), Лоусона и Хансоиа (1974). Возможность применения методов сопряженных градиентов (см. разд. 4.8.5) для учета составляющей матрицы Гессе от (4.58) со вторыми производными функций и выше не рассматривалась; впервые на нее указал Рухе (1979),. который предложил восполыюваться ею как средством «ускорения» метода Гаусса - Ньютона.

Алгоритм Левенберга - Маркардта был независимо сформулирован Левенбергом (1944) и Маркардтом (1963). Деталями его реализации занимались многие. Флетчер (1971а), например, построил процедуру подбора значения параметра Хд в (4.65) в зависимости от отношений между фактическими изменениями функции в результате пробных шагов н ожидаемыми величинами этих изменений. Есть и другой способ реализации схемы Лененбергн - Маркардта, когда подбирается Л, а при заданном А вычисляется версией метода Хебдена, специально приспособленной для задач о наименьших квадратах (см. Хебден (1973), Море (1977) н замечания к разд. 4.4).

Описания квазиньютоновских методов минимизации суммы квадратов пртшодятся в работах Денниса (1973), Бетса (1976), Денниса, Гэя и Уэлша (1977), Гилла и Мюррея (1978а). Авторами скорректированного метода Гаусса - Ньютона являются Гилл и Мюррей (1978а).

Среди прикладных задач о наименьших квадратах нередко встречаются задачи с функциями {fi) специального вида. Например, может оказаться, что все {/(} линейны по части неременных, либо структура матрицы Якоби будет такой, что задачу удастся преобразовать в несколько независимых подзадач меньшей ра:тмерности. В таких случаях имеет смысл обращаться к специальным методам. В их числе можно упомянуть методы решения сепарабельных задач о наименьших квадратах, впервые предложенные Голубом и Перей-рон (1973). Другие ссылки на методы этого типа можно найтн в работах Кауфмана и Перейры (1978), Рухе и Ведина (1980),

По методам решения систем нелинейных уравнений стцеству-ет обширная литература; см., например, Бройден (1965), Пауэлл (1970b). Боге (1975), Брент(1973Ь),Гэн иШнабель(1978),Море(1977).

4.8. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ БОЛЬШОЙ РАЗМЕРНОСТИ

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

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

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



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [ 30 ] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.0016