Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Читайте также:
  1. Взаимно простые числа. Основная теорема арифметики
  2. Дивергенция вектора. Теорема Остроградского–Гаусса
  3. Інтегральна теорема Муавра-Лапласа
  4. Квантование непрерывных сигналов и теорема прерывания
  5. Лекция 7. § 141. Теорема о том, что всякое уравнение второй степени с двумя неизвестными определяет эллипс, гиперболу, параболу или две прямые линии.
  6. Основна теорема арифметики цілих невід’ємних чисел.
  7. Основная теорема
  8. ОТНОСИТЕЛЬНАЯ ЧАСТОТА. ТЕОРЕМА БЕРНУЛЛИ
  9. Ошибки выборочного наблюдения. Предельная теорема, предельная ошибка
  10. Подпоследовательность. Теорема Больцано-Вейерштрасса
  11. ПРОИЗВЕДЕНИЕ СОБЫТИЙ. ТЕОРЕМА УМНОЖЕНИЯ
  12. Ротор вектора. Теорема Стокса



1. Если – решение задачи выпуклого программирования, то найдется ненулевой вектор множителей Лагранжа , такой что для функции Лагранжа выполняются условия:

а) принцип минимума для функции Лагранжа

б) дополняющей нежесткости

в) неотрицательности

2. Если для допустимой точки выполнены условия а-в и , то .

3. Если для допустимой точки выполнены условия а-в и множество допустимых элементов удовлетворяет условию Слейтера, то .

Доказательство: Пусть . Не ограничивая общности, считаем, что . Положим

непустое выпуклое множество.

Действительно, , так как в определении можно положить .

Докажем выпуклость. Пусть . Так как , такие что

положим

.

Обозначим – открытый луч в пространстве . Ясно, что – непустое выпуклое множество. Покажем, что . Действительно, если бы существовала точка , то ввиду определения множества отсюда следовало бы, что имеется элемент , для которого выполняются неравенства . Но из этих неравенств следует, что для допустимой точки , т.е. . Получили противоречие с условием теоремы . Следовательно, .

По первой теореме отделимости множества можно отделить, т.е. существует вектор , для которого

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

(*)

1. Условие неотрицательности. Так как любой вектор с неотрицательными компонентами принадлежит , то , где 1 стоит на i-ом месте i=0,…m. Подставив эту точку в (*) получим, что .

Условие дополняющей нежесткости. Нетрудно видеть, что . Действительно, возьмем в определении точку , тогда и нужные неравенства выполняются. Подставив эту точку в (*), имеем . Если , то, так как по уже доказанному условию неотрицательности , – это противоречит условию допустимости точки . Значит, .

Принцип максимума. Возьмем точку , тогда точка . Отсюда по неравенству (*)

так как положили и уже доказали условие дополнительной нежесткости .

2. Пусть для допустимой точки выполнены условия а-в и . Положим . Тогда для любой допустимой точки будет выполняться неравенство

т.е. .

3. Пусть для допустимой точки выполнены условия а-в и множество допустимых значений удовлетворяет условию Слейтера. Предположим при этом, что . Так как , то в силу условия неотрицательности существует . Следовательно,

Но это неравенство противоречит условию а. Значит, наше предположение не верно. Поэтому , и по доказанному п. 2 .

 





Дата добавления: 2014-01-05; Просмотров: 354; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.80.132.10
Генерация страницы за: 0.019 сек.