Файл: Методы оптимизации в статистических задачах управления..pdf

По теореме о методе штрафных функций точка х+ удовлетворяет ограничениям (255). Поэтому условие для А,+ можно представить в более компактном виде:

#5 *0, i = 1 , 2, . . т.

Это условие принято называть «условием дополняющей не­ жесткости».

Таким образом, необходимым условием оптимальности точки х+ в задачах (255), (256) в предположении наличия хотя бы одной внутренней точки в области D является существование системы

неотрицательных параметров I t , Xt, . . ., Х+, для которых удов­ летворяются условия (263), (264). Это утверждение составляет содержание основной теоремы нелинейного программирования —• теоремы Куна-Таккера в дифференциальной форме [115, 138].

Легко увидеть, что теорема Куна-Таккера является обобще­ нием необходимого условия безусловного минимума. В самом деле, если точка х+содержится внутри области D, т. е. Ft (х+) <0, (г = 1, 2, . . ., т), то из условий (263), (264) автоматически следует

^oW _ 0

дх ~ *

Поясним математический смысл параметров Xf, Х+, . . ., Х+.

Рассмотрим некоторое обобщение задачи (255), (256). Пусть тре­ буется определить х+ из условия

которое означает, что параметр Х£ характеризует чувствитель­

ность минимального значения функции к ограничению Fk (х) + + 8k = 0 при 6 = 0. Это вполне согласуется с условием (264),

Точка минимума этой функции z+зависит от параметров а и б:

z+ = z+ (а, б).

В соответствии с теоремой о методе штрафных функций имеем

1ішФ(г+(а/, б), аі) — F0 (х+(8)).

у->оэ

Дифференцируя это равенство по параметру бА и учитывая, что z+минимизирует Ф (х, а, б), получим

что и требовалось доказать.

Для задачи выпуклого нелинейного программирования, т. е. в предположении, что функции Ft (х) (і = О, 1 , 2, . . ., т) вы­ пуклы, необходимое условие оптимальности (263) или (264) можно представить в более симметричном виде. Построим функцию Лаг­ ранжа:

Так как по предположению Ft (х), (і = О, 1, 2, . . ., т) — вы­ пуклые функции, то при Хі О (і = 1, 2, . . ., т) функция L (х, К) также выпукла по х. Из условия (263) следует, что

114

Поэтому в соответствии с тем, что L (х, Я) выпукла по х, имеет место условие

причем это условие удовлетворяется для любой точки п-мерногс пространства Еп. С другой стороны, так как точка х+принадлежит области D, т. е. для нее удовлетворяется система ограничений (255), то для совокупности неотрицательных параметров Я(. (і = 1, 2 , . . ., т) выполняется условие

Объединяя формулы (268) и (269), получаем, что если при ре­ шении задачи выпуклого программирования окажется, что в об­ ласти D содержится хотя бы одна внутренняя точка, то для опти­ мального решения х+ можно найти такую совокупность неотри­

цательных параметров Я = я^, яt , . . . , Я+, при которой выпол­ няется неравенство

Соотношения (270) или (271) представляют собой необходимое условие оптимальности для задачи выпуклого нелинейного про­ граммирования (теорема Куна-Таккера). Легко показать, что эти соотношения одновременно являются достаточным условием оп­ тимальности для задачи нелинейного программирования (255), (256) общего вида при отсутствии требований выпулкости функ­ ций Ft (х) (і = 0, 1, 2 . . ., т) и выполнения условия Слейтера [46]. Действительно, из неравенства (270) следует

т

І= 1

Поскольку для любого допустимого вектора х, принадлежащего области D, определяемой условием (255), имеет место условие

т

I i X t F ( x ) < 0, то из правой части неравенства (272) и условия

і=і

(273) следует:

т

Fo (х) > F0 (х+) - У і г р . {х) ^ р о (х+).

і = 1

Для любой точки X d D. Это неравенство и доказывает доста­ точность условия (270) для оптимальности точки х+в общей задаче нелинейного программирования.

7. Градиентные методы решения задач нелинейного программирования

Впредыдущем параграфе были выведены необходимые условия оптимальности (263), (264) или (270), для задачи нелинейного про­ граммирования. Используя эти условия, в очень редких случаях удается получить аналитическим методом решение реальных задач. Однако, анализируя условия оптимальности, можно по­ строить некоторые итерационные процедуры, которые дают воз­ можность найти численное приближенное решение.

Вчастности, Эрроу и Гурвиц [115] предложили определять оптимальное решение задачи (255), (256) как седловую точку функции Лагранжа (267) в соответствии с необходимым и доста­ точным условием (270). Для случая строгой выпуклости [109]

функций F( (х), (і — 0, 1,2, . . ., т) и в предположении выпол­ нения условия Слейтера ими было доказано, что решение системы дифференциальных уравнений

сходится к точному решению задачи нелинейного программиро­ вания при t —» оо:

Ііш X (t) = X*

£->• со

скалярной переменной у. На основании этого предлагается ите­ рационная процедура следующего вида:

116