Оптимизация при ограничениях в форме неравенств

Рассмотрим теперь задачу оптимизации, в которую входят ограничения в форме неравенств фДЛГ)>0; у = 1,2, т. Прямые ограничения.

X > 0 можно рассматривать как частный случай фДЛ") > 0.

Пусть X* - оптимальная точка. Если оптимум находится не внутри допустимого множества, задаваемого ограничениями, а на границе, то ограничения могут быть разбиты на две группы: те, которые в оптимальной точке выполняются в виде строгих равенств такие ограничения называют активными, и те, которые в оптимальной точке выполняются в форме неравенств срдЛ' J>0, так называемые неактивные. В теории нелинейного программирования известна теорема Куна и Такера, которая обобщает метод множителей Лагранжа на ограничения, задаваемые в форме неравенств. Теорема устанавливает, что в точке X*:

• 1) Xj >0, т. е. множители X могут быть только положительными или нулевыми;
• 2) для всех неактивных ограничений Xj=0, для активных >0, и т. к. для активных ограничений ц>- fX*) = 0, то

3) вектор-градиент целевой функции может быть представлен как линейная комбинация вектор-градиентов целевой функции и активных ограничений в точке X*:

Теорема Куна и Такера дает необходимые, а при некоторых специальных предположениях и достаточные условия оптимума, позволяющие определить точку X .

Остановимся теперь кратко на методах вычисления оптимального значения X*. Существует несколько возможностей.

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

Остановимся на некоторых из них.

Говорят, что функция Лагранжа имеет седловую точку X, X, если для нее выполняется соотношение

Поиск седловой точки опирается на результаты, вытекающие из условий Куна-Такера, и в некоторых случаях является весьма эффективным.

Рис. 1.18. Характер движения изображающей точки вдоль поверхности-ограничения

При градиентном методе поиска с возвратом внутри допустимой области оптимум ищется с применением любого локального метода поиска. Поиск продолжается до тех пор, пока не будут нарушены некоторые ограничения. Как только произойдет нарушение одного или нескольких ограничений, изображающая точка (рис. 1.18) начнет двигаться по направлению градиента функции Н (Х)_У определяемой соотношением:

Закон движения определяется следующим выражением:

Следует отметить, что на границе области угол между векторами grad / и grad Я близок к 180°. Поэтому, если изображающая точка выходит на ограничение, то далее она движется вдоль границы зигзагообразно, что, естественно, замедляет скорость поиска.

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

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

Эта функция должна обладать следующими свойствами:

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

В качестве такой новой функции обычно применяют выражение:

•5 u'(y vr 4vl 4 v при.

<0;

Здесь H (Л>Цф,(*)] и cp,(X =.

=i ^J [0 при ср,(Л')>().

Константа к — достаточно большое положительное число, выбираемое таким образом, чтобы условие.

выполнялось всюду за пределами допустимой области.

Применение метода штрафных функций удобно тем, что он позволяет пользоваться результатами классического анализа. Недостаток метода — трудность получения точного решения; поэтому его целесообразно использовать в сочетании с другими методами.