Методы первого порядка. Задачи и методы условной оптимизации нелинейного программирования, страница 13

Методы второй группы включают метод прямого поиска с возвратом, метод проектирования вектора-градиента и методы возможных направлений.  Применение этих методов для ограничений, задаваемых неравенствами, имеют свои особенности:

           Так, в методе  прямого поиска с возвратом “коридор” образуется только внутри допустимой области. Остальные особенности метода остаются без изменений Графическое изображение процесса поиска оптимума (при n=2 и m=1) представлено на рис. 4.21.

Рис. 4.21.

При использовании метода проектирования вектора-градиента поиск в допустимой области поиск ведется без учета ограничений любым из способов безусловной оптимизации [20]. При достижении границы поиск идет по касательной к границе ограничений (или суммы достигнутых ограничений) внутрь недопустимой области на “ширину” коридора e. Затем осуществляется возврат на поверхность ограничения по нормали к границе.

Графическое изображение процесса поиска методом проектирования вектора-градиента (при n=2, m=1) приведено на рис. 4.22.

Рис.4.22

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

Методы возможных направлений включают группу методов, исторически первый из которых был разработан  Зойтендейком. Сущность этих методов состоит в организации пошагового движении в направлениях, называемых возможными. Такие направления обладают следующими свойствами:

-  шаг направлен внутрь и по границе допустимой области (допустимое направление);

-  ЦФ вдоль выбранного направления уменьшается (подходящее направление).

Из допустимого и подходящего направлений формируется некоторое частное направление d^(k) , называемое возможным. Такое направление на каждом шаге определяется в результате решения вспомогательной задачи линейного программирования.

В найденном направлении выполняется шаг определенной длины. Длина такого шага определяется либо из условия “протыкания” ОДР,  либо из условия достижения ЦФ минимума.

Для иллюстрации идеи метода приведем пример решения следующей задачи НП, взятый из [20]:

z(x₁, x₂) = (x -3)² + (x₂ –3)²  ® max

g₁(X) = 2x₁ – x₂² -1 ³ 0

g₂(X) = 9 – 0,8x₁² - 2x₂ ³ 0

Графическая иллюстрация решения этой задачи приведена на рис. 4.23. На рисунке показаны допустимое начальное решение X⁽¹⁾ , векторы направлений d⁽¹⁾, d⁽²⁾, d⁽³⁾, точки X⁽²⁾, X⁽³⁾ , найденные из условия “протыкания” ОДР, точка оптимума X^* .  

Рис. 4.23.

Метод Зойтендейка обладает рядом недостатков, которые устранены в его модификациях [18,20].

При применении методов случайного поиска для решения задач НП с ограничениями типа неравенств нет необходимости предусматривать специальную стратегию поиска при наличии ограничений [26]. Достаточно считать, что если очередной случайный шаг приводит к нарушению ограничений, то этот шаг следует отнести  к категории неудачных и далее руководствоваться обычной стратегией случайного поиска.

З а м е ч а н и е  4.37.  Как и в случае ограничений-равенств  рассмотренные нами методы не исчерпывает всего их перечня. Поэтому  рекомендуется ознакомиться с источниками [       ].

4.3  Некоторые частные виды задач  НП

4.3.1. Квадратичное программирование

В задачах квадратичного программирования ЦФ является квадратичной функцией. Такая функция n переменных в общем случае представляет собой сумму линейной и квадратичной форм

                                                  (4.54)

В последнем выражении предполагается, что коэффициенты d_ij образуют матрицу D, обладающуюопределенными свойствами, обуславливающими выпуклость (или вогнутость) квадратичной функции.