Без доказательства

Теорема Каруша-Джона:

Пусть x* - экстремальная точка задачи нелинейного программирования.

Пусть в точке x* градиенты функций, соответствующие активным ограничениям, линейно- независимы, тогда существуют l₁,...,l_m ³0 (не все нулевые), для которых выполняются следующее условия:

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

Доказательство:

Как показано выше, не существует такого S, для которого выполнялись бы следующие неравенства:

, для любого iÎI(x*).

Воспользуемся леммой Фаркаша, составим матрицу:

, iÎI(x*).

Не существует S такого, ÷òî AS<0. Следовательно, существуют такие, что (по лемме Фаркаша) выполняются условия:

(x*) (l_i: = 0, если iÏI(x*)).

Для активных ограничений g_i = 0, для неактивных отсюда l_i = 0. Тогда

l _i g_i (x*) = 0,, так как если бы он был равен 0,то градиенты, соответствующих активных ограничений, были бы линейно- зависимы, что противоречит условию. Разделим (*) на l ₀ и получим требуемое утверждение. Условие линейной независимости градиентов функций активных ограничений иногда называют условием регулярности.