Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Условие регулярности Слейтера

Утверждение, обратное теореме (2.3), т. е. необходимое условие экстремума в ЗНП, оказывается верным только при выполнении дополнительных условий, которым должна удовлетворять задача (2.28). Важнейшим из них является так называемое условие регулярности Слейтера:

F Говорят, что функция gi (х), задающая ограничение в задаче (2.28), удовлетворяет условию регулярности Слейтера, если существует такая точка , принадлежащая области допустимых планов D, что

т. е. является внутренней точкой относительно ограничения gi(x). Поэтому данное условие также называют условием телесности.

Вообще говоря, существуют разные варианты необходимого условия Куна—Таккера. Приведем один из них.

Теорема 2.4. (Необходимое условие наличия экстремума).

Если (D, f) является задачей выпуклого программирования с решением х, ее целевая функция f(x) и функции ограничений gi(x) — дифференцируемы, нелинейные ограничения в форме неравенств удовлетворяют условию регулярности Слейтера, то существует такой вектор и0, что (х,и) — седловая точка функции Лагранжа Ф(х,и).

Мы не будем здесь приводить доказательство теоремы (2.4), которое является довольно сложным. Заинтересованный читатель может найти его в таких источниках, как [1, 13].

Значение теоремы Куна—Таккера состоит в том, что она позволяет связать процесс решения оптимизационной задачи с поиском седловых точек функции Лагранжа, т. е., грубо говоря, с максимизацией этой функции по х и минимизацией по и.

Определим F(x) как функцию, ставящую в соответствие каждому значению х минимальное значение функции Ф(х,и) по и:

и по аналогии

Рассмотрим задачу отыскания максимума функции F(x)

и задачу минимизации G(u)

Очевидно, что

Отсюда следует, что максимум F(x) находится в допустимой области D и совпадает с максимумом целевой функции f(x) задачи (2.28):

Таким образом, задача (2.34), в определенном смысле, равносильна (2.28). Аналогичные выводы могут быть получены и для (2.35). Задачи (2.34) и (2.35) образуют двойственную пару. Как нетрудно догадаться, данное отношение является обобщением отношения двойственности для задач линейного программирования. Соответственно, при определенных условиях пара двойственных задач нелинейного программирования обладает свойствами, аналогичными свойствам двойственных линейных задач. В частности, при любых хХ, и≥0

Условие (2.36) находит широкое применение при построении оценок в итеративных методах решения оптимизационных задач. Например, если имеется возможность приблизительно решить прямую и двойственную задачи и получить последовательности приближений {х(q)} и {и(q)}, то с помощью неравенств вида

можно определить момент остановки вычислительной процедуры.

В заключение отметим, что возможен вариант вывода выражений для целевых функций и ограничений пары двойственных задач линейного программирования из общего определения отношения двойственности для нелинейных задач. Также отметим, что в процессе формирования нелинейных двойственных задач существует большая неоднозначность: их вид можно варьировать, включая в множество Х часть ограничений gi(x)≤0.