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

Рассмотрим -мерную задачу нелинейного программирования

(1)

где

(2)

-не пустое, ограниченное замкнутое множество.

Нам понадобятся далее понятия множителей Лагранжа и функции Лагранжа. Функция Лагранжа для задачи (1) с ограничениями (2) определяется формулой

(3)

где - -вектор множителей Лагранжа.

Нам понадобится также понятие условия регулярности ограничивающих функций. Если точка , то условие линейной независимости векторов называется условием регулярности задачи (1), (2) в точке . Данное условие означает, в частности, что количествоограничивающих функций

Рис. 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 не требует знакоопределенности (т.е. положительности или отрицательности) множителей Лагранжа . Теорема требуется лишь того, чтобы не все из этих множителей равнялись нулю одновременно.

Поиск по сайту: