1) Пусть . - точка абсолютного минимума в задаче выпуклого программирования. Тогда существует ненулевой вектор множителей Лагранжа такой, что выполняются условия:
а) принцип минимума для функции Лагранжа :
;
б) условия дополняющей нежесткости:
;
в) условия неотрицательности:
.
2) Если для допустимой точки выполнены условия а), б), в) и , то .
3) Если для допустимой точки выполнены условия а), б), в) и выполнено условие Слейтера (т.е. ), то . ■
Теорема Куна-Таккера дает необходимые и достаточные условия абсолютного минимума в задаче выпуклого программирования.
Замечание. Если в выпуклой задаче (1) отсутствует ограничение в виде включения , (т.е. ), то условие а) теоремы Куна-Таккера равносильно условию стационарности функции Лагранжа : . Это следует из того, что функция Лагранжа с неотрицательными множителями Лагранжа является выпуклой функцией. А по аналогу теоремы Ферма для выпуклых функций условие является необходимым и достаточным условием абсолютного минимума функции Лагранжа в точке .
Задача. Найти расстояние от точки до конуса .
Решение. Формализуем поставленную задачу, взяв в качестве целевой функции квадрат расстояния от точки до точки, принадлежащей конусу:
.
Составим функцию Лагранжа
.
Выпишем необходимые условия абсолютного минимума:
а) ,
б) ;
в) .
Если , то из условия а) получим , т.е. вектор множителей Лагранжа равен нулю, поэтому этот случай не подходит.
Положим . Разберем отдельно два случая: и .
I.
Рассмотрим два варианта выполнения условия дополняющей нежесткости.
Iа)
Следовательно, если , то
.
Iб)
Следовательно, если , то
,
. Тогда расстояние от точки до конуса равно
.
II.
IIа) если , то
.
IIб) если , то
, .
Ответ: Если , то
.
Если , то
,
.
Если , то ,
. ●