Тема 2. Оптимизационные методы получения детерминированных оценок (стр. 8 )

при ограничениях

, (2.12)

. (2.13)

В векторной форме задача (2.11)-(2.13) представляется в виде

(2.14)

при ограничениях

, , (2.15)

. (2.16)

Допустим, что целевая функция (2.14) является вогнутой, а функции , , входящие в систему ограничений (2.15) – выпуклы. Тогда нетрудно показать, что допустимая область задачи, определяемая системой (2.15 и (2.16, является также выпуклой. Тем самым поставленная задача есть задача максимизации вогнутой функции на выпуклом множестве, и, следовательно, она является задачей выпуклого программирования.

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

Для задачи выпуклого программирования (2.14-(2.16) образуем функцию Лагранжа

,

где , , – множители Лагранжа. Будем писать для краткости . Тогда функция Лагранжа примет вид

.

Функции Лагранжа отводится важное место: при определенных условиях решение задачи выпуклого программирования сводится к отысканию седловой точки функции Лагранжа.

Пара , называется седловой точкой функции , если выполняется неравенство

для всех , .

Следующая теорема играет основную роль в математическом программировании.

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

Весьма важным для практического использования является следствие из теоремы Куна-Таккера, которое определяет необходимое и достаточное условие существования седловой точки у функции Лагранжа, а, значит, и условие оптимальности допустимого решения задачи выпуклого программирования.

В предположении дифференцируемости функций и , , входящих в задачу (2.14)-(2.16), запишем две системы неравенств по следующей схеме (табл. 2.7).

Таблица 2.7

Система неравенств I	Система неравенств II
...	...
...	...

Система неравенств I есть совокупность условий (2.12)-(2.13). Система II определяет систему ограничений двойственной задачи. Будем, как и для линейного программирования, два неравенства, записанные в одной строке, называть сопряженными парами условий.

Используя обозначение для функции Лагранжа, указанные системы неравенств можно переписать в сокращенном виде (табл. 2.8).

Таблица 2.8

I	II
	,
	,

Следствие. Пусть функции и , задачи выпуклого программирования (2.11)-(2.13) непрерывно дифференцируемы при , , и система ограничений (2.12) удовлетворяет условию регулярности Слейтера. Тогда для оптимальности допустимого решения необходимо и достаточно, чтобы существовало , удовлетворяющее системе неравенств II, и такое, что в каждой паре сопряженных условий напротив строгого неравенства стояло бы равенство. Другими словами, должны выполняться соотношения

, ,

, .

Пример 2.9. Определить, является ли оптимальным решением для следующей задачи нелинейной оптимизации

при ограничениях

,

.

Нетрудно видеть, что целевая функция вогнута. Система ограничений линейна и потому представляет собой выпуклую область. Ориентируясь на табл. 2.6, запишем неравенства данной задачи и напротив них соответствующие сопряженные условия (табл. 2.9)

Таблица 2.9

I	II

Видим, что является допустимым решением задачи. Для этого решения первое, второе и четвертое неравенства системы I выполняются как строгие, значит напротив должны стоять равенства, то есть