17-5. Теорема Куна-Таккера

Формулы (17-20)-(17-25) составляют содержание теоремы Куна - Таккера, только в отличие от предыдущего параграфа, где функция Ф (х, Я) была произвольной, в данном случае она является функцией Лагранжа для задачи максимизации нелинейного программирования, а (х_опт, λ_опт) - точка экстремума. Сама теорема может быть сформулирована следующим образом: соотношения (17-20)-(17-25) являются необходимыми и достаточными условиями, для того чтобы точка х_опт представляла собой решение задачи выпуклого нелинейного программирования:

Сведем исходную задачу к классической постановке. Для этого прежде всего ограничения-неравенства φ_i(х)≥b_i сведем к равенствам, введя и переменных x_si ≥ 0 (i = 1,2,..., u), соответствующим неравенствам. Остальные m - u ограничений считаются строгими равенствами. Тогда

Тем самым допускается, что часть из m неравенств имеет вид строгих равенств.

Предположим, что для этой задачи х = х_опт. Обозначим через J множество индексов j (j = 1, ..., n) у для которых x_jопт > 0, а через J - множество индексов j, для которых x_jопт = 0. Аналогично будем считать, что I - множество индексов i (i = 1, ..., u)у для которых φ_i(х_oпт) = b_i, I - множество, состоящее из индексов i, для которых ограничения на φ_i(х_опт) выполняются со знаком строгого неравенства φ_i(x_опт)<b_i. Заметим, что речь идет только о точке оптимума х_опт и знак нестрогого неравенства "≥" теряет свой смысл и соотношение превращается или в строгое неравенство (типа 5>4) или в строгое равенство (типа 3=3). На основании результатов, полученных в § 17-3, можем написать, что

так как множество J соответствует внутренней области допустимых значений, и λ_iопт = 0 ,i∈I, так как множество I соответствует ограничениям в виде строгих неравенств, которые можно не учитывать. Далее

так как множество J соответствует границе области допустимых значений.

Соотношения (17-37) и (17-38) обеспечивают выполнение условия (17-20)

Теперь нетрудно убедиться, что

Это соотношение обеспечивает выполнение формулы (17-21). Затем имеем:

так как множество I соответствует границе области. Эти разности неотрицательны, а остальные n - u равны нулю по условию. Формула (17-39) обеспечивает выполнение условия (17-23), которое по существу совпадает с ограничениями в исходной задаче нелинейного программирования. Наконец, условие (17-24) выполняется в силу доказанных ранее соотношений (17-17), согласно которым для ограничений в виде строгих неравенств

соответствующий множитель Лагранжа λ_i = 0 и λ_i ≠ 0 только при

Таким образом, доказано, что в точке оптимума задач нелинейного программирования выполняются необходимые и достаточные условия

существования седловой точки (необходимость теоремы Куна - Таккера). Для доказательства достаточности этой теоремы необходимо дополнительно потребовать выпуклости (вогнутости) и использовать методы доказательства достаточности условий (17-20) - (17-25) для существования седловой точки. Тем самым доказана теорема Куна - Таккера для случая дифференцируемых функций.

В литературе [Л. 96] имеются доказательства этой теоремы для не дифференцируемых функций F (х) и φ_i(х). В этом случае теорема формулируется следующим образом: вектор х_опт тогда и только тогда является решением задачи (17-36), когда существует вектор λ_опт, такой, что справедливы соотношения

для всех х≥0 и λ≥0, т. е. задача о максимизации F (х) соответствует задаче о седловой точке, иными словами, задаче о максимине для функции Φ (х, λ).