Лекция: Теорема

Пусть f, ji и yk – дифференцируемые функции и справедливо свойство Слейтера (то есть найдутся такие ХÎD, что неравенства ji будут строгими). F(X, L) – соответствующая функция Лагранжа. Тогда для того чтобы вектор Х* являлся решением общей задачи максимизации (8.2) необходимо выполнение условий

1) по X:

"Xj* ³ 0;

2) по L:

Приведенные условия оптимальности называются условиями Куна-Таккера. Опуская строгое доказательство, приведем логическое обоснование выражений (8.5)-(8.9).

По существу они являются обобщением классических условий экстремума, определяющих стационарные точки. Условие (8.5) содержит неравенство, так как неотрицательность вектора X означает, что максимум может быть либо при положительном X и тогда производная F по X обязательно равна нулю (случай 1 на рис. 8.3), либо при X=0 и тогда эта производная может быть как равной нулю, так и отрицательной (случаи 2 и 3 на рис. 8.3). Этим же объясняются условия дополняющей нежесткости (8.6): в точке максимума равны нулю либо X, либо производная, либо вместе.

Выражения (8.7)-(8.9) можно обосно–вать аналогично, если учесть, что по L рассматривается минимум F и

.

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

Особую роль условия Куна-Таккера играют в решении задач выпуклого программирования, так как для них они являются не только необходимыми, но и достаточными. В следующем разделе это свойство будет использовано для построения точного метода.