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

[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]

чает, что д,1я определения оптимума с приемлемой точностью понадобится число итераций, кратное п с солидным множителем, а для большой задачи иногда и 2п итераций уже недопустимо много. На наш взгляд, применение метода соггряженных граднентов следует считать успешным, когда удовлетворительное решение удалось получить менее чем за 5п шагов.

Если собственные значения матрицы Гессе функции F в точке ее минимума распадаются на небольшое число групп, в каждой из которых их разброс невелик, метод сопряженных градиентов может иайти хорошее решение значительно быстрее, чем за п итераций. Так бывает для некоторых штрафных функций, используемых при решении задач с нелинейными ограничениями (см. разд. 6.2.1). Что же касается функций, не обладающих указанным свойством, то для их минимизации обычно требуется от п до 5п итераций, причем чаше всего хватает 2п итераций. В заключение следует сказать, что, хотя схема сопряженных градиентов далека от идеала, на сегодня она является единапвенньш разумным универсальным средством решения задач безусловной минимизации с очень большим числом переменных.

•4.8.4. КВАЗИНЬЮТОНОВСКИЕ МЕТОДЫ С ОГРАНИЧЕННОЙ ПА.У1ЯТЬЮ

В этом разделе мы рассмотрим методы, в которых правильная ориентация направлений поиска обеспечивается при значительно менее жестких требованиях к выбору шага, чем в нелинейном методе сопряженных градиентов. Они называются кеазиньютонов-ашми с ограниченшш памятью. Объединяет их идея использования в качестве р,, произведения -Mgs, где М - положительно определенная матрица, полученная из единичной ограниченным числом квазиньютоновских корректировок по какой-нибудь формуле для аипрокси.мации обращенной матрицы Гессе. При этом М никогда не формируется явно. В памяти машины хранятся только векторы, определяющие квазиньютоновские поправки, и этого вполне достаточно для вычисления произведений М на g.

Чтобы задать конкретый метод рассматриваемого типа, надо выбрать конкретную квазиньютоновскую формулу и зафиксировать число запоминаемых поправочных векторов. Мы приведем в качестве примера «одношаговый метод», построенный на основе BFGS-формулы. В нем матрица М для очередной итерации гюлу-чается из единичной однократным пересчетом в соответствии с результатами предыдущего шага. Вектор рд в этом методе вычисляется так;

P» = -eft-f-(sLi&I/s ,--l/f i&S*-,) -

Нетрудно проверить, что прн точной одномерной минимизации направления рд нз (4.95) оказываются теми же, что и в методе соггряженных градиентов; когда s igj=0, формула (4.95) переходит в (4.89). Таким образом, квазиньютоновскне методы с ограниченной памятью могут генерировать сопряженные направления, причем точный одномерный гюиск .здесь по существу. Чтобы убедиться в последнем, заметим, что независимо от выбора квазиньютоновской формулы матрица М будет обеспечивать равенство s , = A!j/j , (см. разд. 4.5.2.2). ЗнаЧ1гг. с учетом определения вектора рд имеем

yk-,Pn = - yL,Mg, - sl.,gi,.

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

Важное достоинство квазиньютоновских методов с ограниченной памятью состоит в том, что в них легко добиться правильной ориентацин векторов р; гарантировано, что р, будут направлениями спуска, если скалярные произведения yj .ч положительны для всех пар i/y и из формулы пересчета. Это в свою очередь обеспечено, если для выбора шага приь-еняется алгоритм, который приводит к уменьшению модуля производной вдоль направления поиска (см. разд. 4..3.2.1).

4.8.5. МЕТОДЫ СОПРЯЖЕННЫХ ГРАДИЕНТОВ С УЛУЧШЕНИЕМ ОБУОТОВЛЕННОСТИ

4.8.5.1. Квадратичные функции. Допустим, что требуется решить систему Сх=-с, где G - положительно определенная матрица, и предполагается использовать для этого линейный метод сопряженных градиентов. В разд. 4.8.3.2 было указано, что при абсолютно точных вычислениях он найдет решение за чнспо шагов, равное числу различнь1х собственных значений матрицы С. Поэто.му реальная скорость сходимости метода существенно повысится, если исходную систему заменить эквивалентной, но с матрицей, имеющей много единичных собственных значений. Идея предварительного улушиения обусловленности и состоит в то.м, чтобы осуществить преобразование С такого рода.

Соображения, лежащие в основе реализации предлагаемого подхода, заключаются в следующем. Пусть W - положительно определенная матрица. Тогда вектор х, удовлетворяющий равенству Gx=-с, можно найтн. решив систему вида

W--4CW--4 y = --W-lc (4.96)

и положив х=~у. Обозначим матрицу этой системы через Поскольку W-4RW4 = W-C, у R будут те же собственные числа, что и у матрицы l-G (см. разд. 2.2.3.4).



Значит, чтобы «облегчить работу» методу сопряженных градиентов, надо постараться подобрать W так, чтобы как можно больше собственных значений WC лежало вблизи единицы, и заменить исходную систему на (4.96). Не претендуя на строгость, можно сказать, что W подбирается .здесь с целью минимизации числа обусловленности матрицы W~G.

Вычислительную процедуру поиска решения системы Gx = -c применением линейного метода сопряженных градиентов к (4.96) организуют таким образом, что в расчетах используется только матрица U7, а W4 не нужна. Чтобы понять, как это делается, надо выписать формулы, подобные (4.91) для системы (4.96), обозначив вектор переменных через и, невязки через Чд, а направления через ш,. Затем надо умножить уравнения для пересчета переменных и направлений на а уравнение для пересчета невязок на W"/" и заменить W"Ui, на Хд,К-"Шд на р, а W4bt на г. Результатом будет следующий алгоритм: задав х„, вычислив c--Gx„ и положив р , =0, р , =0, для ft = 0, 1, ... найти

Рк ОРк

Xk*i = 4 + akPk, (4.97)

•<,+1 = -д-(-«(,Срд;

Определяя алгоритм решения системы Gx=-г, формулы (4.97) одновременно задают алгоритм поиска минимума квадратичной функции гх--VsXCx. Прн такой интерпретации эти формулы лучше переписать иначе, с тем чтобы их можно было применять и для минимизации нелинейных функций об1цего вида. Соответствующее правило расчета направления рд будет звучатЁ так; для вычисления р надо решить систему

после чего взять

Pk = k + tk-iPk-u где h-.\~yl-klyk-,Pk-f При переходе к нему от (4.97) учтено, что Гд = д, что направления Pj в (4.97) взаимно сопряжены относительно G и что к, в (4.97) есть шаг в точку минимума вдоль Рд.

.Матрицу W, «улучшающую обусловленность», можно определять по-разному. Например, можно сразу строить обратную к ией матрицу W~*, используя какой-нибудь квазиньюгоновскнй метод с ограниченной памятью. В результате г(г<?[) итераций такого метода

МЫ получим матрицу М, удовлетворяющую квазиньютоновскому условию для г пар векторов (s, у,}, т. е. каждая нз этих пар будет связана равенством Sj-Myj. При этом для матрицы Гессе минимизируемой квадратичной формы инеем GSi=4/y, и, следовательно, Sj=MGSj.

Таким образом, матрице MG обеспечено по меньшей мере г единичных собственных значений, что и позволяет рекомендовать М на роль W-K

4.8.5.2. Нелинейные функции общего вида. Изложенный выше метод сопряженных градиентов с улучшением обусловленности непосредственно обобщается на задачи минимизации нсквадратич-ных функций. Формулы расчета направлений останутся прежними, только матрица W будет меняться от шага к шагу. Точнее говоря, вместо W в системе для расчета г/, будет фигурировать W. Как и в квадратичном случае, можно сразу строить Wk, используя какой-нибудь квазиньютоновский метод с oi-раниченной памятью. Однако это - довольно сложный прием. Более простои и успешно применнемьи"! способ построения U опирается на идею диагонального масштабированпя.

В данном разделе речь идет о задачах, к которым обычные квазиньютоновские методы не применимы: мы считаем, что для записи ква;*иньютоновскнх приближений в ггамяти машины не хватает места. Однако люжно хранить и пересчитывать от шага к шагу только диагональные элементы В. Сами по себе они не дают возможности строить хорошие направления поиска, но составленная у них матрица вполне пригодна на роль й,. Обозначим через tj и 4l>y /-е элементь векторов р„ и у соответственно, а через Af = diag(6„ 6„) н At , = diag(6„ 6„) приближения диагонали матрицы Гессе на k-{[ и к-1-й итерациях. Тогда переход от Дд 1 к Ад мог бы выглядеть так:

к 6,6,+-у) +--ч?.

gk-iPk-1 =e-iW-iP»-i

Это соотношение получено из BFGS-формулы (4.37) и совместно с уравнением

Адгд=-g-ft

для расчета гд задает один нз методов сопряженных градиентов с диагональным масштабированием. При его реализации следует предусмотрегь контроль положительности диагональных элементов Ад н «замораживать» нх значения, когда пересчет дает отрицательные величины.

Мы предложили для вычисления Дд иметшо BFGS-формулу не случайно. Она ближе друпгх методу сопряженных гралиеитов, так как в квадратичном случае при точном одномерном поиске они



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

Диагональное масштабирование применимо и в квазиньютоновских методах с ограниченной памятью. Здесь матрицы Лд могут использоваться вместо единичной в качестве начальных матриц циклов квазиньютоновских корректировок. Например, одношаговый BFGS-мегод с диагональным масштабированием определяется формулой вида

Pft = -+ -

где g„ = Ag

4.8.6. РЕШЕНИЕ НЬЮТОНОВСКИХ УРАВНЕНИЙ ЛИНЕЙНЫМ МЕТО.ТОМ СОПРЯЖЕННЫХ ГРАДИЕНТОВ

Встречаются ситуации, когда вычислить большую разреженную матрицу Ol, нетрудно и разместить ее в памяти машины можно, 1Ю применить для решения ньютоновской системы какой-нибудь метод с матричной.факторизацией нельзя (см. разд. 4.8.1). Бывает и так, что явно формировать Од непрактично, но организовать эффективный расчет произведения Од на любой вектор легко; к примеру, если Сд представляет собой произведение нескольких разреженных матриц, то сама она может оказаться плотной и не поместиться в память, хотя для хранения сомножетелей места хватит; трудностей с вычислением произведений Од на векторы при этом не будет. И в том и в другом случае окончательно отказываться от ньютоновской схемы мтшимизации не обязательно.

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

G„lh=-gk. (4.98)

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

для расчета направления поиска осуществляется только о;шн шаг метода (4.91), вектор Рд будет равен антнградиенту -g; если же проделать п шагов, то рд (в отсутствие ошибок округления) будет точным решением системы (4.98). Значит, напраатение поиска в усеченном методе Ньютона, использующем процедуру (4.91), лежит «между» антиградиентом и обычным ньютоновским направлением. Когда матрица Од положительно отфеделена и начальным приближением в лтшейном методе сопряженных граднентов служит -gt, все последующие приближения будут направлениями спуска.

Усеченный метод Ньютона эффективен только тогда, когда малого количества итераций метода сопряженных традиентов хватает для определения хорошего направления поиска. Поэтому здесь особое значение приобретает оггисанная в разд. 1.8.5.1 техника предварительного улучшения обусловлентюсти. и она важна не только как средство повышения скорости сходимости метода сопряженных градиентов. Применение этой техники по сути дела означает, чти прн построении усеченного метода Ньютона мы будем «отталкиваться» от алгоритма с расчетов] направлений спуска по формуле Рд=-Mgk, где М - некоторая положтгтельно определенная матрица. Точный смысл сказанного заключает-ся в том, что первым приближением в линейном методе сопряженных граднентов будет вектор -Мрд, и если, например, матрица М определяется каким-нибудь квазиньютотювским ыетодо.м с ограниченной памятью, этот вектор скорее всего окажется значительно лучшим направлением спуска, чем аитиградтгент. Поэтому и последующие приближения будут намного лучше, чем при обращении к обычному лтшейному методу сопряженных градиентов, прттчем независимо от того, насколько сильно введение М повлияет на скорость сходимости этих приближений. В данном случае усеченный метод Ньютона будет представлять собой нечто среднее между классическим методом Ньютона и квазиньютоновским алгоритмом с ограниченной памятью, при.меняемым для построения матриц М.

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

Идея адаптации квазиньютоновской схемы к задачам большой размерности принадлежит Шуберту (1970), который первым предложил модификации обычных квазиньютоновскнх формул, позволяющие строить разреженные поправочные матрицы. Иной вывод аналогичных формул дали Авила и Конкус (1979). Задача (4.74) для определения симметричных разреженных поправок была поставлена Пауэллом (1976а) и независимо решена Тойнтом (1977) и Марви-лом (1978). Способ вывода «разреженных» аналогов квазиньютоновских формул однопараметрического семейства (4.35) получил Шанно (1980); Тапа (1979) существенно упростил построения Шанно и обобщил нх для более широкого класса формул. Дальнейшие сведения



[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.0012