full_book

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Вотличие от метода штрафов, последовательность γ k не обязана стремиться

кбесконечности. Сходимость может быть обеспечена за счет настройки

множителей µ k.

Теорема 3.5. Пусть для задачи с ограничениями–равенствами (3.24) выполнены

предположения А, В, тогда γ и δ>0, что при выполнении условий

µ0−µ < δ γ0 и γ ≤ γ k ≤ γк+1 — k

для метода модифицированной функции Лагранжа (3.29)–(3.30):

1) вспомогательные задачи (3.29) будут иметь единственное решение, причем

µ k→µ* и уk→у* при k→∞;

2) если lim γ k = γ * < ∞, k : µk ≠ µ* , то 0 ≤ q <1 , что

k→∞

ДОКАЗАТЕЛЬСТВО теоремы требует обоснования ряда вспомогательных фактов и из-за ограничений объема не приводится. Его можно найти в книге Д.Бертсекас [2], раздел 2.2.

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

а именно, его сходимость гарантируется только при достаточно точном начальном приближении множителей Лагранжа.

Применение метода требует автоматической настройки коэффициента штрафа. Здесь может быть применен подход, похожий на используемый в методе штрафов, а именно.

АЛГОРИТМ НАСТРОЙКИ КОЭФФИЦИЕНТА ШТРАФА. Введем параметр α < 1 —

коэффициент желаемого уменьшения невязки в ограничениях на шаге метода, а также множитель β > 1 прироста коэффициента штрафа, например, α=0.25, β=10. Обычно используется следующая схема настройки γ k

Таким образом, при достаточно быстром убывании невязки коэффициент штрафа расти не будет.

3.3.5. Метод модифицированной функции Лагранжа в задачах с равенствами и неравенствами

Вернемся от задачи (3.24) к задаче с равенствами и неравенствами (3.23), но воспользуемся в явном виде рассмотренным ранее приемом сведения ограничений–неравенств к форме равенств g i(y) + zi2 = 0 (i=1,…,m).

Построим модифицированную функцию Лагранжа в виде

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

+ 0.5γ (gi ( y) + zi2 )2 }.

Минимум в (3.29) по переменным (y,z) разделяется в последовательное взятие минимумов по z и по y. Находя минимум по z в (3.32) аналитически, получим

(zi*)2 = max{0; –λ i /γ – gi(y)}

Подставив это выражение в (3.32), получим окончательный вид модифицированной функции Лагранжа с исключенной переменной z:

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

3.4. Другие общие методы учета ограничений

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

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

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

3.4.1. Метод параметризации целевой функции

Как и в методе внешнего штрафа здесь вводится штрафная функция Н(у) вида (3.4), которая может быть построена аналогично (3.5) в виде степенной функции

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

параметризации строятся так, чтобы параметр β k влиял не на величину штрафной добавки, а на способ учета целевой функции f(y) исходной задачи. Выбор нового значения параметра β k+1 жестко связан в этих методах с полученным оптимальным значением S*β k функции текущей вспомогательной задачи.

ОПИСАНИЕ МЕТОДА. В качестве начального значения β0 принимается нижняя оценка глобального минимума функции f(y) на Y, т.е. выбирается β0 ≤ f(y ). Для

где Ф — функция настройки параметра β, может иметь различный вид. Например, при r = 2 используется правило

На рис. 3.7 приведена геометрическая интерпретация процесса решения задачи (3.37) – (3.38) по методу (3.40), (3.41), (3.43) при двух конфигурациях множеств вида

Q+ = { ( (c1 g1(y))+ ,…, (cm gm(y))+ , f(y) ) : y E }.

Рис.3. 7. Два типа поведения метода параметризации

Решение задачи (3.41) соответствует отысканию сферы с центром в точке (0; β k) минимального радиуса из имеющих пересечение с множеством Q+. Точки

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

касания этой сферы с Q+ является образами точек уk при отображении

( (c g)+ ; f): E →Q+.

Центр новой сферы размещается в точке (0; βк+1), которая получается в результате пересечения предыдущей сферы с осью f. На рис. 3.7 проиллюстрирован характер процесса сходимости последовательности β k к оптимальному значению f *= f(y*). Левый рисунок соответствует сходимости за бесконечное число шагов, а правый — за конечное. Формальное обоснование метода и условия сходимости определяются следующей теоремой.

Теорема 3.6. Пусть множество Е RN является компактом, f, g C(E), т.е.

непрерывны на Е, Y ≠ , β0 < f(y *). Тогда любая предельная точка у∞ последовательности уk (k=0,1,2,…) в методе параметризации (3.40), (3.41), (3.43) при r=2 является глобальным минимумом исходной задачи (3.37)–(3.38). Кроме того, существует предел

ДОКАЗАТЕЛЬСТВО. В силу непрерывности функций и компактности Е из теоремы Вейерштрасса вытекает существование решений вспомогательных задач (3.41). Таким образом, последовательность β k определена. Из (3.43) следует ее монотонность:β k+1 ≥ βk. Кроме того, по построению β0 ≤ f *.

По индукции легко доказать, что f * будет являться верхней оценкой для β k. Действительно, пусть для некоторого k: β k ≤ f *. Поскольку y* Υ E, то

существуют предельные точки. Пусть у∞– одна из них. Из ранее доказанного следует, что

f(y∞) ≥ f *, но ранее было показано, что f * ≥ β *. Итак: β *= f(y∞) ≥ f *≥ β * Отсюда видим, что f(у∞) = f *. Теорема доказана.

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

)Замечания. А. Если при некотором k окажется, что Sβ k (y k) = 0, то найденное решение уk вспомогательной задачи будет являться точным решением исходной задачи, т.е. уk Υ . При этом поиск следует остановить.

B. Если, за счет вычислительных ошибок, на некотором шаге окажется

β k > f *, то (0, β k) Q+ и элементы последовательности уk перестанут изменяться, следовательно, метод потеряет сходимость. Это накладывает повышенные требования на точность решения вспомогательных задач в методе параметризации.

3.4.2. Метод допустимой точки

определяющая верхнюю огибающую системы нормированных (с помощью коэффициентов сi) функций ограничений.

)Замечание. Перед началом использования метода должна быть известна допустимая начальная точка y 0 Υ.

ОПИСАНИЕ МЕТОДА. Вводится параметр метода γk Полагается γ0 = f(y0). Далее для произвольных k ≥ 0 определяется итерационная процедура следующего вида

Заметим, что вспомогательная функция (3.47) напоминает свертку Гермейера для многокритериальных задач (см. пункт 1.3.7, формула (1.31) ). Вид функции Sγ k (y) для случая у R1 для одной из возможных ситуаций показан на

рис.3.8 утолщенной линией.

Рис.3. 8. Выполнение итераций в методе допустимой точки

Теорема 3.7. Пусть Е — компакт, f, g C(E), Y ≠ и, кроме того, в сколь угодно малой окрестности любой допустимой точки существуют y Y со значениями

G(y) < 0. Тогда любая предельная точка у∞ последовательности уk, построенной методом допустимой точки (3.47)–(3.49), является глобальным минимумом задачи (3.37)–(3.38). Кроме того, существует предел, как в (3.44):

lim f ( yk ) = f *= f (y* ).

k→∞

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

ДОКАЗАТЕЛЬСТВО. В силу непрерывности функции (3.47) и компактности Е, задачи (3.48) имеют решение.

Легко видеть, что последовательность γ k является, по построению, не возрастающей, а поскольку все точки уk допустимы, то γ k ≥ f *= f (y*), т.е. данная последовательность ограничена снизу. Следовательно, существует предел γ k → γ * при k → ∞. Осталось показать, что γ *= f (y*).

Пусть это не так и γ * > f(y*). Рассмотрим значения γ k достаточно близкие к

γ*:

γk – γ * < δ, k > K. Далее обратим внимание, что для этих k возможна оценка

Sγk ( yk +1 ) ≥ f ( yk +1 ) −γ k =γ k +1 − γ k > −δ .

Рассмотрим точки у Ε, лежащие в достаточно малой ε – окрестности у*. По предположению теоремы среди них найдется такая точка у что G( y) < −η для достаточно малого η > 0. Более того, можно выбрать η и δ настолько малыми, чтоk >K одновременно выполнится еще одно неравенство: f( y) – γ k< −η. Это

возможно в силу непрерывности f(y) и предположения γ *> f(y*). Таким образом, Sγ k( y) < – η.

В силу того, что δ выбирается произвольно и может быть сделано δ < η, получим Sγ k(y k+1) > Sγ k( y) для у Ε, что противоречит правилу (3.48). Теорема

доказана.

Возможна геометрическая интерпретация метода в пространстве значений функций (c g), f при m=1, показанная на рис.3.9 для двух случаев конфигураций множеств

Q = { ( c 1 g 1(y);…; c m g m(y); f(y) ): y Ε}.

Рис.3. 9. Два типа поведения итераций в методе допустимой точки

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

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

)Замечания. A. Функции Sγ (y) вспомогательных задач метода допустимой точки не являются гладкими, что создает существенные препятствия при использовании методов локальной оптимизации для решения вспомогательных задач (3.48). Этот метод учета ограничений используется, в основном, в специальных алгоритмах многоэкстремальной оптимизации (см. раздел 4.3), где гладкость не является существенной. B. В методах многоэкстремальной оптимизации метод центров обычно

используется в модифицированной форме, когда параметр γ k функции S γ k(y) изменяется непосредственно в процессе поиска ее минимума на E:

3.4.3. Индексный метод учета ограничений

Индексный метод [44] был разработан для одномерных многоэкстремальных задач с частично вычислимыми ограничениями. Его можно рассматривать как развитие метода допустимой точки, описанного в предыдущем пункте, хотя он был разработан независимо. В некотором смысле индексная схема идет дальше метода допустимой точки на пути построения вспомогательных задач, а именно, при этом подходе функции вспомогательных задач оказывается не только не гладкими, но могут оказаться разрывными.

Вэтом пункте метод будет описан не в своем оригинальном варианте [44],

акак общая вычислительная схема учета ограничений.

Метод рассматривается при следующем видоизменении постановки исходной задачи. Обозначим Υ0 ≡ Ε и определим набор вложенных множеств

При этом предполагается, что областью определения i–го ограничения является множество Yi–1, а областью определения целевой функции f — множество Υm. Введем еще одно вспомогательное пустое множество Υm+1= , а также введем переобозначение для целевой функции, положив g m+1(y) ≡ f(y). Выполняется следующее включение

Υ0 Υ1 ... Υm Υm+1= .

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

Сопоставим задаче (3.53) вспомогательную задачу, которая будет иметь решение даже в том случае, когда множество Υm может оказаться пустым. Для этого введем классификацию точек у Ε по значениям индексов ν = ν(у), определяемых номером первого нарушенного ограничения, точнее у Υν−1, у Υν . Таким образом, если все ограничения в точке y выполнены, то ее индекс будет равен m+1. Запишем это в форме определения.

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Определение 3.2. Индексом ν(у) точки у E назовем номер первого

решение (т.е. M(E)=m+1), то оно будет совпадать с решением задачи (3.54). Если же окажется ν( y *)=M(E) < m+1, то это значит, что исходная задача (3.54) решений не имеет. Согласно индексной схеме вводится новое понятие результата измерения в точке у. Считается, что результатом измерения в точке y является вычисление значений

а также множества номеров точек, выполненных измерений, индексы которых больше ν:

Определим достигнутые к шагу k модифицированные рекордные значения функции измерений z(y) по группам точек с одинаковым значением индекса ν

В индексной схеме метод многоэкстремальной оптимизации на k+1 – м шаге выполняет размещение точки очередного измерения, исходя из следующей

результатам вычислений функций исходной задачи в точках выполненных ранее измерений.

На рисунках 3.10, 3.11 представлены виды функции Sk (y) из (3.59) для задачи, изображенной на рис.3.8, в предположении, что проведено k=3 и k=5 измерений.

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Рис.3.10. Структура вспомогательной функции в индексном методе после k=3 измерений

На рис. 3.10 в точках проведенных измерений наибольшее значение индекса

на величину z*ν=2k происходит только для значений функции g2(y).

Рис.3.11. Изменение структуры вспомогательной функции после добавления испытания в точке с индексом ν=3

На рис. 3.11 есть два измерения, выполненных в области Y2 , где определена функция f(y), поэтому наибольшее значение индекса ν в точках измерений равно 3

и, следовательно, значения z*νk для ν=1 и ν=2 равны нулю, а для ν=3 величина z*νk отлична от нуля. В результате на этом шаге графики функций g1(y) и g2(y) не

смещены, а значения функции f(y) смещены на величину z*ν=3k.

Обоснование сходимости индексного метода приведено в [44] применительно к оригинальной авторской версии алгоритма в сочетании с информационно–статистическим методом одномерной многоэкстремальной оптимизации.

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Лист регистрации изменений