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

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

Рассуждения, подобные использованным в предыдущем примере, здесь приводят к такому гладкому аналогу:

найти

2 г,

mm хея": г. seffl" при ограничениях М = г,-s,-, /•,>0; s,.>0.

= 1, 2, m; = 1, 2.....т.

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

Задачи и It обычно возникают из псггребностей согласования данных, и поэтому для них характерны «малые» оптимальные значения минимизируемых сумм. Если же минимум просто равен нулю, то соответствующую точку можно искать как решение гладкой задачи о наименьших квадратах:

найти min S fi (х).

Когда минимум в задаче или li «мал», но все же отличен от ну.чя, его можно попытаться определить, решая серию задач вида

найти min 2 Ш;/ (х).

(4.5)

Для них разработаны специальные алгоритмы (см. разд. 4.7).

Обозначим через x оптимальную точку в задаче (4.5), н пусть И)/= 1/т, 1=1, ...,т. Тогда формула построения послег довательности весов в (4.5) для /, будет выглядеть следующим образом:

uuf+" = i (х<*)

Здесь 5= 2/П*) ti** и соответственно 2tf" = l. Анало-

i= 1 i=i

гичная формула для задачи Zi такова:

в ней 5=2 1/Л-(х*) (предполагается, что значения (х") отличны от нуля при всех t). Чаще всего двух-трех итераций

по k оказывается вполне достаточным, чтобы получить приемлемые решения исходных задач.

И в случае с /„, и в случае с Zj нет нужды очень точно определять промежуточные значения х". Поэто1,;у число итераций, необходимых для отыскания пригодной точки ic", обычно невелико. Время, затрачиваемое на решение задач (4.5), сокращается еще и потому, что х:*, как правило, оказывается хорошим начальным приближением для поиска х*"*.

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

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

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

Изложенный выше метод многогранника представляет собой модификацию алгоритма Спендли, Хекста и Химсворта (1962), сконструированную Нелдером и Л1идом (1965). Иные модификации читатель найдет в работе Паркинсона и Хатчинсона (1972). Достаточно полный обзор прочих методов прямого поиска содержится в работе Свэна (1972).

Методы решения задач минимизации составных функций были предметом активных исследований последних лет. О них еще пойдет речь в разд. 6.8, где будут даны соответствующие ссылки. Схема решения задач Zi и с линейными путем последовательного поиска минимумов взвешенных сумм квадратов предложена Лоуео-ном (см. Лоусон н Хансон (1974)).



4.3. МЕТОДЫ для ГЛАДКИХ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ

4.3.1, МОДЕЛЬНАЯ СХЕМА МИНИМИЗАЦИИ ГЛАДКИХ ФУНКЦИЙ

В этом разделе рассматриваются методы безусловной минимизации даажды непрерывно дифференцируемой функции F(x) векторного аргумента х.

Для разработки любого оптимизационного алгоритма принципиальное значение имеет выбор меры прогресса при переходе от одного приближения к другому. Понятно, что, конструируя итеративный метод, важно иметь некоторое разумное правило, по которому будет выноситься суждение о том, «лучше» новая точка предыдущей или нет, а такое правило предполагает наличие указанной меры. Эта мысль красной нитью пройдет через все последующее изложение. Для задач безусловной минимизации естественной мерой прогресса служит приращение целевой функции. Представляется разумным требовать, чтобы F убывала на каждой итерации, т. е. соблюдалось условие спуска, состоящее в том, что f ft+i<f t для всех /г>0. Методы, которые удовлетворяют этому требованию, называются методами спуска. Именно они будут предметом обсуждения в оставшейся части данной главы.

Все представленные ниже методы укладываются в рамки следующей модельной схемы:

Алгоритм L] (модельная схема решения п-мерных задач безусловной минимизации). Имея текущее приближение х искомой точки X*, на очередной итерации надо выполнить следующие дейсгвия:

U1. [Проверка соблюдения условий останова.] Проверить условия останова и, если онн выполнены, вычисления прекратить и взять х в качестве искомого решения; в прсггивном случае перейти к следующему шагу.

U2. [Расчет направления поиска.] Рассчитать ненулевой п-мерный вектор называемый направлением поиска.

из. [Расчет длины шага.] Вычислить положительное число (длину шага), обеспечивающее неравенство F(Xf.-)raPk) <i <F(x,).

U4. [Пересчет оценки решения.] Положить x+i i-x-f-apj, ft <-ft-I-1 и вернуться к шагу Ul.

Важно отметить, что шаг U3 в модельной схеме предполагает решение некоторой одномерной задачи (определения скаляра а,,).

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

спуска в Хь, т. е. у.цовлетворял неравенству gkph<0. Здесь и в дальнейшем через g,, обозначается вектор g(Xt). Точно так же через f ft, Gft впредь будут обозначаться f (xs) и G(Xft) соответственно. Когда Pi,- направление спуска, неравенство f(Xj-fapt)< <iF(Xf,) выполнится при любом достаточно малом положите.чьном а (см. разд. 3.2.2).

4.3.2. СХОДИМОСТЬ МОДЕЛЬНОЙ СХЕ.ЧЫ

Прежде чем перейти к конкретным методам, рассмотрим условия, при которых последовательность, генерируемая по модельной схеме, сходится к точке х*. в которой градиент g{x*) равен нулю. Строгий анализ сходимости выходит за рамки данной книги, так что мы ограничимся краткой сводкой соответствующих результатов. Подробные доказательства читатель найдет в литературе, ссылки на которую даны в конце раздела,

В модельной схеме значение минимизируемой функции F монотонно убывает. Однако неравенства f i,+i<fсами по себе еще ие обеспечивают сходимости последовательности {Xft) к точке минимума F. Это видно из примера с функцией х и последовательностью точек V2-b2-*. Из fs + ,<fft и ограниченности F (х) снизу вытекает только одно - существование предела последовательности {F/,}. Совпадет ли этот предел с F (х*) нли нет, не ясно.

Строго монотонно убывающая последовательность {fj,}, генерируемая по модельной схеме, может не сойтись к .минимуму по двум причинам. Во-первых, как бы ни выбиралось направление pj, все можно испортить неудачным способом построения шагов и, назначая нх так, что величины убывания F по итерациям будут слишком быстро стремиться к нулю. Во-вторых, решения не получить, если метод расчета направлений Pt выдает векторы, вдоль которых функция F почти постоянна. Последнее означало бы, что направление р почти касательно к линии уровня f (x)=fft, т. е. gh и Рй почти ортогональны (величина -glpiJ(\\gi,\\i\\Ph\\i) близка к нулю). Значит, если мы хотим получить гарантированно сходящуюся процедуру, надо позаботиться о том, чтобы выбор а,, обеспечивал «существенное убывание» F на каждой итерации и чтобы угол между направлением рц и градиентом gh всегда отличался от прямого не менее, чем на некоторую фиксированную ненулевую величину.

В доказательстве сходимости модельной схемы кроме двух сформулированных выше условий оговаривается некоторое необременительное требование к функции F. Огносится оно к ее множеству уровня. Соответствующее определение звучит так: для данной функции F и числа р множеством уровня i(fl) называется совокупность всех точек х, удовлетворяющих неравенству f (хХР. Требование же, о котором идет речь, состоит в том, что множество L {F (Хо)) должно бьпъ ограниченным и замкнутым. Везде в этой главе будет



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

Итак, если (i) функция F дважды непрерывно дифференцируема, (ii) множество уровня L(F(Xo)) замкнуто и ограничено, (iii) F «существенно убывает» на каждой итерации и (iv) при всех k угол между и градиентом отличается от прямого не менее чем на фиксированную ненулевую величину, то алгоритм U генерирует последовательность точек, для которой

Иш lgjl = 0.

fc-1-СО

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

4.3.2.1. Вычисление длины шага. Качество процедуры выбора шага в методе спуска оценивается тем, какое изменение функции он обеспечивает на каждой итерации. В частности, для сходимости нужно, чтобы шаг приводил к «существенному убыванию» F. Этому требованию можно удовлетворить, подчиняя специальным ограничениям. Известно несколько наборов таких ограничений. Например, существенное убывание F обеспечено, если для выполнены условия Гольдштейна - Армийо:

О <-Hiasgfpt < F-F+i <-V-Ji£lpi,-

Здесь pi. Pa- числа, удовлетворяющие неравенствам 0<pi<Ha<l. Двусторонние ограничения иа в (4.6) гарантируют, что шаг будет и не «слишком малым» и не «слишком большим».

Вычисляя шаг на основании правила (4.6), обычно его представляют произведением некоторой начальной оценки а" на степени положительного параметра w. В результате а** находится

как первый нз элементов последовательности {да.а"}, / = 0.....

для которого выполняется неравенство (4.6).

Эффективность описанной процедуры расчета шага в конкретных алгоритмах сильно зависит от выбора оценки а*"*. Типичны реализации с а"=1, причем это объясняется не тем, что именно такая оценка дает максимум вероятности удовлетворить (4.6) с первой попытки, а тем, что она лучше других согласуется с ньютоновскими и квазнньютоновскими способами задания направлений спуска (см. разд. 4.4 и 4.5). В общем получается, что процедура хороша лишь тогда, когда назначаемая априори величина а°, как правило, будет хорошим шагом н другие элементы последовательности {цуа*"} часто просматривать не придется.

Мы хотим подчеркнуть, что само по себе условие (4.6) еще не служит гарантией качества шага, н, когда речь идет о выборе хорошего а"", имеется в виду нечто большее, чем выбор с единствен-

ной целью удовлетворить этому условию. Для большинства возникающих на практике задач значение «» = 10"? удовлетворяло бы ему при разумных р, и jij на всех итерациях (т. е. подходящий шаг «1, устанавливался бы ценой вычисления лишь одного значения функции), и тем не менее при любом из используемых правил расчета направлений спуска задание такого а*" было бы исключительно неэффективно. Следовательно, работу процедуры выбора шага нельзя оценивать только по количеству вычислений функции, требуемых для достижения условий, гарантирующих сходимость. Обязательно нужно учитывать полное уменьшение функции на каждой итерации. К сожалению, излишне увлекаясь теоремами сходимости, об этом нередко забывают.

Каков бы нн был критерий прнемлеьюстн (имеются в виду ограничения типа (4.6)), обычно он задает некий диапазон подходящих значений, одни из которых «лучше», а другие «хуже». Интуиция подсказывает, что «лучшими» следует считать те значения, которые приводят к большему изменению F. Сможет ли алгоритм расчета длины шага эффективно отыскивать «хорошие» в этом смысле ctft, зависит как от способа генерирования в нем пробных шагов, так и от ограинченнй, налагаемых на из соображений сходимости.

Понятно, что повышение качества выбора шагов на итерациях метода спуска всегда будет связано с какими-то дополнительными условиями, и эти усилия оправданны только до тех пор, пока они с лихвой окупаются увеличением эффективности итераций. В равновесии, к которому следует стремиться, ни упрощение, ни усложнение процедуры определения не должны приводить к улучшению функционирования метода в целом. Точка такого равновесия меняется от метода к методу и даже от задачи к аадаче. Поэтому нужны разные способы вычисления, и в частности разные критерии приемлемости а. Один нз таких критериев (правило (4.6)) мы уже рассмотрели. Теперь перейдем к критериям иного сорта, согласованным с интерпретацией задачи выбора шага как задачи на поиск одномерного минимума. Иногда желательно или даже существенно, чтобы шаг «1, бьш хорошим приближением точки минимума функции F вдоль направления р. Во-первых, это обеспечивает «существенное» уменьшение F. а, во-вторых, высокая скорость сходимости многих методов спуска достигается только в том случае, когда шаг выбирается именно этим способом. Практичный критерий приемлемости шага ttft как приближенного решения задачи одномерной минимизации состоит в требовании, чтобы модуль производной функции F по направлению р в точке xj-\-akPk был существенно меньше, чем в Xt,:

1 g (Ч +tPtV Рк I <-r\elPf (4.7)

Здесь Г) - число из диапазона 0<1K1, определяющее точность, с которой «ь аппроксимирует стационарную точку F вдоль р. Варьируя значение г), мы можем тем самым управлять трудоем-



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