Объединяя теоремы 2 и 3, можно сформулировать необходимое и достаточное условие глобального максимума для задач выпуклого программирования, для которых выполнено условие Слейтера.

Теорема 4 (необходимое и достаточное условие наличия в точке глобального максимума)

Пусть в задаче нелинейного программирования

1)  функции непрерывно дифференцируемы в некоторой окрестности точки ;

2)  функции , выпуклы (в частности, линейны) на ;

3)  выполнено условие Слейтера.

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

Приведенное в теореме 3 достаточное условие носит глобальный характер. Но его можно несколько ослабить для локального случая.

Теорема 5 (достаточное условие локального максимума – локально-выпуклый случай)

Пусть существует такая окрестность точки , что вогнута в или на , где Х - допустимое множество, а для которых (эффективные ограничения) выпуклы в (это условие можно заменить на выпуклость множества ). Тогда из выполнения условий Куна-Таккера в точке следует наличие условного локального максимума в этой точке. Если при этом функция строго вогнута, то локальный максимум строгий.

2.4.3.  Седловая точка функции Лагранжа. Теорема Куна-Таккера

Рассмотрим функцию Лагранжа

для задачи максимизации

F(х)→ max при gj(x) ≤ bj, j = 1,2,…,m; x ≥ 0.

Напомним, что функция Лагранжа для задачи нелинейного программирования задана при x0 и λ0.

Определение. Точка (x*, λ*), где x*0 и λ*0, называется седловой точкой функции Лагранжа, если

L(x, λ*)L(x*, λ*) L(x*, λ)

для всех x0 и λ0.

Оказывается, что седловая точка функции Лагранжа (1) задачи оптимизации (2) имеет удивительные свойства, которые мы рассмотрим далее.

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

Отметим, что в условии Слейтера в точке х0ÎX лишь нелинейные функциональный ограничения gj(x0) ≤ bj, j=1,2,…,m, должны выполняться в виде строгих неравенств.

Теорема Куна-Таккера. Пусть в задаче выпуклого программирования множество X удовлетворяет условию Слейтера. Тогда для того, чтобы вектор х* являлся решением задачи выпуклого программирования, необходимо и достаточно, чтобы нашелся такой вектор λ*0, что пара (x*, λ*) составляет седловую точку функции Лагранжа, т. е.

L(x, λ*)L(x*, λ*) L(x*, λ) для всех x 0 и λ0.

[1] Теорема 3.1 доказана, например, в книге: С. Карлин «Математические методы в теории игр, программировании и экономике». М.: Мир, 1964.

[2] См. Васильев методы решения экстремальных задач. М.: Наука, 1980, стр. 170.

[3] См. , , Фомин управление. М.: Наука, 1979.

[4] См. Васильев методы решения экстремальных задач. М.: Наука, 1980, стр. 173.

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5