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

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

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

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

Идея «приведения» или «проектирования» градиентов первоначально высказывалась в отношении задач с линейными ограничениями. Ссылки на соответствующие работы даны в замечаниях к разд. 5.1 и 5.2. Для задач с нелинейными ограничениями первый метод «проекций градиентов» был предложен Розеном (1961), который обобщил сконструированный им же аналогичный метод минимизации при линейных ограничениях (Розен, 1960). Для определения в алгоритме Розена неявно используется ортогональная матрица Zj.

Авторами схемы обобщенных приведенных градиентов являются Абади и Карпентье (1965, 1969). В ее первой реализации матрица (6.18) строилась в явном виде. Программа, разработанная Абади и его коллегами по Electricite de France, широко применялась для решения практических задач (см., например, Абади и Гигу (1970)). Экспериментальное сопоставление различных методов, проведенное Колвиллом (1968), показало, что методы обобщенных приведенных градиентов были одними из самых надежных и эффективных. К настоящему моменту их семейство пополнилось большим количеством новых алгоритмов: как уже было отмечено в разд. 6.3.1, для конкретизации каждого пункта схемы типа приведенных градиентов есть намало возможностей.

В последние годы иад методами типа приведенных градиентов в числе прочих работали Сарджент и Муртаф (1973), Абади (1978), Лэсдон и Уорен (1978),

Известно, что при существенно нелинейных ограничениях методы типа приведенных градиентов работают плохо, поскольку сильно искривлеитшге границы допустгшого множества отслеживать тяжело (см. разд. 6.3.2). В связи с этим выдвигались разные предложения, и в частности предлагалось занижать требуемую точность соблюдения ограничений. Правда, последнее означает пересмсгтр принципиальных позиций и переход в класс методов спроектированного лагранжиана (см. разд. 6.5). Общий обзор методов типа приведенных градиентов с некоторыми соображениями относительно их связей с методами спроектированного лагранжиана читатель найдет в статье Сарджента (1974),

6.4. МЕТОДЫ МОДИФИЦИРОВАННЫХ ФУНКЦИЙ ЛАГРАНЖА

К классу методов модифицированных функций Лагранжа можцо идти разными путями. Однако конечную цель всегда формулируют одинаково: свести поиск решения задач NEP или NIP к минимиза-

ции без ограничений, причем вспомогательную функцию подобрать так, чтобы (i) не было неизбежной плохой обусловленности (как в методах гладких штрафных и барьерных функций из разд. 6.2,1) и (ii) Ф имела непрерывные первые производные (в отличие от негладких штрафных функций нз разд. 6.2.2).

6.4.1. ОПРЕДЕЛЕНИЕ МОДИФИЦИРОВАННОЙ ФУНКЦИИ ЛАГРАНЖА

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

Методы модифицированных функций Лагранжа можно использовать и для задач с равенствами, и для задач с неравенствами. Принцип учета равенств всегда один и тот же, а для неравенств возможны варианты. Обычно используется какая-нибудь стратегия прогнозирования активного набора, и тогда в начале каждого цикла безусловной минимизации по некому правилу определяется, какие ограничения войдут в с"(см. разд. 6.5.5). Другие схемы учета неравенств в методах модифицированных функций Лагранжа обсуждаются в замечаниях. Пока же ради простоты изложения предположим, что заранее известен правильный список активных в х* ограничений, и через с{х) будем обозначать вектор, составленный из их функций.

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

g{x) = A{xfX.

(6.22)

Здесь А-матрица, чьи t строк представляют собой градиенты активных в X* ограничений. Если Л (х*) имеет полный ранг, вектор X" определяется равенством (6.22) однозначно. Введем функцию Лагранжа

L{x, Ц = Р{х) - 1с{х).

(6.23)

(Заметьте, что определение (6.23) зависит от того, как формируется вектор с.) Соотношение (6.22) означает, что при К=к* х* будет ее стационарной (по х) точкой. Если бы эта стационарность означала экстремальность, функцию Лагранжа можно было бы использовать в качестве Ф. Однако в общем случае х* не доставляет минимума L{x, X*) (см. второй фрагмент рис. 6Ь). Значит, даже имея X*, рассчитывать на то, что X* удастся найти безусловной минимизацией функции Лагранжа, нельзя.



гл. 6. Задачи с нелинейными ограничениями

Обозначим через Wix.k) матрицу вторых производных по х от L{x, X), т. е.

W(x, X)cw-XM,w. i=i

у tt(x*, X*) могут быть и отрицательные, и нулевые собственные значения, но спроектированную матрицу Гессе (х") W (х", X*) Z (х) в силу сказанного ранее мы считаем положительно оп-редетеннок (через Z (х) принято обозначать матрицу, столбцы которой формируют базис пространства векторов, ортогональных строкам А(х)). Следовательно, х* будет точкой минимума L (х, X) по X на многообразии, орпюгональном градиентам активных в х* ограничений.

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

L(x. I, p)F(x)--k-c(x)-i{xfc{x). (6.24)

Здесь р-положительный параметр штрафа.

В точке X* и сам квадратичный штраф, и его градиент обращаются в нуль (поскольку с состоит из функций активных в X ограничений). Таким образом, прв Х = К* точка х* является стационарной (по х) для (6.24). Матрица Гессе штрафного терма равна Ci(x)G,{x)-i-A{xy А{х). При х = х* ненулевым в этом

выражении будет только второе слагаемое А{хУА(х). Это-положительно полуопределенная матрица, причем все ее собственные значения, отвечающие собственным векторам нз ранг-пространства A(xY, больше нуля. Значит, поправка к функции Лагранжа в (6.24) приводит к увеличению (возможно, отрицательных) собственных значений матрицы W для векторов из ранг-пространства А (xV, в то время как свойства матрицы Гессе в отношении векторов, ортогональных А {xY, сохраняются. Нетрудно доказать существование конечного значения р, такого, что для любого р > р матрица Гессе V}.,i (х*, Х-*, р) будет положительно определена и соответственно в л* реализуется сильный локальный минимум Lix, X*, р). При этом независимо от р для любой матрицы Z (х*), ортогональной строкам Л (х*), справедливо равенство

Z(x)VLL>, p)Z(x) = Z(x«)W {х; i.)Z{x).

6.4. Методы модифицирование функций Лагранжа

т. е. на спроектированную матрицу Гессе штрафная добавка не влияет.

Проиллюстрируем эффект описанной модификации функции Лагранжа иа простом примере.

Пример 6.4. Рассмотрим одномерную задачу

найти minx

при ограничении х-)-1=0.

Ее единственной допустимой и, следовательно, оптимальной точкой является х*=-1, причем >.*=3. Таким образом,

L(x, ?.*)=x»-3(х--1).

Эта функция в х имеет локальный максимум. В то же время при любом р>р(р = 6) модифицированная функция Лагранжа

La (X, Х>, р) = х-3 (х+ 1) (х-1- 1)"

в X* достигает локального минимума. Графики для х и L(x, ?.*) изображены на рис. 6h сплошной и нунктирнон линиями. Модифи-


Рис. eh. Сплошная линия - график целевой функции иэ примера 6.4, f (х)-х; пунктирная - график функции Лагранжа; штриховая - график молифициро-ванной функции Лагранжа Lix, л , 9).

цированная функция Лагранжа с р=9 показана штриховой линией. Отметим, что оиа не ограничена снизу при любом значении параметра штрафа р.



6.4.2. СХЕМ.А АЛГОРИТМОВ С МОДИФИЦИРОВАННЫМИ ФУНКЦИЯМИ ЛАГРАНЖА

Из сказанного в разд. 6.4.1 следует, что в идеальном случае X* можно найти однократной безусловной минимизацией гладкой функции (6,24). Однако этот случай практического интереса не представляет, поскольку предполагает знание вектора X*, а, не имея решения х*, его вычислить нельзя. В реальной ситуации вместо истинных множителей Лагранжа используются их оценки. Центральная роль, которую они играют в методах модифицированных функций Лагранжа, объясняет, почему эти методы часто называют также MetnoikiMU множителей.

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

6.4.2.1. Модельная схема. В данном разделе схематично описан один из способов поиска минимума при ограниченияч-неравен-ствах с использованием модифицированной функции Лагранжа. Он предполагает задание начального списка включаемых в с ограничений, начальной оценки вектора множителей Лагранжа Л», начального приближения Хо, начального значения параметра штрафа и положительного целого числа К, которое послужит верхней границей количества итераций. Определив все это и сделав присвоение А-*-0, надо выполнить следующие действия.

Алгоритм AL (Модель метода модифицированной функции Лагранжа)

ALI. [Проверка соблюдения правил останова.] Если х удовлетворяет условиям оптимальности или А > /С, вычисления прекратить. В первом случае Xj берется в качестве иско-. мого решения; во втором выдается признак неудачи.

AL2. [Минимизация модифицированной функции Лагранжа.] Использовав Xj в качестве начальной точки, применить процедуру решения подзадачи

(6.25)

предусматривающую возможность неограниченности Lj снизу. Лучшее нз найденных ею приближений взять в качестве Xfi+i.

AL3. [Пересчет оценок множителей Лагранжа.] Если это уместно, изменить состав с. Вычислить новый вектор оценок множителей Лагранжа X+j.

найти minL(x, Xj, р).

AL4. [Увеличение, если это необходимо, параметра штрафа.] Если в точке х+, невнзки ограничений :идачп существенно меньше, чем в х,, перейти к следующему шагу, а иначе увеличить р.

AL5. [Перевод счетчика итераций.] Сделать присвоение ft. и вернуться к шагу AL1.

6.4.2.2. Свойства модифицированной функции Лагранжа. Предполагая испапьзовать какой-нибудь метод с модифицированной функцией Лагранжа 1л, надо иметь в виду следующие обстоятельства.

-*-1-1

Локальность минимума. Как и для штрафных функций, описаи-иых в разд, 6.2 (в отсутствие у исходной задачи специальных свойств), в точке х* в лучшем случае реализуется лишь локальный минимум La- При этом La может быть не ограниченной снизу для любого значения параметра штрафа р. Следовательно, применяя к подзадаче (6.25) стандартный алгоритм безусловной минимизации, нужно предусмотреть в нем соответствующие меры предосторожности (на что и указано в п. AL2 модельной схемы). Обычно увеличением р в конце концов удается получить настолько широкую область притяжения л:*, что неограниченность 1. становится неопасной. Однако полных гарантий сходимости к х* в общем случае дать нельзя.

Трудности выбора параметра штрафа. Подобрать подходящий параметр р иногда бывает непросто даже в таких ситуациях, когда проблема неограниченности снизу модифицированной функции Лагранжа не возникает. Дело в том, что среди значений р. обеспе-чивающих существование в х* локального безусловного минимума La, наряду со «слишком большими» обычно есть и «слишком малые». ,И те и другие дают плохо обусловленные La. При завышенных р функция La становится плохо обусловленной по тем же причинам, что и гладкие штрафные функции. Причиной плохой обус.1;оБлеино-сти La при заниженных р является вырождение ее матрицы Гессе (еслн матрица Гессе обычной функции Лагранжа знаконеопределеиа) при минимальном допустимом р.

На рис. 61 изображены линии уровня La (х, р) при трех значениях параметра р для задачи из примера 6.2, ограничение которой трактуется как равенство. Вторая функция (рО.2) обуслсшлена хорошо. Первая (р=0.075) и третья (р=100) иллюстрируют последствия выбора слишком малых и слишком больших р.

Критическая роль оценок множителей Лагранжа. Поскольку xf будет точкой минимума модифицированной функции Лагранжа лишь если для сходимости использующего ее л1етода при огра-

ниченном р необходимо обеспечить сходимость генерируемых оценок множителей к X*.



[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