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

Метод проектирования вектора-градиента для ограничений-равенств также предполагает замену этих ограничений условием попадания в заданный “коридор”. Однако движение к точке оптимума осуществляется по касательной к поверхности ограничений в текущей точке.  Для определения конкретного направления поиска в касательной плоскости (в двумерном случае касательная плоскость представляет собой прямую линию) на нее проектируют градиент критерия оптимальности. В направлении проекции градиента осуществляется движение до тех пор, пока не будет достигнута граница допустимого “коридора” или не найдена точка экстремума по направлению. Из достигнутой точки осуществляется возврат на ограничение по нормали к нему. Далее процедура повторяется.

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

Рис. 4.16

З а м е ч а н и е 4.29. В случае, если начальная точка  X⁰  выбрана не на поверхности ограничений, то предварительно осуществляется ее спуск на ограничение по направлению нормали к нему.

Достоинством последнего метода является большая скорость движения к условному оптимуму, чем у предыдущего метода, а недостатком – большой объем вычислений.

Более подробное описание рассмотренных методов приводится в [    ]

З а м е ч а н и е  4.30.  Приведенные методы условной оптимизации при ограничениях типа равенств не исчерпывают всего перечня таких методов и их разновидностей. Другие методы такого рода рассмотрены в [  ]

4 3.3.  Методы оптимизации при ограничениях  типа неравенств

4.3.3.1. Общие вопросы оптимизации при ограничениях типа неравенств

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

z(X) ® min 

g_i (X) £ 0,                                                                   (4.46)

i=1,…, m.                                           

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

Отличительной особенностью задач НП с ограничениями типа неравенств является то, что если оптимум ЦФ находится внутри допустимой области (внутри ОДП), то иногда задачу можно решить любым методом поиска без ограничений. Однако такие случаи на практике встречаются редко. Оптимум обычно оказывается на границе области. В связи с этим приходится применять специальные методы оптимизации.

4.3.3.2. Аналитические методы решения задач оптимизации при ограничениях типа неравенств

Метод множителей Лагранжа может быть обобщен на случай функциональных ограничений, имеющих вид неравенств. Основой такого обобщенного метода является теорема Куна-Таккера [5]. Смысл этой теоремы состоит в следующем. Если точка X^*  является точкой минимума  задачи (4.46), то существуют такие неотрицательные множители (называемые множителями Лагранжа) l₁ , l₂ , …, l_m , что выполняются два условия (называемые условиями Куна-Таккера), связывающие эти множители со значениями градиентов функций z(X) и g_i(X) в этой точке.

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

Достаточность теоремы Куна-Таккера имеет место только для задачи выпуклого программирования (т.е. для задачи, в которой функций z(X) и g_i(X) выпуклы). Такая задача обычно записывается в следующем виде, учитывающем также и условие неотрицательности:        

min z(X);