5. Критерий оптимальности; теорема Куна-Таккера

Данный раздел посвящен рассмотрению вопроса об оптимальности найденной точки в основной задаче выпуклого программирования. Рассматривается задача

f(x) —► min{x € X},(1) где X = {x | φ_j(x) <=0(j = 1, m)}. (2)

Если функции f(x) и φ_j(x) (j = l,m) выпуклы, то задача (1)-(2) называется основной задачей выпуклого программирования. Пусть задана некоторая точка x* € X. Ограниче­ние φ_j(x) <=0 называется активным в этой точке, если φ_j(x*) = 0. Множество индексов активных ограничений обозначим через

I(x*) = {j€{1,...,m}| φ_j(x*) = 0}.

Функция

F(x,y) = f(x) +sum{j=1,m}(y_jφ_j(x)),

определённая для всех x€ Е_п, у > 0, называется функцией Лагранжа для задачи выпук­лого программирования. Пара (x*,у*), где x* € Е_п, у* >= 0, называется седловой точкой функции F(x, у), если F(x*, у) < F(x*, у*) < F(x, у*) для всех x € Еn, у >= 0. В дальнейшем будем считать, что функции f(x) и φ_j(x) (j = l,m) (и, следовательно, функция Лагранжа) непрерывно дифференцируемы.

Теорема 10. Для того чтобы точка х* € X была точкой глобального минимума основ­ной задачи выпуклого программирования (1)-(2), достаточно существования таких чисел yj >= 0 (j € I(х*)), что выполняется равенство –f’(x*)=sum{j€I(x*)}( y_jφ’_j(x*)),

Другими словами, если (х*,у*) — седловая точка функции Лагранжа, то х* — это точ­ка глобалвного минимума для задачи ввшуклого программирования. Чтобы выполнялось обратное утверждение, необходимо наложить дополнительное условие на множество X. Ес­ли существует такая точка х € X, что φ_j(x) < 0 для всех j = 1,т, то говорят, что это множество удовлетворяет условию регулярности Слейтера.

Теорема Куна—Таккера (дифференцируемый случай). Если функции f(x) и φ_j(x) (j = 1, т) выпуклы, а множество X = {х |φ_j(x) <=0(j = 1,m)} удовлетворяет условиям регулярности Слейтера, то для оптимальности точки х* € X необходимо и достаточно существования таких чисел yj >= 0 (j € I(х*)), что –f’(x*)=sum{j€I(x*)}( y_jφ’_j(x*)),(з)

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

Теорема 11. Для того чтобы точка х* € X была точкой глобального минимума вы­пуклой функции f(x) на множестве X = {х | <a_j ,x>-b_j <= 0 (j = l,m)} необходимо и достаточно существование таких чисел yj >=0(j = l,m), что –f’(x*)=sum{j€I(x*)}( y_ja_j),

В Приложении рассматривается метод возможных направлений, в котором используется следующая

Теорема 12. Для того чтобы точка х* € X была точкой глобального минимума за­дачи выпуклого программирования (1)-(2), достаточно, чтобы для всех векторов s, удо­влетворяющих системе < φ’_j(x*), s> <=0 (j € I(х*)), выполнялось условие (f'(x*),s) >= 0.

Рассмотрим примеры применения приведённых выше теорем. Общая схема проверки оптимальности точки х* для задачи (1)-(2) такова:

1. Убедиться, что решаемая задача действительно является задачей выпуклого програм­мирования (т. е., что все функции выпуклы и задача на минимум).

2. Проверить, что X удовлетворяет условиям Слейтера (кроме случая линейных огра­ничений) .

3. Проверить, что х* € X и найти множество индексов активных ограничений I(х*).

4. Записать и решить систему (3). Точка х* будет оптимальной в том и только в том случае, если система (3) имеет решение у* >= 0.