<< Предыдущая

стр. 163
(из 163 стр.)

ОГЛАВЛЕНИЕ

-
Из второго из этих условий следует, что при xi > 0
?L(x, ?)
-
= 0.
?xi
С другой стороны, если ?L(x, ?)/?xi < 0, то xi должен быть равен нулю.
- -
Другая модификация теоремы связана с наличием в задаче ограничений в виде равенств.
Обозначим множество соответствующих индексов через E. Задача принимает следующий
вид:
?(x) > max
?j(x) > 0, j ? {1, ..., m}\E,
?j(x) = 0, j ? E, (***)
x ? X,
xi > 0, i ? P ? {1, ..., n}.
При этом в теореме Джона снимается условие, что все множители Лагранжа неотрица-
тельны — множители Лагранжа ?j при j ? E могут иметь произвольный знак.
Теорема Джона не гарантирует, что множитель Лагранжа целевой функции, ?0, отличен от
нуля. Однако если ?0 = 0, то условия Куна-Таккера характеризуют не решение рассматри-
-
ваемой задачи, а структуру множества ограничений в точке x и теорема не имеет непо-
средственной связи с интересующей нас задачей максимизации функции ?(?), поскольку
градиент самой функции ?(?) «пропадает» из условий Куна — Таккера. Поэтому важно

700
701
охарактеризовать условия, которые гарантируют, что ?0 > 0. Такие условия называются
условиями регулярности.
Одно из условий регулярности формулируется следующим образом: градиенты активных
-
ограничений в точке x линейно независимы.
-
Обозначим через A множество индексов тех ограничений, которые в точке оптимума x
активны, т.е.
?j(x) = 0 ? j ? A.
-
Тогда если градиенты ограничений — векторы
-
{??j(x)}j?A
линейно независимы, то ?0 > 0.
Заметим, что если ?0 > 0, то без потери общности можно считать ?0 = 1, что обычно и дела-
ется. Соответствующую теорему и называют собственно (прямой) теоремой Куна — Так-
кера.

Прямая теорема Куна — Таккера (необходимое условие оптимальности)
Пусть функции ?(?), ?1(?), ..., ?n(?) дифференцируемы, и x — решение задачи (*), такое
-
что x ? int(X) и выполнено условие регулярности указанного типа.
-
Тогда существуют множители Лагранжа ?j > 0, j = 1, ..., m, такие что при ?0 = 1 выполнены
следующие соотношения:
?L(x, ?)
-
= 0, i=1, ..., n
?xi
и
?L(x, ?)
-
m
?j = 0.
¤
??j
j=1



Несложно переформулировать эту теорему для задач (**) и (***). Здесь требуются такие
же модификации условий Куна — Таккера, как и в теореме Джона.
Условие
?L(x, ?)
-
= 0, i=1, ..., n
?xi
можно переписать в виде:
m
??(x) = –¤?j??j(x).
- -
j=1

Это соотношение показывает, что в точке оптимума градиент целевой функции является
линейной комбинацией градиентов ограничений, причем все коэффициенты этой линей-
ной комбинации неположительны.
Один из вариантов обратной теорема Куна — Таккера утверждает, что при вогнутости
функций ?(?), {?k(?)} выполнение этих условий в допустимом решении x (т.е. точке, удов-
-
летворяющей ограничениям) при некоторых множителях Лагранжа, удовлетворяющих
-
требованиям прямой теоремы, гарантирует, что x является решением задачи.



701
702
Обратная теорема Куна–Таккера (достаточное условие оптимальности)
Пусть функции ?(?), ?1(?), ..., ?n(?) дифференцируемы и вогнуты, множество X выпукло и
точка x допустима в задаче (*), причем x ? int(X).
- -
Пусть, кроме того, существуют множители Лагранжа ?j > 0, j = 1, ..., m, такие что при
?0 = 1 выполнены следующие соотношения:
?L(x, ?)
-
= 0, i=1, ..., n
?xi
и
?L(x, ?)
-
m
?j = 0.
¤
??j
j=1

-
Тогда x — решение задачи (*).


Теорему можно очевидным образом переформулировать для задач (**) и (***).




702

<< Предыдущая

стр. 163
(из 163 стр.)

ОГЛАВЛЕНИЕ