Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

3.5. Теорема Куна-Таккера

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

Теорема 3.2 (Куна-Таккера).Пусть в основной задаче (3.2) выпуклого программирования


множество X = {х∈Г: f(x)≥}} обладает свойством регулярности (3.3).

Необходимым и достаточным условием оптимальности х* является существование такого y*≥0, чтобы пара х*, y* была седловой точкой функции Лагранжа L(x,y) на множестве х∈Г, y≥0.

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

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


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


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


покажем, что и


для всех α∈[0, 1]. Так как , то найдется х'∈Т такой, что


и аналогично


Нам достаточно показать, что


где x = αx + (1-α)x". Из выпуклости φ(x) и -φ(x) следует



Таким образом,


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


Для каждого ч∈Х ввиду оптимальности х* будет

z0≥φ(x)≥φ(x*), но в Р0 z0<φ(x*).

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

zi≥bi-fi(x)>0, но в Р0 zi<0.

Итак, множества S и Р0 выпуклы и не имеют общих точек. В соответствий с теоремой 2.5 существует гиперплоскость, разделяющая эти множества, то есть существует вектор

(3.12)

такой, что

(3.13)

для всех


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

(3.14)

Неравенство (3.13) остается справедливым и тогда, когда принадлежит границе Р; поэтому, выбрав

z0 = φ(x),
ω0 = φ(x*),
z = b - f(x),
ω = 0,

получим для всех x∈Γ

u0φ(x) + ≥u0φ(x*)(3.15)

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

≥0 для всех x∈Γ.

Так как u≥0 (см. (3.14)), и u≠0 (см. (3.12)), а для всех х∈X будет

b - f(x) ≤ 0,

то при ui > 0 равенство

bi - fi(x) = 0

будет выполняться для всех х∈Х, что противоречит свойству регулярности (3.3).

Значит, из предположения u0 = 0 вытекает u = 0, что противоречит (3.12). Итак, u0 > 0.

Пусть

y* = 1/u0u≥0,

тогда (3.15) примет вид

φ(x*)≤φ(x) + *, b - f(x)>

для всех x∈Γ, а для х = х* отсюда вытекает

*, b - f(x*)>≥0(3.16)

Но y*≥0, а

b - f(x*)≤0

(так как х*∈X); поэтому

*, b - f(x*)> = 0(3.17)

Для любого y ≥ 0 будет

*)>Ͱ0(3.18)

Из (3.16), (3.17) и (3.18) получаем

φ(x*) + *)>≤φ(x*) + *, b - f(x*)>≤φ(x) +

для всех x∈Γ, y≥0 или

L(х*, y)≤L(х*, y*)≤L(х, y*), х∈Γ, y≥0.

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

Пусть в E1 заданы

φ(x) = -x, f(x) = -x2, b = 0, Г = {x: x≥0}.

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

min(-х)

при условиях

2≥0, х≥0.

[ля множества X, состоящего здесь из одной точки x = 0, не выполняются условия Слейтера. Очевидно, что x* = 0 и φ(x*) = 0, но функция Лагранжа

L(x, y) = - х + yx2

при х≥0 и y≥0 вообще не имеет седловой точки.

Замечание. Если множество X определяется только линейными неравенствами, то теорема 3.2 верна без каких бы то ни было дополнительных условий на X. Соответствующая теорема будет доказана несколько позже.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"