full_book

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

(см. пункт 1.4.1) следует, что ( g j ( yo ), y1 − yo ) ≤ 0.Аналогично, из свойств функции h(y) получим ( h( y0 ), y1 − yo ) = 0.

Домножая скалярно равенство (2.19) на вектор направления d = y1 – yo, получим

n

∑νi0 ( f i ( yo ), d) ≥ 0, что при ν0 ≥0 и ν0 ≠0 означает, что i : ( fi(yo),d) ≥0. Из

i=1

псевдовыпуклости fi(yo) и последнего неравенства следует fi(y1)≥ fi(yo). Но это противоречит нашему предположению.

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

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

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

Теорема 2.7. Пусть f(y), g(y)-дифференцируемы в точке уo, а h(y)-непрерывно

ДОКАЗАТЕЛЬСТВО. Исключим из рассмотрения тривиальный случай, когдаh1(yo),…, hp(yo) –линейно зависимая система. В этом случае утверждение теоремы будет элементарно выполнено при ν 0 = 0,λ0 = 0, µ0 ≠ 0.

Далее будем считать h1(yo),…, hp(yo) линейно независимыми. Рассмотрим следующие множества

Условия экстремума с использованием этих множеств можно записать в следующей очевидной форме: для того, чтобы точка уo, внутренняя для Е, была локально слабо эффективной, необходимо существование ε > 0 при котором

Введем в окрестности точки уo аппроксимации множеств, входящих в условие (2.27), конусами:

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

Лемма 2.1. Если выполнено условие непересекаемости (2.27), то

Рис.2.1 иллюстрирует утверждение леммы.

Рис.2. 1. Соотношение между коническими аппроксимациями множеств

ДОКАЗАТЕЛЬСТВО леммы. Пусть d K f IKY . Тогда i=1,…,n: ( fi(yo),d)<0,

j J(yo): ( gj(yo),d)<0 и d KH. В условиях теоремы найдется o(ε), что h(yo+ε d+o(ε) )=0 (рис.2.2).

Рис.2.2. Кривая уε, порожденная на многообразии H касательным направлением d

Обозначим уε=yo+ε d+o(ε). Тогда при малых ε

f(уε) = f(yo)+( f(yo),d) ε+o(ε) < f(yo).

Аналогичные рассуждения показывают, что при достаточно малых ε: g j (уε) <0, j J(yo), и g s(уε) < 0 при s J(yo) за счет того, что g s(уo) < 0.

В результате оказалась найдена точка уε Оε (yo) Y со значением f(yε)<f(yo), что противоречит слабой эффективности точки уo. Лемма доказана.

Нам осталось показать, что условие (2.31) равносильно (2.24)–(2.26). Это можно сделать, сконструировав специальные вспомогательные линейные задачи оптимизации. Поскольку мы рассматриваем случай линейной независимости системы векторов h1(yo), h2(yo),…, hp(yo), то конус KH(yo) в (2.31) не пуст и либо в нем имеется вектор d≠0, либо KH(yo)={0}.

Случай А. KH(yo)={0}. В этой ситуации вектора h1(yo), h2(yo),…, hp(yo)

образуют базис в пространстве RN (т.е. в этом случае, p=N), следовательно всегда

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

можно вектор ( f(yo),v0) разложить по нему с коэффициентами µ1,…, µ p, и

положить λi =0 (i=1,…,m).

Cлучай В. d KH(yo), что d≠0. При этом можно выделить два подслучая в (2.31): KY≠ и КY= . Первый является основным, второй случай можно рассматривать во многом аналогично.

Лемма 2.2.. При выполнении условий K f KY= , KY≠ значение do=0 является слабо эффективным решением задачи

____

Предположим, что она не слабо эффективна для этой задачи, тогда η K Y , что

( f(yo),η)<0≡( f(yo),do). По предположению относительно η : ( gi(yo), η) ≤ 0 для j J(yo) и ( h(yo),η)=0. Поскольку KY≠ , то ξKY: ( gj(yo),ξ)<0 для j J(yo),

( h(yo),ξ)=0. Образуя смесь dε= η+ε ξ c малым ε>0, получим вектор dε K f KY,что противоречит (2.31). Таким образом, лемма 2.2 доказана.

Воспользуемся доказанной леммой.

Задача (2.32) является выпуклой, а условие KY≠ гарантирует ее регулярность по достаточному условию Слейтера (теорема 2.3). Поэтому для нее можно записать необходимое и достаточное условие по теореме 2.5. Нетрудно видеть, что это условие совпадает с (2.24)–(2.26) и при этом окажется, что v0≠0 , т.е. условие KY≠ является условием регулярности в исходной задаче.

Теперь рассмотрим оставшийся случай KY= . Поскольку KH(yo)≠ , то

нормалям к равенствам, т.е. по системе h1(yo),…, hp(yo), что позволит удовлетворить утверждению теоремы. Последний случай рассматривается

Следствие 2.7.1 (достаточное условие регулярности для невыпуклых задач).

Пусть в задаче FYE из (2.4), (2.5) yo int E, f(y), g(y) –дифференцируемы в точке уo, а h(y) – непрерывно дифференцируема в уo. Если d RN, что ( hs(yo),d)=0 (s = 1,…,p) и j J(yo): ( gj(yo),d)<0, при этом h1(yo),…, hp(yo)-линейно независимы,

то область Y регулярна в точке уo.

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

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

Следствие 2.7.2 (вторая форма достаточного условия регулярности для невыпуклых задач). В задаче, приведенной в следствии 2.7.1, для регулярности области Y в точке уo int E достаточно, чтобы набор векторов

h1(yo),…, hp(yo), g j1(yo),…, g jr(yo), где {j1,…,jr}=J(yo), был линейно независим.

Доказательство легко получается от противного.

2.2.2. Условия экстремума второго порядка

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

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

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

Теорема 2.8. Пусть f, g, h C 2(E) и для точки уo Y, являющейся внутренней для Е (уo int E), выполнены условия А и В:

А. (v0 ,λ0 , µ0 ),v0 ≥ 0,v0 ≠ 0,λ0 ≥ 0, что λj0gj(yo) = 0 (j=1,…,m) и для функции Лагранжа (2.6) выполнено условие стационарности (2.17), т.е.

Тогда при n > 1 точка уo – локально слабо эффективна, а при n = 1 является строгим локальным минимумом задачи.

В (2.35) используется ΓyL — матрица Гессе функции Лагранжа по

переменным у.

ДОКАЗАТЕЛЬСТВО. Рассмотрим малую ε – окрестность точки уo. Возьмем произвольную точку y Οε ( yo ) IY. Будем считать ε настолько малым, что

множество номеров активных в точке y ограничений–неравенств J(y) J(yo). Заметим, что J(y) может отличаться от J(yo) за счет того, что точка у может быть выведена с границ части активных ограничений внутрь области Y.

Если вектора d≠0 и удовлетворяющие условиям пункта В существуют, то можно построить линейное, касательное в точке уo многообразие

М(уo,у)= {yo+d: ( h(yo), d)=0, ( gj(yo), d) = 0, j J(y)}

к пересечению поверхностей, порожденных ограничениями–равенствами и активными в точке у неравенствами (рис.2.3).

Заметим, что возможен случай, когда J ( y) = и ограничения–равенства отсутствуют. В этом случае следует считать, что M ( yo , y) = RN , и все необходимые рассуждения следует провести с соответствующей поправкой.

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

Рис.2. 3. Фрагмент границы и касательное многообразие

Пусть zy – проекция точки у на многообразие М(у0,у), запишем операцию

и g , y – zy = o(β). Это позволяет представить точку у в виде y= yo + β dy + o(β).

Построим оценки для скалярного произведения

(f(y),ν0) ≥ (f(y),ν0) + (g(y),λ0) + (h(y),µ0) = L(y, ν0, λ0,µ0) =

≤0 = 0

=L(yo, ν0, λ0,µ0) + ( yL(yo, ν0, λ0,µ0), y – yo) + (dy β+o(β))TΓyL(ξ ,ν0,λ0,µ0)(dyβ+o(β))=

=0

=L(yo, ν0, λ0,µ0) + β 2 dyT ΓyL (ξ,ν0,λ0,µ 0 ) dy + o(β 2) > L(yo, ν0, λ0,µ0) = (f(yo),v0) (2.36)

(f(y),v0)> (f(yo),v0).Отсюда при n = 1 (в силу v0 ≠0, v0≥ 0 ) следует, что уo – точка строгого локального минимума, а при n > 1 можно утверждать лишь (свойство 1.4 пункта 1.3.5) , что уo – локально слабо эффективна. Теорема доказана.

Проанализируем теперь вопрос о необходимости условий (2.33)–(2.35) для слабой эффективности уo. Сформулируем следующую теорему.

Теорема 2.9. Пусть f, g, h C1(E), yo –локально слабо эффективная точка (локальный минимум при n=1), задача регулярна в точке уo и yo int E, тогда выполнено условие (А) теоремы 2.8. Если, кроме того, f, g, h C2(E) и задача – однокритериальна (т.е. n=1), то для всех векторов d, удовлетворяющих условиям (2.34) теоремы 2.8, выполняется неравенство

)Замечание. Следует обратить внимание, что первое утверждение теоремы верно для любых задач, а второе – справедливо только для однокритериальных задач. Для многокритериального случая условие второго порядка не является необходимым.

Проследим ход рассуждений. Легко видеть, что первое утверждение следует из теоремы 2.7. Чтобы выяснить справедливость второго, предположим, что оно не выполняется и вектор d≠0, удовлетворяющий (2.34), для которого неравенство (2.37) нарушается, т.е. dTΓyL(yo,ν0,λ0,µ0)d < 0. Введем коэффициент смещения β вдоль d. В силу достаточной гладкости g и h найдется поправка о(β), что точка y(β) = yo + β d + о(β) будет удовлетворять равенствам

h(y(β)) = 0 и gj(y(β)) = 0, j J(yo).

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

Повторяя выкладки, аналогичные (2.36), получим

L(y(β),v0,λ0,µ0) < L(yo,v0,λ0,µ0) = (f(yo),v0)

Но

L( y(β),v0,λ0,µ0) = ( f(y(β)), v0) + ∑λ0j g j ( y(β)) + ( h(y(β)), µ0) = f( y(β), v0 )

j J ( yo )

в силу приведенных выше равенств, которым удовлетворяют в точке y(β) функции gj и h.

Следовательно, при малом β получаем, что f(y(β),v0) < (f(yo),v0) при v0 ≥0,

v0≠0.

Рассмотрим это неравенство. При размерности векторного критерия n=1 мы получаем обычную однокритериальную задачу, в которой неравенство приведет к f( y(β) ) < f(yo), что противоречит локальной оптимальности точки уo. Это означает, что свойство (2.37) выполняется для однокритериальных задач.

Пусть теперь n > 1. Приведем контрпример, показывающий, что рассматриваемое неравенство не противоречит локальной слабой эффективности точки уo и, следовательно, в многокритериальных задачах (2.37) может не выполняться. Структура примера поясняется на рис.2.4.

Рис.2. 4. Иллюстрация к контрпримеру

Видно, что при определенной структуре множества Слейтера и Парето существование в сколь угодно малой окрестности уo допустимой точки y(β) со значением линейной свертки Ψν 0 ( y(β)) < Ψν 0 ( yo ) не противоречит слабой

эффективности точки уo.

Таким образом, неравенство (2.37) в многокритериальных задачах может нарушаться. Доказательство теоремы завершено.

2.3. Элементы теории двойственности в задачах математического программирования с одним критерием

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

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

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

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

многокритериальные задачи требует, как оказывается, привлечения новых конструкций по сравнению со скалярным случаем (см., например, главу 4 в [6]). Иными словами, возникают трудности при попытке такого изложения теории двойственности, когда результаты и форма их записи одинаково подходили бы для многокритериального и скалярного случаев.

По этой причине в настоящем курсе элементы теории двойственности будут представлены только для однокритериальных задач ((2.4),(2.5) при n=1).

Рассмотрим однокритериальную задачу, которую будем называть прямой задачей Р.

Задача P

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

)Замечание. Для однокритериальной задачи понятие слабо эффективного решения уo совпадает с понятием эффективного решения y*, а также с понятием глобально-оптимального решения y*. Поэтому далее для решения будет использоваться обозначение не уo, а y*. Соответственно и значения множителей Лагранжа будут обозначаться как λ*, µ* .

Ограничимся в нашем рассмотрении задачами с выполненным условием регулярности (хотя бы для точки решения y*). При этом множитель Лагранжа при f(y) может быть принят равным ν =1, поэтому, в отличие от общего случая (2.6),

К постановке двойственной задачи проще всего придти, опираясь на полученные в разделе 2.1 условия экстремума. В теоремах 2.1, 2.4 было показано, что (применительно к рассматриваемой регулярной скалярной задаче) следующие условия являются достаточными для глобальной оптимальности точки y* Y:

Таким образом, в рассматриваемом классе задач седловая точка функции Лагранжа (2.40) по области y E,λ ≥ 0 Rm , µ RP определяет глобально– оптимальное решение у* исходной задачи.

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

которая при некоторых значениях параметров может принимать бесконечные значения равные –∞.

Определение 2.3. Функцию L* (λ, µ) называют функцией двойственной задачи.

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

Определение 2.4. Задачей двойственной по Лагранжу назовем задачу следующего вида (назовем ее задачей D)

Задача D

Переменные λ и µ называют двойственными переменными.

С учетом (2.42) двойственная задача является максиминной задачей. Интуитивно кажется, что при достаточно общих условиях ее решение должно соответствовать точке λ ,µ ,у .из (2.41) Несколько позднее этот вопрос будет рассмотрен точно.

)Замечание. При записи задачи в постановке Р ко множеству Е может быть отнесена различная часть ограничений, что позволяет одну и туже задачу записывать в разных формах Р. Это приведет к неоднозначности формулировок двойственных задач D. Таким образом, одной задаче оптимизации можно сопоставить несколько форм записи Р и несколько двойственных к ним задач D.

Теория двойственности устанавливает связи между решениями прямой и двойственной задач [1]. Первая (слабая) теорема двойственности устанавливает простое мажарантное соответствие между значениями f(y) и L (λ,µ).

ДОКАЗАТЕЛЬСТВО вытекает из следующей простой оценки

L (λ, µ) = inf { f(y) + ( λ, g(y) ) + ( µ, h(y) ): y E} ≤ f(y) + ( λ, g(y) )+(µ,h(y)) ≤ f(y).

В случае отсутствия ограничений–равенств и количестве ограничений– неравенств m=1 утверждение теоремы хорошо иллюстрирует рис.2.5.

Рис.2. 5. Соотношение функций прямой и двойственной задач

Следствие 2.10.1.

являются решениями прямой и обратной задач P и D.

С. Если в прямой задаче Р int { f(y): y Y} = –∞, то (λ,µ) c λ ≥ 0 L (λ, µ) = –∞. D. Если sup { L (λ, µ): λ≥0, µ RP } = +∞, то Y= .

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

В пояснении нуждается только последнее свойство. Его проще всего обосновать от противного. Допустим у Y, тогда при λ ≥ 0

L (λ,µ) ≤ f(y)+(g(y), λ ) + ( h(y), µ) ≤ f(y) < +∞,

что противоречит заданному условию.

Центральный факт из теории двойственности – сильная теорема двойственности. Она показывает, что при условиях выпуклости и регулярности оптимальные значения функций в задачах P и D совпадают. Этот факт вполне понятен в рамках геометрической интерпретации задач на последнем рисунке.

Теорема 2.11 (сильная теорема двойственности). Пусть множество Е выпукло и не пусто, f и g – выпуклы на Е, h(y) – афинная (h(y) = A у – b). Пусть, кроме

ДОКАЗАТЕЛЬСТВО.

1.Пусть inf = –∞, тогда по следствию 2.10.1(C) из слабой теоремы двойственности sup = –∞, т.е. равенство (2.46) будет выполнено.

2.Пусть inf достигается в некоторой точке у Y, тогда по теоремам 2.2–2.3

(λ ,µ ) с λ*≥0, что (λ ,g(y ) ) = 0 и

L(y*,λ ,µ ) = min{L(y,λ*,µ*): y Y}= L*(λ*,µ*).

Но значение в левой части равенства равно f(y*)+(λ ,g(y*))+(µ ,h(y*)), где два последних члена равны нулю, следовательно, f(y*) ≤ L*(λ*,µ*).

Тогда по следствию 2.10.1(В) из слабой теоремы двойственности получаем выполнение (2.46), также окажется выполненным и условие (λ , g(y*))=0.

Остался не рассмотренным случай, когда inf { f(y): y Y}=С ≠ –∞, но он не достигается. Тогда у Е система

g( y) ≤ 0, h( y) = 0

f ( y) ≤ С

не совместна.

Если рассмотреть множество S = Uy E S( y) из доказательства теоремы 2.2,

то точка (C,0,0) будет его граничной точкой. Тогда по теореме об отделимости выпуклого множества S и его граничной точки (C,0,0) (ν * , λ* , µ* ) ≠ 0 что ε≥0, δ≥0, y E:

ν* ( f ( y) + ε) + (λ* , g( y) + δ ) + (µ* , h( y)) ≥ C ν *

Далее, аналогично доказательству теоремы 2.2, можно показать, что ν ≥ 0, λ*≥ 0,

где, в силу регулярности задачи, ν*≠0 и его можно положить равным 1. Выбирая в неравенстве ε=0, δ=0, получим, что L(y,ν , λ ,µ ) ≥ C, поэтому L*(λ*,µ*) ≥ C. По следствию 2.10.1(A) это доказывает справедливость утверждения теоремы.

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

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

условиях теоремы 2.11 при существовании конечного глобального минимума задача Р можно определить его, решая двойственную задачу D в пространстве

(λ,µ) Rm+p с простыми ограничениями λ≥0. Проблема заключается в том, что функция двойственной задачи L*(λ, µ) определяется через решение вспомогательной экстремальной задачи (2.42), где минимум ищется только по

области Е, в качестве которой обычно используется либо все пространство RN, либо область (2.3) в виде N–мерного параллелепипеда.

Таким образом, для выпуклой регулярной задачи

644L*7(λ,µ4) 48

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

Дальнейший материал этого раздела направлен на изучение свойств функции L*(λ,µ). Сейчас будет показано, что она обладает достаточно хорошей структурой.

Теорема 2.12. Пусть Е-компакт, а f, g, h С(E), т.е. непрерывны на Е. Тогда функция L*(λ, µ) двойственной задачи вогнута на множестве λ ≥ 0 Rm , µ RP .

ДОКАЗАТЕЛЬСТВО. Выберем два допустимых значения для λ и µ: (λ1,µ1) , (λ2,µ2) и произвольное α (0,1). Сделаем оценку

L* (λα , µα ) = inf { f ( y) + (λα , g( y)) + (µα ,h( y)) : y E} =

= inf {αL( y,λ1 , µ1 ) + (1−α)L( y,λ2 , µ2 ) : y E } ≥αL* (λ1 , µ1 ) + (1−α)L* (λ2 , µ2 ).

Вогнутость доказана.

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

Приведем без доказательства2 теорему, дающую ответ на этот вопрос.

Теорема 2.13. Если Е – компакт, функции f, g, h C(E), и (λ, µ) с λ≥0 точка глобального минимума y*(λ, µ) функции Лагранжа по y на Е единственна, то

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

2 Обоснование аналогичного свойства можно найти, например, в книге М.Базара, К.Шетти [1], раздел 6.3