Выпуклое программирование. Теорема Куна-Таккера.

Задачей выпуклого программирования или выпуклой задачей называется следующая задача на : где X- векторное пространство (не обязательно нормированное). множество s состоит из бесконечных числовых последовательностей. Зададим на X метрику: – она не является нормой т.к. не выполняется равенство треугольника. X – основное пространство задачи; f – основной функционал, M – подмножество ограничений.

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

Лемма. Пусть X – нормированное пространство, тогда в выпуклой задаче локальный минимум является и глобальным.

Алгоритм поиска решения:

1. Составляем функцию Лагранжа

2. Находим выполняется ли условие минимума: где – допустимое решение задачи – условие не жесткости, т.е. – условие неотрицательности, т.е.

3. Находим критические точки, т.е. допустимые точки, которые удовлетворяют условиям 2.

Замечание. Обычно проверяют случай, когда Если то выполняется условие Слейтера, т.е. для которого

4. Если критическая точка найдена для то она является решением задачи. Если же найден допустимый план только для то необходима проверка дополнительных условий.

Теорема Куна-Таккера. 1. Пусть X – линейное векторное пространство, - подмножество в X, тогда, если является решением задачи выпуклого программирования, то найдется такой ненулевой вектор во множестве Лагранжа , что выполняются следующие условия:

принцип множителей Лагранжа.

условие дополняющей не жесткости, т.е.

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

2) Если то а)-в) являются достаточными условиями, чтобы являлся решением задачи.

3) Для того, чтобы достаточно выполнения условия Слейтора, т.е. такой, что .