Методы выпуклого математического программирования и условные нелинейные оценки

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

Необходимые и достаточные условия оптимальности как теорема Куна — Таккера

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

Общие сведения о задачах выпуклого программирования

Рассматривается формулировка необходимых и достаточных условий для следующей задачи: вычислить

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

Рассмотри м множество

где /|(х), 1 = 1, т — вогнутые непрерывные на множестве Г скалярные функции, а Г — заданное выпуклое и замкнутое множество. В частности, Г может совпадать с пространством 9?".

Из теории выпуклых множеств известно, что множество (2.6.2) выпукло, поскольку является пересечением выпуклых множеств Г и {х е И"| г"(х) > Ь}. Из непрерывности УХХ) и замкнутости множества Г следует замкнутость множества Ж

Пусть сформулирована задача: вычислить

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

Множество Ш должно удовлетворять условию регулярности.

Определение 1. Если для каждого I (г = 1, т) существует точка х-, е ©, что влечет за собой

то множество Ш удовлетворяет условию регулярности Слейтера.

Рассмотрим вектор

который характеризует невязки в неравенствах, задающих ограничения.

Определение 2. Функция

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

Определение 3. Пара х",у„ называется седловой точкой функции Лагранжа £(х, у) на множестве х е Г, у> О, если

для всех х е Г, у> 0. Последнюю формулу можно записать также следующим образом:

Теорема 1. Если пара х^у, — седловая точка функции Лагранжа £(х,у) на множестве х є Г, у > 0, то х* — оптимальная точка задачи выпуклого программирования.

Доказательство. Развернутая форма условий (2.6.7) с учетом (2.6.6) имеет вид

Из левого неравенства следует, что

поскольку у* >0 и это неравенство имеет место для любого значения у > 0, то Ь(х„)<0. В частности, (2.6.9) имеет место и для у = 0, т.е. (у*, Ь(х))>0, а следовательно (так как у,>ОиЬ(х*)<0),

Если хе), то из (2.6.1) и (2.6.5) следует, что к{х) < 0, и поэтому для х е © будет иметь место условие

Так как (2.6.8) имеет место для всех значений х є Г, и в частности для хеЭ, то из правого неравенства (2.6.8) и из (2.6.10) и (2.6.11) получаем для всех хеШ неравенства

Но х*еЯЭ (так как х е Г и Ь(х,()<0) и, следовательно, х* — оптимальная точка.

Вперед теорема является необходимым и достаточным условием оптимальности.

Теорема Куна — Таккера

Теорема формулируется следующим образом.

Теорема 2. Пусть в задаче (2.6.3) множество 23 = = {х ^Тх) Ь£ обладает свойством регулярности Слейтера (2.6.4). Необходимым и достаточным условием оптимальности является существование такого у"^0, чтобы пара х*,у* была седловой точкой функции Лагранжа £(х, у) на множестве х е Г, у > 0.

Достаточность доказана в теореме 1.

Необходимость. Пусть х8 оптимален. Рассмотрим в (п + 1)-м пространстве множества

где S(x) определяется для каждого х е Г следующим образом:

Покажем, что множества Р и S выпуклы. Выпуклость множества Р очевидна.

(У (г"

Пусть I ° eS и z" eS, и покажем, что и (zfl.z)r = (ъ'0, z)r

+(l-a)-(2o,z)7*eS для всех а є [0, 1]. Так как (z'0,z)TeSt то найдется такой вектор х є Г, что (z'0, z)T eS(x'), и аналогично (zq, z")r є S(x"). Нам достаточно показать, что (z0, z)T eS(x), где x = ax'+(l-a)x". Из выпуклости <р(лг) и -f(x) следует

Таким образом, (г0, г) е Б с Б.

Теперь докажем, что множества Р0 и Б не имеют общих точек. Здесь будет

Для каждого хє-Ш ввиду оптимальности х„ будет справедливо г0><р(х)>ф(х„), но в Р0 г0<(р(х„).

Для каждого х є Г, такого, что хеВ, найдется хотя бы один номер такой, что

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

такой, что + (и, г) > и0ш0 + (и, для всех (г0, г)Т е Б и (а>0, € Р0.

Поскольку множеству Р„ принадлежат точки со сколь угодно большими по модулю отрицательными компонентами, то необходимо должно быть

Неравенство (2.6.13) остается справедливым и тогда, когда ("?0, у/)т принадлежит границе Р; поэтому, выбрав (Е0 = -(=*)• хф Ь= г(х), ге>0 (х„), а> 0, получим для всех х е Г

Убедимся, что щ > 0. Предположим, что щ = 0. Тогда (2.6.15) примет вид

Так как и > 0 (см. (2.6.14)) и и 0 (см. (2.6.13)), а для всех хе© будет справедливо

то при щ > 0 равенство А,- - /(х) = 0 будет выполняться для всех хе©, что противоречит свойству регулярности Слейтера.

Значит, из предположения и0 = 0 следует, что и = 0, а это противоречит (2.6.12). Итак, щ > 0.

Пусть у, = М(7'и 0, тЬгда (2.6.15) примет пил

<р(х,)<<р(х) + (У!>,Ь-г(х))

для всех х б Г и для х = х,. Отсюда следует

(Уо,Ь-Г(х))>0. (2.6.16)

Но у„>0, а Ь-гХх„)<0 (так как хеЭ), поэтому

(ув,Ь-г(х„)) = 0. (2.6.17)

Для любого значения у > 0 будет справедливо

(у,Ь-г(х,"))<0. (2.6.18)

Из неравенств (2.6.16)—(2.6.18) получаем

Ф(х.) + (у, Ь - г(х.)) < ф(х") + (у., Ь - г(х„)) < Ф(х) + (у., Ь - {(х))

для всех X 6 Г, у > О, или

£(х„, у) < £(х„ у.) < £(х, у„),

где представлено семейство квадратичных аппроксимаций Ф(х) в окрестности хк, что соответствует неравенствам седловой точки.

Дифференциальные условия Куна — Таккера

Для практического применения весьма важен случай дифференцируемость ограничений.

Теорема 3. Если функции ф(х) и /(.г) задачи выпуклого программирования (2.6.2) непрерывно дифференцируемы на множестве Г = {х|х 0}, >го для того чтобы пара х„У), была седловой точкой функции Лагранжа в области х > 0, у > 0, необходимо и достаточно выполнения условий, приведенных в табл. 2.3.

Таблица 2.3.Условия Куна — Таккера

^>0 Эх		х ^	= 0	х„>0
		1У'>]	= 0

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