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


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

3.7. Задача с линейными ограничениями

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

Пусть допустимое множество имеет вид

(3.28)

Будем рассматривать следующую задачу выпуклого программирования:

(3.29)

(функция φ(х) - выпуклая).

Аналогично (3.25) и (3.26) для точки х обозначим

I(x) = {i: (Ax)i = bi}, (3.30)
J(x) = {j: xj = 0}.(3.26)

Напомним, что вектор s≠0 будет возможным направлением в точке x∈R1, если существует λ0>0 такое, что для всех λ∈[0, λ0] точка x + λs принадлежит R1.

Легко видеть, что следующие неравенства являются [необходимыми и достаточными условиями того, чтобы отправление s было возможным в точке х:

(As)i≥0 для i∈I(x), (3.31)
sj≥0 для j∈J(x), (3.32)

Теперь можно сформулировать и доказать следующую теорему.

Теорема 3.5. Для того чтобы для выпуклой непрерывно дифференцируемой функции φ(х) существовала в R1, оптимальная точка х*, то есть


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

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

Необходимость. Пусть х* оптимален. Поскольку функция φ(x) выпукла, то из теоремы 2.12 (см. замечание к теореме) следует, что

(3.33)

для всех s таких, что


Пусть для простоты

I(x*) = {1, 2, ..., k≤m} и J(x*) = {1, 2, ..., l≤n}

(что не ограничивает общности). Далее воспользуемся теоремой Фаркаша. Для того чтобы использовать принятую нами в теореме Фаркаша форму записи, введем матрицу

BT = [a1, a2, ..., ak, e1, e2, ..., el],

где аi - i-й столбец матрицы АТ, а еj - j-й координатный вектор. Теперь условия (3.31) и (3.32) можно записать так:

Bs ≥ 0. (3.34)

Для матрицы В и векторов φ'(х*) и s выполняются условия теоремы Фаркаша, поэтому существует такой вектор

uT = (y1, y2, .... yk, v1, v2, ...., vl)≥0,

что

φ' (х*) = ВTu,

то есть


(3.35)

В теореме 3.4 доказано, что такое представление эквивалентно неравенствам Куна -Таккера (3.19)-(3.24) и, следовательно, по теореме 3.3 существует y* такой, что х*, y* - седловая точка функции L(x, y) в области x≥0, y≥0.

Замечание. В этой теореме на множество R1 не накладывались условия регулярности, в отличие от теорем 3.2 и 3.4.

В теореме Куна - Таккера для доказательства того что из оптимальности х* следует, что пара х*, y* является седловой точкой функции Лагранжа L(x, y), требовалось условие регулярности Слейтера. Здесь же из оптимальности х* сразу следует соотношение (3.35), а значит (по теореме 3.4), следуют неравенства (3.19)-(3.24), а по теореме 3.3 эти неравенства определяют седловую точку функции Лагранжа L(x, y).

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





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


Диски от INNOBI.RU




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