- •Одномерная задача оптимизации
- •Многомерная задача безусловной оптимизации
- •Задача выпуклого программирования
- •Задача нелинейного программирования с ограничениями типа равенств
- •Теорема Куна-Таккера для задачи нелинейного программирования с ограничениями типа неравенств
- •Теорема Куна-Таккера для общей задачи нелинейного программирования
- •Аналитическое решение многомерных задач нелинейного программирования
Задача нелинейного программирования с ограничениями типа равенств
Рассмотрим -мерную задачу нелинейного программирования
(1) |
где
(2) |
-не пустое, ограниченное замкнутое множество.
Нам понадобятся далее понятия множителей Лагранжа и функции Лагранжа. Функция Лагранжа для задачи (1) с ограничениями (2) определяется формулой
(3) |
где - -вектор множителей Лагранжа.
Нам понадобится также понятие условия регулярности ограничивающих функций. Если точка , то условие линейной независимости векторов называется условием регулярности задачи (1), (2) в точке . Данное условие означает, в частности, что количествоограничивающих функций, проходящих через точку , не может быть больше размерности вектора варьируемых параметров, т.е. должно быть выполнено неравенство . Например, на рис. 1 в ситуации (а) количество ограничивающих функций, проходящих через точку , превышает размерность вектора варьируемых параметров, в ситуации (б) в точке градиенты (), () ограничивающих функций коллениарны.
Рис. 1. Ситуации, в которых в двумерном случае (n=2) не выполняется условие регулярности системы функций h(X) в точке X*.
Исключительно важное место в теории и практике решения задач нелинейного программирования с ограничениями типа равенств занимает следующая теорема (правило Лагранжа для задачи оптимизации с ограничениями типа равенств).
Теорема 1. Пусть функция и функции имеют непрерывные частные производные в некоторой окрестности точки и пусть эта точка является точкой локального минимума функции при условии . Пусть, кроме того, выполняется условие регулярности системы функций в точке . Тогда существуют такие множители Лагранжа ,[1,], не все из которых равные нулю одновременно, что для функции Лагранжа точка является стационарной точкой функции, т.е.
(4) |
Доказательство теоремы приведем для одного частного случая. Пусть =3, т.е. минимизируемая функция , и пусть заданы два ограничения типа равенств
(5) |
Ограничения (5) определяют область допустимых значений , которая представляет собой некоторую кривую в пространстве , являющуюся результатом пересечения поверхностей , . Допустим, что функция () имеет точку локального минимума в области . Допустим также, что выполнены условия теоремы 1, т.е. функции (), имеют непрерывные частные производные в некоторой окрестности точки и градиенты функций в этой точке линейно независимы. Положим, кроме того, что из равенств (5) переменные , можно выразить через переменную в виде
(6) |
Подставив выражения (6) в выражение для функции (), преобразуем исходную задачу к следующей задаче оптимизации без ограничений, которая содержит только одну переменную :
(7) |
Поскольку функция () имеет точку минимума , производная по функции в точке равна нулю:
(8) |
Дифференцируя по выражения (5), получим
(9) |
Запишем уравнения (8), (9) в виде матричного уравнения
(10) |
Поскольку вектор не нулевой, то равенство (10) возможно лишь в том случае, когда . Но это возможно лишь в том случае, когда вектора-строки матрицы линейно зависимы. Значит, существуют такие скаляры , не все равные нулю, что
(11) |
В выражении (11) скаляр a не может быть равен нулю, поскольку противное означало бы линейную зависимость векторов , что противоречит условию теоремы. Поэтому после деления на из (11) получим
Таким образом, для рассматриваемого частного случая справедливость теоремы доказана
Отметим, что теорема 1 не требует знакоопределенности (т.е. положительности или отрицательности) множителей Лагранжа . Теорема требуется лишь того, чтобы не все из этих множителей равнялись нулю одновременно.
Пример 1
Рассмотрим в качестве минимизируемой функции () функцию Розенброка (=2). Положим, что имеется только одно ограничение типа равенств, которое задается с помощью функции ()=++0.2=0. Легко видеть, что градиенты функций (), () равны, соответственно
Задачу иллюстрирует рис. 2, линии уровня функции Розенброка на котором получены с помощью следующей MATLAB-программы:
x=-2:0.06:0;
y=x;
[X,Y]=meshgrid(x);
Z=100.*(Y-X.^2).^2+(1-X).^2;
V=[2,8,32,125,250,500,1000,2000];
contour(X,Y,Z,V);
[C,h]=contour(X,Y,Z,V);
clabel(C,h);
В точках , векторы градиента функций , () не коллениарны. Поэтому для этих точек не существует не равный нулю множитель Лагранжа , при котором функция Лагранжа равна нулю: . И поэтому точки , не могут быть точками локального минимума для рассматриваемой задачи. Наоборот, в точке векторы градиента функций , коллениарны и поэтому существует не равный нулю множитель , при котором справедливо равенство Отметим, что, например в точке , градиент функции Розенброка равен
Рис. 2. K прим. 1.
Теорема 1 означает, что в ее условиях вместо задачи условной оптимизации (1), (2) можно решать задачу безусловной оптимизации
Необходимым условием существования локального минимума этой задачи в некоторой точке является условие (см. Теорему 2.1).
Широко известна другая форма теоремы 1, которую мы сформулируем в виде следствия этой теоремы.
Следствие. В условиях теоремы 1 существуют такие множители Лагранжа , не все из которых равные нулю одновременно, что имеют место следующие равенства:
(12) |
(13) |
Здесь равенство (12) повторяет равенство (4), а справедливость равенства (13) следует из того факта, что по условиям теоремы точка удовлетворяет всем ограничениям, т.е. .
Заметим, что из (13) следует справедливость еще одного полезного равенства