2017-11-01
826Теорема Куна-Таккера
Теорема Куна-Таккера была сформулирована в 1951 г. Рассмотрим задачу выпуклого программирования
, (з)
где 
– линейное пространство, 
– выпуклые функции на , 
– выпуклое подмножество .
Для задачи (з) введем понятие функции Лагранжа:
.
Здесь 
– множители Лагранжа. (Ограничение 
в функцию Лагранжа не включается).
Теорема Куна-Таккера. 1. Пусть 
. Тогда, существуют 
, «нерон», такие, что выполняются
а) принцип минимума
;
б) условие неотрицательности
;
в) условие дополняющей нежесткости
.
2. Если 
, то условий а)-в) достаточно для того, чтобы допустимая точка .
3. Для того, чтобы , достаточно выполнения условия Слейтера, т. е. существования точки 
, для которой 
.
Комментарии к теореме Куна-Таккера.
1.Соотношение а) отражает мысль Лагранжа в наиболее завершенной форме: если 
доставляет минимум в задаче с ограничениями (типа неравенств), то эта же точка доставляет минимум функции Лагранжа (в задаче без тех ограничений, которые включены в функцию Лагранжа).
|
|
|
2. Соотношения б) и в) характерны для задач с неравенствами.
Доказательство теоремы Куна-Такккера опирается на теорему отделимости для конечномерного случая (д-во в АТФ, п. 1.3.4.).
Конечномерная теорема отделимости. Пусть 
– выпуклое подмножество в 
, не содержащее точки 
. Тогда существует набор чисел 
таких, что для 
выполняется неравенство 
.
Другими словами гиперплоскость 
, проходящая через 0, делит на две части, в одной из которых целиком лежит .
Двумерная иллюстрация: можно провести через 0 гиперплоскость таким образом, что множество останется по одну сторону: 
(
).
Если – невыпуклое множество, этого сделать было бы нельзя.
Перейдем к доказательству теоремы Куна-Таккера. Докажем пункт 1.
1. Н е о б х о д и м о с т ь. Пусть . Будем считать, что 
, – иначе возьмем новую функцию 
.
Введем множество
,
.
Дальнейшую часть доказательства разбиваем на несколько этапов.
I. Множество – непусто.
Возьмем 
и в качестве 
– очевидно, так как у нас 
=0,
– очевидно, так как у нас 
(см. (з)).
II. Множество – выпукло.
Возьмем 
и 
. Тогда 
и 
такие элементы из (
), что (см. множество ):
, 
,
, 
.
Надо доказать, что 
такая, для которой выпуклая комбинация 
будет принадлежать множеству : 
.
Положим 
. Тогда, 
, поскольку – выпукло, а так как все функции выпуклы, то
т. е. точка 
– выпукло.
III. Точка 
не принадлежит .
Действительно, если 
, то 
такая, что 
, 
. Но из этих неравенств следует, что не является решением задачи (з). Значит, 
.
Итак, – выпукло, , 
. Следовательно, можно применить конечномерную теорему отделимости, согласно которой 
такие, что
|
|
|
. (*)
Из I, II, III (*).
IV. Докажем условие неотрицательности: .
Возьмем в качестве 
, где 
и 1 стоит на 
-м месте. 
(см. п. I).
подставим в (*) 
. Так как – произвольно, то 
.
V. Докажем условие дополняющей нежесткости: .
а). Если 
, то условие очевидно.
б). Если 
, то 
(см. формулировку (з)).
Возьмем 
, где 
и 
стоит на 
-м месте.
– достаточно взять точку в качестве точки 
в А: 
– очевидно, так как ; 
при 
и 
при 
– очевидно.
подставим в (*) 
,
причем 
. В силу произвольности 
получаем 
, но 
(см. IV, т. е. условие б)) 
, если 
.
VI. Докажем принцип минимума.
Пусть , 
, . Покажем, что 
. 
– очевидно, 
– очевидно .
Подставим 
в (*) 
(в силу произвольности ) 
, так как =0 по предположению, – по условию дополняющей нежесткости. Отсюда следует принцип минимума: 
.
Итак, пункт 1 теоремы Куна-Таккера доказан.
Докажем пункт 2.
2. Д о с т а т о ч н о с т ь. Пусть 
. Но тогда
.
В логической цепочке присутствуют пункты а), б), в).
3. Докажем утверждение 3 от противного.
Пусть условие Слейтера выполняется (
: 
), но все-таки 
. Приведем к противоречию.
,
так как, в силу условия «нерон», не все 
, 
. Тогда,
.
А это противоречит принципу минимума.
Теорема доказана. 
Пример. 
. Решим поставленную задачу, используя теорему Куна-Таккера. Функция Лагранжа:
.
Выпишем условия, определяющие решение данной задачи выпуклого программирования:
, так как выполняется условие Слейтера: 
Можно положить 
.
Из соотношений (1), (2) следует, что 
и 
. Тогда, учитывая, что , из условия дополняющей нежесткости (4) получаем
.
Так как, в силу условия неотрицательности (3): 
, то 
. При значении функция Лагранжа стремится к 
при 
. Значит, по следствию из теоремы Вейерштрасса, минимум функции Лагранжа, в силу единственности найденного решения, достигается в точке 
. Достаточные условия теоремы Куна-Таккера выполнены, следовательно, 
и 
.
