Задача на условный экстремум

Предположительно, что – дифференциальные функции в и ранг матрицы Якоби равен в каждойточке допустимой области , определяемой условием (3). Последнее означает, что градиенты в точках не обращается в нуль и линейно независимы, т.е. условия (3) задают зависимость параметров от параметров. В этом случае:

1. Вводится функция Лагранжа

,

2. дальше минимизируется как функция переменных на безусловный минимум, т.е. используются необходимое и достаточные условия.

Задача выпуклого программирования

(1)

 

(2)

где и - выпуклые дифференциальные функции.

Предположим, что допустимое множество удовлетворяет условию регулярности (условие Слейтера):

Существует точка такая, что для всех , т.е. существует у множества хотя бы одна внутренняя точка.

Говорят, что если в точке выполняется неравенство , то это ограничение является пассивным в точке . Очевидно, что для внутренней точки допустимого множества все ограничения являются пассивными.

Если же в точке какое-то ограничение выполняется с равенством , то оно называется активным в точке .

Обозначим через множество индексов активных ограничений в точке .

.

Введем дополнительные переменные и перейдем от ограниченной – неравенств к ограниченным – равенствам

(3)

функция Лагранжа для задачи (1), (3)

(4)

И получим систему управлений для определения стационарных точек

(5)

(6)

(7)

Условия (5), (6), (7) являются необходимыми условиями минимума в задаче (1), (3).

Исключим из этой системы вспомогательные переменные .

Очевидно, условие (7) эквивалентно (2) (т.к. ).

Умножим каждое равенство (6) на , тогда получим

или (с учетом (7)) . (8)

Составим функцию Лагранжа задачи (1), (2)

.

С учетом соотношения (5), (2) и (8) необходимые условия минимума в задаче (1) (2) принимают вид

(9)

(10)

(11)

Условие (11) означает, что в искомой точке хотя бы один из сомножителей обращается в нуль.

Если , то (ограничение с номером и является активным. Если же в точке (пассивное ограничение), то .

Условие (9) можно заменить

(12)

Откуда следует, что антиградиент в точке минимума является линейной комбинацией внешних нормалей к активным для точки ограничениям.

Тогда с учетом формул (9) – (11) можно сформулировать следующие необходимые условия минимума в задаче (1), (2) с допустимым множеством , удовлетворяющим условию регулярности.

Если является решением задачи (1) (2), то для некоторых чисел

, выполняются соотношение

(13)

(14)

(15)

(16)

которые называются условиями Куна-Таккера.

Эти условия являются и достаточными условиями минимума в задаче (1), (2).

Теорема Куна-Таккера. Для того, чтобы была решением задачи выпуклого программирования (1), (2) с дифференцируемыми функциями и достаточно ( если удовлетворяет условию регулярности, то и необходимая), чтобы существовал сектор , для которого выполняются условия (13) – (16).

Задача математического программирования со смешанными ограничениями.

(17)

(18)

(19)

предполагаются дифференцируемыми.

Справедлива следующая теорема Куна-Таккера:

Пусть в задаче (17) – (19) функции выпуклы и дифференцируемы, функции – линейны, а допустимое множество удовлетворяет условию регулярности.

Тогда, для того, чтобы была решением задачи (17) – (19), необходимо и достаточно, чтобы существовали векторы и для которых выполняются условия:

(20)

(21)

(22)

(23)

(24)