Геометрическая интерпретация задач нелинейного программирования

Классификация методов нелинейного программирования

Для решения задачи нелинейного программирования было предложено много методов, которые можно классифицировать по различным признакам.

По количеству локальных критериев в целевой функции методы нелинейного программирования делятся на:

• однокритериальные,
• многокритериальные.

По длине вектора методы делятся на:

• однопараметрические или одномерные ,
• многопараметрические или многомерные .

По наличию ограничений методы нелинейного программирования делятся на:

• без ограничений (безусловная оптимизация),
• с ограничениями (условная оптимизация).

По типу информации, используемой в алгоритме поиска экстремума методы делятся на:

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

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

2.1. Задача нелинейного программирования при ограничениях – неравенствах

Теорема Куна-Таккера. Рассмотрим случай задачи с ограничениями-неравенствами:

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

В точке минимума неравенства могут выполняться как равенства или строгие неравенства.

Ограничение называется активным в точке , если оно выполняется в ней как строгое равенство, то есть если .

Используя геометрические свойства допустимой области, найдем необходимые условия экстремума для задач минимизации с ограничениями. Для этого сначала рассмотрим случай, когда все линейны. Итак, пусть требуется найти при условии

, . (2.3)

Здесь каждое ограничение (2.3) определяет полупространство в . Допустимая область задана пересечением полупространств, определяемых неравенствами (2.3), и следовательно, является выпуклым многогранником. Вектор является нормалью к гиперплоскости, определяемой уравнением , и направлен внутрь области .

Пусть точка является точкой минимума задачи (2.1) с ограничениями (2.3). Обозначим множество индексов активных ограничений через

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

,

или

для всех и .

Рис. 2.1.

Таким образом, входящий вектор определяет допустимое направление перемещения из точки . Но так как минимальна в точке , то при любом , удовлетворяющем (2.5), будем иметь:

Применим теперь теорему, которая есть следствием леммы Фаркаша. Из условий (2.5), (2.6) на основании леммы Фаркаша следует, что существует множество неотрицательных скаляров , для которых

Если принять, что при (то есть для неактивных ограничений), (2.7) можно переписать в виде

Кроме того, получим, что

поскольку при , а при . Поэтому уравнения ограничений можно включить в целевую функцию следующим образом:

Следовательно, удовлетворяет следующим условиям:

При рассмотрении задачи минимизации при условиях может случиться так, что не будет существовать таких , , для которых без дополнительных предположений о природе функций были бы справедливы уравнения (2.9), (2.10), где - оптимальное решение. Эти дополнительные предположения называют условиями регулярности ограничений. В частности, в рассмотренном случае, в качестве таких условий использовали линейную независимость векторов-градиентов ограничений , .

Теорема Куна-Таккера. Выше найдены условия оптимальности (2.9), (2.10) для задачи НП с линейными ограничениями. Обобщим эти условия на случай задачи (2.1), (2.2), когда все ограничения нелинейны.

Условия оптимальности решения задачи НП формулируются в следующей теореме, имеющей исключительно важное значение в теории нелинейного программирования.

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

Определим функцию Лагранжа следующим образом:

Тогда теорему Куна-Таккера можно записать в виде

Заметим, что множители Лагранжа в задаче НП с ограничениями-равенствами являются знаконеопределенными, тогда как в теореме Куна-Таккера они должны быть положительными.

Задачи нелинейного программирования самого различного физического смысла допускают геометрическую интерпретацию. Рассмотрим такую интерпретацию для наиболее наглядного и простого случая двух переменных, , - плоскость.