Нелинейное программирование

Тема 6

Нелинейное программирование

План

1.  Постановка задачи

2.  Метод множителей Лагранжа

3.  Теорема Куна-Таккера. Условие регулярности Слейтера

4.  Выпуклое и вогнутое программирование

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

6.1 Постановка задачи

Задача нелинейного программирования в общем случае формулируется следующим образом:

найти max(min){f(x1, x2, ..., xn)}

при условиях

где функции f(x1, x2, ..., xn), gi(x1, x2, ..., xn) – нелинейные функции переменных x1, x2, ..., xn (i = 1, 2, ..., m).

Задача нелинейного программирования называется также задачей на условный экстремум.

В отличие от задач линейного программирования для задач нелинейного программирования не существует универсального метода решения.

В задачах линейного программирования область допустимых решений R(x) всегда является выпуклым с конечным числом крайних точек. Перебрав только крайние точки, всегда за конечное число шагов можно найти оптимальное решение. В задачах нелинейного программирования нелинейность ограничений не всегда обеспечивает выпуклость области допустимых решений и конечность числа его крайних точек. Из-за этих особенностей и возникают основные трудности решения задач нелинейного программирования.

Пример 1. Область допустимых решений R(x) определена ограничениями:

Область допустимых решений имеет вид (Рисунок 6.1) и является не выпуклой.

Пример 2. Область допустимых решений R(x) определена ограничениями:

Область допустимых решений имеет вид (Рисунок 6.2), является выпуклой, но имеет бесконечное число крайних точек.

6.2 Метод множителей Лагранжа

Метод позволяет найти максимум (минимум) функции f(x1, x2, ..., xn) при ограничениях-равенствах. Основная идея метода заключается в переходе от задачи на условный экстремум к задаче нахождения безусловного экстремума специально построенной функции Лагранжа.

Пусть требуется найти min {f(x1, x2, ..., xn)} при ограничениях

Предположим, что функции f, g1, g2, ..., gm дифференцируемы. Введем набор переменных l1, l2, ..., lm по числу ограничений, которые называются множителями Лагранжа. Составим функцию Лагранжа следующего вида

Для того, чтобы вектор был решением задачи, необходимо существование такого вектора , что пара векторов удовлетворяет системе уравнений

Таким образом, метод множителей Лагранжа состоит из следующих шагов:

1.  Составляем функцию Лагранжа L(X, L).

2.  Составляем систему уравнений.

3.  Находим ее решение и исследуем функцию f(X) в окрестностях точки Х0 на min(max).

6.2.1 Исследование функции на экстремум

Для того, чтобы стационарная точка Х0 была экстремальной, достаточно чтобы матрица Гессе H в точке Х0 была:

Ø  положительно определенной, тогда Х0 – точка min;

Ø  отрицательно определенной, тогда Х0 – точка max.

Для двумерной функции f(x1, x2) матрица Гессе имеет вид

Для трехмерной функции f(x1, x2, x3) матрица Гессе имеет вид

Квадратичная форма Q(X) является отрицательно определенной, если значения k-х угловых миноров определителя ½А½отличны от нуля и имеют знак (–1)k (k=1, 2, ..., n). В этом случае матрица А называется отрицательно определенной.

Квадратичная форма Q(X) является положительно определенной, если значения всех угловых миноров определителя ½А½ положительны. В этом случае матрица А называется положительно определенной.

k-м угловым минором определителя матрицы A(n´n) называется определитель вида

Пример. Пусть точка является точкой экстремума функции f(x1, x2, x3) = x1 + 2x3 + x2x3 – . Определить характер экстремума?

Пусть матрица Гессе имеет вид

.

Определим k-е угловые миноры:

Так как матрица Гессе является отрицательно определенной, то точка является точкой максимума.

6.3 Теорема Куна-Таккера. Условие регулярности Слейтера

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

Теорема. Пусть f(X), gi(X) (i=1, 2, ..., m) имеют непрерывные частные производные на некотором открытом множестве Ân, содержащем Х0. Если Х0 является точкой минимума функции f(X) при ограничениях , удовлетворяющих условию регулярности в виде линейной независимости векторов , то существует такие неотрицательные множители Лагранжа , , ..., , что

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

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

Условие регулярности – это дополнительные предположения о природе функций gi(X) для существования оптимального вектора X0. В частном случае, когда f(X) и все gi(X) являются выпуклыми функциями, условие регулярности имеет следующий вид: существует такой вектор Х, что для всех i=1, 2, ..., m. Это условие называется условием регулярности Слейтера.

6.4 Выпуклое и вогнутое программирование

Частным случаем задачи нелинейного программирования является задача выпуклого программирования, которая формулируется следующим образом: найти min{f(X)} при условиях

где все функции f(X) и gi(X) выпуклы по X={x1, x2, ..., xn}.

Применив теорему Куна-Таккера, получим следующие необходимые и достаточные условия оптимальности: если функции f(X), gi(X) дифференцируемы и выпуклы по Х, то вектор Х0 является оптимальным решением задачи выпуклого программирования тогда и только тогда, когда существует такой вектор , что для пари векторов будут выполняться следующие условия:

Задачу выпуклого программирования решают следующим образом:

1.  Составляют функцию Лагранжа

2.  Записывают условие оптимальности в виде системы уравнений и неравенств.

3.  Находят совместное решение .

Задача вогнутого программирования формулируется следующим образом: найти max{f(X)} при условиях

где все функции f(X) и gi(X) вогнуты по X={x1, x2, ..., xn}.

Покажем эквивалентность данной задачи задаче выпуклого программирования. Введем обозначения f*(X) = – f(X) и g*i(X) = – gi(X). Так как max{ f(X)} = min{– f(X)}, то приходим к задаче:

найти min{f*(X)} при условиях

где все функции f*(X) и g*i(X) выпуклы по X={x1, x2, ..., xn}, поэтому это задача выпуклого программирования.

Условия оптимальности формулируются аналогично задаче выпуклого программирования: Пусть функции f(X), gi(X) дифференцируемы и вогнуты по Х. Для того, чтобы вектор Х0 являлся оптимальным решением задачи вогнутого программирования необходимо существование такого вектора , что для пари векторов будут выполняться следующие условия:

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

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

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

Эта задача формулируется следующим образом:

найти max(min){ f(X)}= BтX + XтCX = при условиях

где – симметричная матрица.

Матрица С будет отрицательно определенной в задаче максимизации и положительно определенной в задаче минимизации. Это означает, что функция f(X) является выпуклой по переменным Х в задаче минимизации и вогнутой в задаче максимизации. Ограничения в этой задаче предполагаются линейными, что гарантирует выпуклость области допустимых решений.

Применив теорему Куна-Таккера, получим следующие необходимые и достаточные условия оптимальности: вектор является оптимальным решением задачи квадратичного программирования тогда и только тогда, когда существуют такие m-мерные векторы , и n-мерный вектор , что

Первые два условия образуют систему из (n + m) линейных уравнений с 2(n + m) неизвестными (векторы X0, L0, V0, W0). Третье и четвертое – это условие дополняющей нежесткости, которые налагают дополнительные ограничения на переменные X0, L0, V0, W0, а именно:

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