full_book

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

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

допустимого множества, то любая предельная точка у*∞ будет находиться на пересечении границ ∂Υ ∂Υ.

ДОКАЗАТЕЛЬСТВО [5]. В теореме 3.1 показано, что у*∞ Υ Υ. Поэтому в

пренадлежащих Υ и Υ и сходящуюся к у*∞. Это доказывает справедливость свойства.

Свойство 3.3. Если Y* int Y и штрафные задачи решаются точно (т.е. ε k=0),

Свойство 3.4. Если в методе штрафов последовательность коэффициентов

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

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

Заметим, что в том случае, когда решение исходной задачи размещается на границе допустимой области Y и не является точкой безусловного минимума

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

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

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

Свойство 3.5. Пусть известна хотя бы одна допустимая точка уΥ Υ и

точное решение задачи со штрафом будет удовлетворять указанному критерию останова.

3.2.4. Оценки скорости сходимости метода внешнего штрафа

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

Дополнительные предположения.

А. Отсутствует погрешность решения задач со штрафом (εк≡0).

В. Используется степенной штраф вида (3.5) с r>0, а невязка в ограничениях оценивается функцией G(y) из (3.12).

С. Множество Е – замкнуто, а f – липшицева на Е с константой L в метрике

ρ(.,.).

D. δ>0 и α>0, что у ( Οδ(Υ)\Υ ) Ε выполняется G(y) ≥α ρ(y,Υ).

Будем измерять ошибку оценивания решения у* исходной задачи (3.1), (3.2) через решение у*γ вспомогательной задачи (3.7), используя разность значений функций исходной и вспомогательной задач. Запишем величину ошибки

Теорема 3.2 (об оценке скорости сходимости). Если выполнены условия 1–4

теоремы сходимости 3.1 и кроме того – дополнительные предположения A–D, то при точном решении вспомогательных задач со штрафом

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

А. Пусть при некотором γ решение задачи со штрафом (3.5)–(3.7) у*γ Υ тогда у γ Υ (поскольку для у Υ Sγ ( y) ≡ f ( y), ). Следовательно ∆(γ)=0.

В. Во всех остальных случаях γ : yγ* E \ Y.Рассмотрим эти случаи.

По теореме 3.1 при γ→∞ ρ (у γ,Υ )→0. Тогда δ>0 при достаточно больших γ: у γ Οδ (Υ ) \Υ . По дополнительному предположению (D)

G( yγ* ) ≥α ρ( yγ ,Y * ) .

Рассмотрим точку z γ — проекцию у γ на Υ :

zγ = πΥ ( у γ ).

Выполним оценку величины штрафа

H ( yγ* ) ≥ (max{max{ 0; c1 g1 ( yγ* );...;cm gm ( yγ* ) }; max{ Cs hs ( yγ* ) : s =1,..., p }})r = = (G( yγ* ))r ≥α r ( ρ( yγ* ,Y * ) )r .

Теперь оценим значение минимума функции задачи со штрафом

± f ( zγ )

Sγ ( yγ* ) = f ( yγ* ) + γ H ( yγ* ) ≥ f (zγ ) − f (zγ ) − f ( yγ* ) + γαr (ρ( yγ* ,Y * ))r ≥ ≥ f ( y* ) − Lρ( yγ* ,Y * ) + γαr ρ( yγ* ,Y * )r = f ( y* ) − Lρ + γαr ρr ,

где ρ = ρ( yγ* ,Y * ) .

Следовательно, 0 ≤ ∆(γ ) ≤ ρ(L −γαr ρr −1) Вид зависимости для разных диапазонов значений r показан на рис.3.4.

Рис.3.4. Вид верхних оценок для ∆(γ) при различных r

Рассмотрим несколько случаев.

Пусть 0 < r < 1. При γ→∞ ρ=ρ (у γ,Υ )→0, следовательно γαr ρr −1 → ∞ .

Начиная с некоторого γ верхняя оценка для ∆(γ) станет отрицательна, что противоречит возможному знаку ∆(γ). Это означает, что начинают нарушаться условия, при которых эта оценка получена, т.е. окажется выполненным у*γ Υ. Тогда, согласно рассмотренному случаю (A), у γ Υ , а значит, ∆(γ)=0.

Пусть r = 1. При γ > Lαr ∆(y) < 0 , если ρ>0. Повторяя приведенные выше рассуждения, приходим к выводу, что ∆(γ)=0.

Пусть r > 1. В этом случае нетрудно показать (см. рис. 3.4), что при указанном в (3.16) значении C выполнится неравенство

∆(γ ) ≤ max { ρ (L −γαr ρr−1 ) : ρ ≥ 0 } = Cγ 1(r−1) .

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

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

Теорема 3.3. Если g j (y) для j=1,…,m выпуклы и непрерывны на выпуклом компакте Е, область {y Ε: g(y) ≤ 0 } удовлетворяет условию Слейтера: у Ε,

β=min { hs(y) : s=1,…,p, y Ε, h(y)=0 }, то β>0. Поэтому при некотором δ>0 для ограничений–равенств в невязке G(y) из (3.12) следует выбрать, например,

α ≤ min{ 0,5β | Cs |: s =1,..., p }.

Рассмотрим неравенства. Пусть Gg(y) = max{ g j (y): j = 1,…,m}. По условиюу Ε, что Gg( y) < −d < 0. Пусть в точке y из Ε нарушаются ограничения– неравенства, отсюда Gg(y) > 0. Очевидно (см. рис. 3.5), что y′ [y, y], что

Gg(y′)=0.

Рис.3.5. Поведение невязки у границ области при выпуклых ограничениях

Отсюда и из ранее сделанной оценки для ограничений–равенств следует справедливость теоремы.

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

В теореме об условиях сходимости метода штрафов предполагается, что при решении каждой задачи со штрафом определяется y*γk(ε k) — оценка глобального

минимума штрафной задачи. Поскольку методы многоэкстремальной оптимизации требуют значительно большего объема вычислений, чем методы локальной оптимизации, то при практических расчетах, обычно прибегают к следующему приему. На первой итерации метода штрафов для вычисления y*γ0(ε 0) используют один из методов многоэкстремальной оптимизации, а на

следующих итерациях для получения оценок y*γk+1(ε k+1) (k=1,…) прибегают к

методам локальной оптимизации, в которых в качестве начальных точек поиска используются точки y*γk(ε k), найденные на предыдущей итерации.

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

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

использовании локальных методов оценка решения не будет приближаться к точному решению. Похожий эффект возможен и при расположении решения y* на границе допустимой области, если начальная оценка y*γ0(ε 0) окажется в

окрестности локального минимума функции штрафа H(y), расположенного вне допустимой области. Действительно, при всех достаточно больших значениях коэффициента штрафа γ у Sγ( y ) — функции штрафной задачи, будет

существовать локальный минимум, расположенный в малой окрестности локального минимума функции штрафа. Если такая ситуация возникла на первой же итерации метода штрафов, и оценка y*γ0(ε 0) попала в область притяжения

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

вычисляемых в точках получаемых оценок y*γk(ε k), при k→∞.

Рис.3. 6 Возможность потери решения при наличии локального минимума у функции штрафа

На рис.3.6 приведен пример описанной выше ситуации. В этом примере решается задача поиска минимума линейной функции –y1 + y2 в прямоугольной области –3 ≤ y1 ≤ 3, 0 ≤ y2 ≤ 5 при дополнительном ограничении (y12+y22–11)2+(y1+y22–7)2+(y1–y2) ≤ 0.3. Функция штрафа в этом примере имеет локальный минимум, расположенный в окрестности точки y1=2,45, y2=2,15. При сколь угодно большем увеличении коэффициента штрафа у функции штрафной задачи сохраняется локальный минимум в окрестности этой точки. На рисунке показано поведение метода прямого поиска Хука–Дживса (см. раздел 7.7), запущенного из начальной точки, расположенной в области притяжения этого минимума. Видно, что правильное решение оказалось потерянным.

Допустимая область выделена на рисунке более темным цветом, в ней показаны изолинии линейной минимизируемой функции. Левый рисунок соответствует выбору значения коэффициента штрафа γ =10, а правый — значения γ =1000.

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

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

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

Прежде чем говорить о методе модифицированных функций Лагранжа следует рассмотреть общую схему метода множителей.

3.3.1. Общая схема метода множителей Лагранжа и ее недостатки

Из главы 2 известно, что для «хорошо» устроенных задач математического программирования (3.1) – (3.2), например, для случая выпуклого Е, выпуклых на Е функций g и f, а также афинных функций h, при регулярности допустимой области Y критерием глобальной оптимальности точки у* является (см. теоремы

Причем задача на максимин в (3.17) соответствует двойственной задаче математического программирования (2.42) – (2.43).

Из (3.17) следует, что задача оптимизации (3.1)–(3.2) в пространстве размерности N при функциональных ограничениях может быть (при оговоренных выше условиях) сведена к задаче взятия максимина в области простой структуры (без функциональных ограничений) в пространстве размерности N+m+p.

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

Первый вариант реализации, использует градиентные направления в пространстве переменных у и (λ, µ), и фиксированный коэффициент длины шага. Он был предложен в 60-х годах авторами Эрроу и Гурвицем. Их итерационный метод поиска седловой точки функции Лагранжа имеет вид

Здесь g(yk) и h (yk) являются векторами градиентов функции Лагранжа по переменным λ и µ и, одновременно по теореме (2.14), — компонентами субградиента двойственной функции Лагранжа (2.42). Операторы πΕ и ()+ выполняют проектирование на множества Е и (R+)m. Значение коэффициента шага

х>0 является параметром метода.

Ксожалению, процедура (3.18)–(3.20) может порождать расходящийся процесс. Чтобы показать это достаточно привести пример.

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

ПРИМЕР РАСХОДИМОСТИ. Рассмотрим простую задачу с E=R1, m=1, g1(y) = = – y ≤ 0, f(y)=y, ограничения–равенства отсутствуют (т.е. р=0). Следует заметить, что эта задача удовлетворяет всем указанным выше условиям. Ее решением является точка у*=0, а соответствующее значение λ в условиях экстремума равно 1.

Поскольку функция Лагранжа в этой задаче имеет вид L(y, λ) = y–λy, то без учета операции проектирования (.)+ итерационный процесс (3.18)–(3.20) примет для нее следующую форму

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

λk+1 – λk+2 = λk – λk+1 – х2(1 – λk)

или

Стационарным решением последнего разностного уравнения является значение λ* = 1, что правильно соответствует значению множителя Лагранжа в условиях экстремума. Поскольку λ*>0, то при начальном значении λ0 близком к 1 опущенный оператор проектирования (.)+ для λ не будет оказывать влияния на итерационный процесс, пока он выполняется в области λ >0. Поэтому сходимость процесса можно исследовать без его учета.

Необходимым и достаточным условием асимптотической устойчивости стационарного решения λk≡λ* для уравнения (3.22) является размещение внутри

единичного круга корней характеристического полинома z2 – 2z + (1– x2) = 0, но z1,2 = 1 ± (1−(1−x2) )0,5 = 1± x , следовательно max z1,2 =1+ x ≥1. Процесс итераций расходится для любого х. Возможность расходимости (3.18)–(3.20)

доказана.

Второй вариант реализации метода множителей непосредственно основан на решении двойственной задачи (2.42)–(2.43) с использованием той же итерационной схемы по λ и µ, что и в методе Эрроу–Гурвица, но с полным вычислением двойственной функции Лагранжа. Его итерационные формулы приведены в конце главы 2 в формулах (2.50)–(2.52).

Необходимо сразу подчеркнуть, что область его применения ограничивается задачами, где нет разрыва двойственности (см. теорему 2.11 и рис. 2.5). Кроме того, этот вычислительный метод нельзя применить при неограниченных значениях двойственной функции Лагранжа. Например, в рассмотренном выше примере L*(λ,µ)=−∞ при λ≠1 и 0 – при λ=1. Хотя это и не противоречит (3.17), но препятствует поиску решения численными методами.

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

3.3.2. Преобразование постановки задачи, сведение задач с неравенствами к задачам с равенствами

В целях удобства дальнейшего изложения будем считать, что множество E=RN, т.е. задача ставится так:

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

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

Задачу будем считать достаточно гладкой, что позволит записывать условия экстремума в форме градиентных равенств. Наличие дополнительных требований вида y Ε≠RN лишило бы нас возможности использовать эту форму записи в общем случае.

Чтобы упростить изложение, избавимся от ограничений–неравенств. Существует общий прием сведения неравенств к равенствам за счет увеличения размерности пространства переменных. Рассмотрим неравенство g i (y)≤0. Введем дополнительные переменные zi, чтобы gi(y)=–zi2. Отсюда эквивалентной формой записи неравенства будет

gi(y) + zi2 = 0.

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

y := ( y | z ,..., zm ) RN +m , N := N + m .

14243

z

Окончательно приходим к задачам, в которых присутствуют только ограничения–равенства

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

Вначале вернемся к общей постановке задачи (3.1) – (3.2) (позднее результаты проведенного анализа будут применены к постановке (3.24) ).

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

Заметим, что условие существования седловой точки у L(y,λ, µ) не является необходимым условием для задач общего вида, а также для произвольных задач вида (3.24). Таким образом, в точке решения у* у функции L(y, λ*,µ*) может не быть минимума по у на Е.

Пример. Рассмотрим задачу с невыпуклой функцией f(y) = y3 и одним ограничением h(y) = y+1 = 0:

y3 →min, y Υ={y R1: y+1=0}.

В этой задаче существует единственная допустимая точка у = –1. Условие экстремума дает –3(–1)2 = µ* 1 , следовательно µ*= –3, L(y, µ *) = y3 – 3(y+1).

В точке у = у*= –1 уL(y*,µ )=0, ΓyL(y ,µ ) = −6< 0, следовательно в этой точке по переменной у у функции Лагранжа достигается максимум, а не минимум.

Таким образом, единственное, что можно гарантировать у функций Лагранжа L(y, λ, µ) для гладких регулярных задач в точке решения у* Ε – это стационарность точки y*, λ ,µ*.

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

) Поставим задачу: так модифицировать функцию Лагранжа, чтобы точки (y*, λ ,µ*) оставались седловыми, но при λ=λ , µ=µ модифицированная функция имела хотя бы локальный минимум по у в точке у*, даже если задача не выпукла.

Рассмотрим структуру функции Лагранжа. Пусть для у* известен набор активных ограничений J* = J(y*) и значения самих множителей Лагранжа λ , µ*. В силу условий Куна–Таккера λ*j g j (y ) = 0 (j = 1,…,m) и, кроме того, h(y*) = 0. Поэтому на множестве

Поскольку у* — точка минимума функции f на Y, и у* Y(у*) Y, то на множестве Y(y*) функция Лагранжа (в силу (3.26)) также будет иметь в точке у* минимум.

Для того, чтобы данное свойство сохранилось не только на Y(y*), но и на всем множестве Е (или хотя бы локально, в области Ε Οε(у ) ) необходимо сделать добавку к L(.), обеспечивающую возрастание этой функции при удалении от многообразия Y(y*).

Чтобы упростить изложение, вернемся к постановке (3.24), т.е. будем считать, что задача представлена в форме задачи с равенствами. Наложим на нее дополнительные ограничения, гарантирующие существование в точке у* строгого локального минимума f на Y. Для этого воспользуемся достаточными условиями второго порядка для строго локального минимума из теоремы 2.8.

Предположения о задаче (3.24)

А. Пусть f, h C 2(RN), y – решение задачи (3.24), являющееся ее регулярной точкой.

В. Для множителей Лагранжа µ , при которых выполнено условие экстремума

При этих предположениях у* будет являться строгим локальным минимумом в задаче (3.24). Условие (3.27) можно трактовать как условие положительной определенности матрицы Гессе по переменным у для функции Лагранжа L(у,µ ) на линейном многообразии касательных направлений

KH(y*) = {d RN : (d, hs(y*))=0 (s = 1,…,p)},

которое было введено при доказательстве теоремы 2.7 (см. формулу (2.28)).

Заметим, что модифицированная функция Лагранжа должна иметь в точке у* матрицу Гессе (гессиан), положительно определенную на всем RN.

Построим модифицированную функцию Лагранжа L γ (y,µ), добавив к L(.)

слагаемое, возрастающее при уходе точки у с ограничений–равенств:

ИССЛЕДОВАНИЕ. Изучим эту функцию.

y L γ (y,µ)= f(y) + (µ+γ h(y))Τ h(y)

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

= ΓyL ( y* , µ* ) + γ ( h( y* ))T h( y* ).

Введем два обозначения:

V(d) = dT ΓyL(y*,µ*) d, W(d) = dT ( h(y*))T h(y*) d = h(y )d 2.

Тогда

d≠0, d KH(y*): V(d) > 0, W(d) = 0

d≠0, d KH(y*), W(d) > 0.

Для достаточно малого ε и ξ Οε(0) при d KH(y*) выполнится V(d+ξ)>0, W(d+ξ)≥0. Обозначим

η1 = inf { V(d ): d =1, d (KH(y*)+Οε(0) ) },

η2 = inf { W(d ): d =1, d (KH(y*)+Οε(0) ) }.

Заметим, что множество KH(y*)+Οε(0) представляет ε – слой вокруг линейного многообразия KH(y*). Поскольку η2 > 0, то γ > 0, что η1 + γ η2 > 0.

Все это, в совокупности, определяет положительную определенность гессиана функции L γ (y, µ ) в точке у*. Замечая, что y L γ (y ,µ )= y L(y ,µ )=0, видим, что для L γ (y,µ ) выполнены достаточные условия строгого локального минимума в точке у* по переменным y.

Лемма 3.4. Для задачи (3.24), удовлетворяющей предположениям А, В при достаточно большом γ модифицированная, согласно (3.28), функция Лагранжа имеет в точке у* строгий локальный минимум по у.

ДОКАЗАТЕЛЬСТВО приведено перед текстом леммы.

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

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

например, [5,23]).

3.3.4.Метод модифицированной функции Лагранжа для задач с ограничениями–равенствами

Метод модифицированной функции Лагранжа имеет следующую