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

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

На рис. 6j показаны линии уровня функции (6.24) для задачи из примера 6.2 (ограничение которой трактуется как равенство) при трех значениях Х(?.=0.5, Х=0.9 и >.= 1.б). Параметр штрафа был взят равным 0.2. Такой выбор р обеспечивает наилучшую обусловленность функции (6.24) с Х-=>.*. Из приведенных фрагментов


Рис. 6i. Линии уровня модифицированных функций Лагранжа L.i(x. Я*, р) с р=0.075. р-0.2 и р= 100 для задачи иэ примера 6.2 с ограничением, трактуемым как равенство.

видно, как сильно иногда влияют на характер поведения модифицированной функции Лагранжа даже малые вариации оценок множителей.

Можно показать, что приближения {х} из модельной схемы разд. 6.4.2.1 будут сходиться к х* не быстрее, чем оценки {к] к


Рис. 6j. Линии уровня модифицированных функций Лагранжа Ljix, %, р) с Я=0.5, Л=0.9 и Я=1,0 для задачи из примера 6.2 с ограничением, трактуемым как равсисгео.

X*. Отсюда, в частности, следует, что квадратичная скорость сходимости к X* достижима только тогда, когда для оценивания используется какой-нибудь метод второго порядка (см. разд. 6.6.2).

В первых реализациях схемы модифицированных функций Лагранжа правило пересчета формулировали, исходя из обеспеченного в решении х подзадачи (6.25) равенства

g(x) - A {xf К+рА(хГс {X) = 0.

Оно говорит о том, что вектор

(6.26)

(6.27)

играет в точке х ту же роль, что X* в х, т.е. задает разложение градиента g{x) по строкам матрицы А (х). Поэтому представляется естественным взять (6.27) в качестве формулы пересчета Xj, что и делалось. (Как будет показано в разд. 6.6.1, при некоторых условиях (6.27) определяет линейные оценки множитспей.)

На рис. 6к изображены три первые точки, полученные алгоритмом AL для задачи примера 6.2 (с ограничением, трактуемым как равенство), причем исходной оценкой для X» послужила Х„ = 0, а носледуюшне оценки вычислялись по формуле (6.27) Параметр штрафа р был зафиксирован равным 0.6. Последовательность {Х из (6.27) в общем случае сходится лишь линейно, и потому алгоритм AL с пересчетом оценок множителей по формуле (6.27) тоже оказывается линейно сходящимся. Для примера 6.2 набор


Рис. 6к, Три первые точки, выданные методом модифицированной функции Лагранжа для задзчи нз примера 6.2 с ограничением, трактуемы.м как равенство; каждая есть результат безусловной мИ нимизации.

Xt-xl). * = 3, ...,8, выглядит так; 1.69x10-, 9.17x10-», 4.61x10-», 2.41X10-S 1.23X10-S 6.39x10- Ошибка уменьшается приблизительно вдвое на каждой итерации. Если же при менить к задаче примера 6.2 алгоритм AL, в котором по-преж нему Х„ = 0 и р = 0.6, но множители оцениваются методом вто рого порядка (см. разд. 6.6.2), то значениями {Hxj-x.J, k=\, .... 6, будут 5.61x10-1, 1.88x10-. 2.75xl0- 6.59x10", 3.87 X 10" и 3.19 X 10"". Здесь очевидна квадратичная сходимость.

*6.4.3. ВАРИАЦИИ СТРАТЕГИИ ПОИСКА

Схема разд. 6.4.2.1 представляет собой не более чем один из многих способов применения модифицированной функции Лагранжа. Понятно, что идти к равенству (6.22) можно и но-другому.

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



предлагались методы модифицированных функций Лагранжа с различными степенями точности решения (6.25). Среди них - «крайний» метод, в котором х и X пересчитываются синхронно; точнее говоря, выполняется одна итерация спуска для (6.25), затем пересчитывается X, делается один шаг безусловной минимизации прн новом X и т. д. В последнем случае на каждой итерации ставится новая подзадача. При этом шаги спуска по х обычно выбирают на основании квадратичной аппроксимации L, и, коль скоро это так, рассматриваемый метод можно проинтерпретировать в терминах данной аппроксимации, а не самой L. Тогда его уместно будет отнести к классу методов спроектированного лагранжиана с квадратичной подзадачей (которые мы рассмотрим в разд. 6.5.3).

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

Кем и когда идея модификации функции Лагранжа была высказана впервые, не ясно. Во всяком случае в середине 40-х годов она уже была достаточно популярна (см. Хестенс (1946, 1947)). С историей этого вопроса можно познакомиться по докладу Хестеи-са (1979). В практику численной оптимизации модифицированные функции Лагранжа вошли относительно недавно. Подход, представленный выше, в основном следует построениям Хестенса (1969). Другой вывод методов модифицированных функций Лагранжа был независимо дан Пауэллом (1969). Он предложил применять квадратичный штрафной терм, в который каждое ограничение входит со своим «сдвигом» и «весом». В алгоритме Пауэлла (для задачи NEP) целевая функция подзадачи безусловной минимизации выглядит так;

f(x)-Ц<,(ё,.to-0,)

где Oi- положительный вес, а 0;- сдвиг для ("-го ограничения. Еслн взять все веса равными, она будет отличаться от (6.24) только не зависящим от х слагаемым. Для пересчета оценок множителей как Хестенс, так и Пауэлл рекомендовали формулу (6.2). В качестве еще одной из первых работ по методам модифицированных функций Лагранжа можно назвать статью Хаархоффа и Вайса (1970). Обзоры свойств этих методов читатель найдет у Бертсекаса (1975b, 1976а, Ь), Мангасарьяна (1975) и Флетчера (1977). Общий взгляд на модифицированные функции Лагранжа излагается в статье Хестенса ( 980Ь). Отличные от (6.24) функции данного класса описаны, например, в работе Богса и Толле (1980).

Учитывать в методах модифицированных функций Лагранжа ограничения-неравенства можно разными способами. Байс (1972) и Рокафеллар (1973а, Ь, 1974), например, предположили искать решение задачи с неравенствами последовательной безусловной мини-

мизацией по х обобщающей (6.24) функции вида Lj(x. X, p)=f (х)-ьХ

п, ( - Х,.с,. (X) + f с, (х)\ если с,.х < ,

-f-X;, если c,.(x)>-J-

(6,28)

В данной записи X представляет собой «расширенный» вектор множителей Лагранжа. Как сама функция (6.28), так и ее градиент непрерывны всюду, и в том числе в точках, где какие-то из «активных» ограничений (т. е. тех, для которых е,<Х/р) становятся «неактивными» (Ci>Xj/p). Вторые производные от Lj, разрывны в этих точках, ио есть надежда, что последние будут лежать вдали от решения, и поэтому указанная разрывность ие осложнит работы алгоритма безусловной минимизации La. Аналог формулы Пауэлла - Хестена (6.27) для модифицированной функции Лагранжа (6.28) таков:

X,. -X,.-min (р(;, X,.).

Здесь через Xi обозначено обновленное значение оценки i-ro множителя. Эта формула гарантирует неотрицательность X, для «активных» неравенств и дает нулевые Х; для «иеактивны.ч». Иные формулы пересчета, предназначенные для методов с более частыми сменами Х;, приводятся, например, в диссертации Вайса (1972). К задачам с неравенствами можно применять также стратегии прогнозирования активного набора (см. разд. 6.5.5), когда для каждой подзадачи безусловной минимизации определяется, какие из ограничений в ией учесть, и эти ограничения трактуются как равенства.

Характер сходимости любого метода модифицированных функции Лагранжа существенно зависит от качества используемых в нем оценок множителей. Способ их построения разумно подбирать так, чтобы скорости сходимости образуемо!! ими последовательности н последовательностей точек, генерируемых при решении подзадач (6.25), были одинаковы. В частности, решая (6.25) процедурой ньютоновского типа, для вьмисления Х; имеет смысл взять метод второго порядка (см. разд. 6.6.2). Тогда можно будет достичь квадратичной сходимости процесса в целом. Если же к (6.25) применяется квазиньютоновская процедура, то достаточно, чтобы формулы пересчета оценок множителей обеспечивали им свер.члинейную сходимость. Характеристики методов с разными способами вычисления оценок множителей анализируются в работах Байса (1972), Бертсекаса (1975b, 1976b), Корта (1975), Берда (1976, 1978), Корта и Бертсекаса (1976), Тайна (1977, 1978), Глэда (1979) и Глэда и Шлака (1979).

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



Когда между двумя последовательными пересчетами оценок множителей выполняется только одна итерация спуска в (6.25), вся процедура становится похожей на метод спроектированного лагранжиана с квадратичной подзадачей (см. разд. 6.5.3). В частности, Тапиа (1978) показал, что при определенных условиях приближения, генерируемые комбинацией квазиньютоновского метода для (6.25) и некой формулы пересчета оценок, просто идентичны получаемым с помощью одного из методов спроектированного лагранжиана. И все же ие надо забывать о концептуальном различии между методами модифицированных функций Лагранжа, базирующихся на подзадачах безусловной минимизации, и методами спроектированного лагранжиана, в основе которых лежат подзадачи с линейными ограничениями.

Модифицированные функции Лагранжа неоднократно использовались для построения комбинированных алгоритмов. Из них стоит упомянуть комбинации с методами типа приведенных градиентов, оп[1саниые в статьях Миеле, Крэгга, Айера и .Певи (1971), Миеле, Крэгга и Леви (1971).

Предметом пристального внимания многих исследователей был вопрос о выборе и интерпретации параметра штрафа р. Особый интерес представляет связь между р и областью сходимости (см. Берт-секас (1979)).

Подходу к решению задач условной оптимизации, рассмотренному выше, близка идея построения гладкой точной штрафной функции. Так как х* является точкой безусловного минимума (6.24) с Х=Х*, можно показать, что при любой дважды дифференцируемой -(х), удовлетворяющей равенству Х(х*)=к*, для достаточно больших р в х* реализуется минимум

F {х)-1 (xV г {x)--c{xrS{x). (6.29)

Следовательно, функция (6.29), как и абсолютная штрафная (см. разд. 6.2.2.1), может послужить точной штрафной функцией. Первым ее предложил Флетчер (1970b), (см. также Флетчер и Лилл (1970), Лш1л (1972) и Флетчер (1973)). К сожалению, 1{х) определяется через производные от f и el так что подсчет градиента (6.29) оказывается весьма трудоемкой процедурой. Дальнейшие подробности относительно методов точных гладких штрафных фукций читатель найдет по приведенным выше ссылкам.

6.5. МЕТОДЫ СПРОЕКТИРОВАННОГО ЛАГРАНЖИАНА

6.5.1. ПРЕДВАРИТЕЛЬНЫЕ СООБРАЖЕНИЯ

6.5.1.1. Описание подзадачи с линейными ограничениями. Если в искомой точке х* вьшолнеиы достаточные условия из разд. 3.4, то Б ней будет достигаться минимум функции Лагранжа на множестве векторов, ортогональных градиентам активных в х* ограниче-

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

Коль скоро приближения к х* решено определять из подзадач с ограничениями, естественно формулировать их так, чтобы множители Лагранжа этих подзадач служили приближениями для X*. Обозначив через оценку вектора Х*, используемую при постановке подзадачи в очередной точке xj, это соображение можно оформить в виде следующего требования: из равенств Хд=х* и ХХ* должно следовать, что х*- решение подзадачи, а Я.*- ее вектор множителей Лагранжа.

6.5.1.2. Формулировка подзадачи. Ради простоты начального изложения допустим, что набор активных в х* ограничений каким-то образом выявлен; через с в дальнейшем обозначается вектор, составленный из их функции. О методах определения активного набора речь пойдет в разд. 6.5.5.

Пусть д - шаг из неонтимальной точки х,, в х*. Он должен удовлетворять равенству

c{x)=i{x„+g) = 0. (6.30)

Чтобы сформулировать подзадачу для расчета приближения д, воспользуемся тейлоровским разложением функции с в окрестности Xj:

с (х-) - ?j + лЛх*-Xj) Ч-О (II x-xJI =) = о, (6.31)

где через и А, обозначены с (х) и А (х). Пренебрегая нелинейным слагаемым, получаем, что приближения к х* можно искать

среди X. для которых

(6.32)

Система ограничений (6.32) задает множество точек, обнуляющих линейную аппроксимацию нелинейной функции с, построенную в Xft. Она аналогична системе, используемой для вычисления шага в ньютоновской процедуре решения уравнений (6.30) (см. (4.72) в разд. 4.7.6).

11 к, 2984



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