Методы условной оптимизации

1.0. Задача нелинейного программирования. Метод неопределенных множителей Лагранжа

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

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

Итак, в этом случае определяется функция Лагранжа

(1)

где , , - неотрицательные и не зависящие от весовые коэффициенты, которые можно отождествить с множителями Лагранжа.

В дальнейшем понадобится понятие выпуклой функции. Приведем соответствующее определение и некоторые свойства этой функции.

Определение. Функция называется выпуклой в области , если для любых двух векторов , выполняется неравенство

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

Выпуклая функция не может принимать значения, большего, чем значения функции, полученной линейной интерполяцией между и . Если имеет место обратное неравенство, то функция называется вогнутой. Функция вогнутая (строго вогнутая), если (- ) выпуклая (строго выпуклая). Дифференцируемая выпуклая функция обладает следующими свойствами:

1) - () для всех , где = ;

2) матрица вторых частных производных по (матрица Гессе) положительно определенная (или положительно полуопределенная) для всех , если строго выпуклая (выпуклая);

3) в области функция имеет только один экстремум.

Критерий Сильвестра (проверка выпуклости): функция является строго выпуклой (выпуклой) в точке , если матрица Гессе положительно определенная (или положительно полуопределенная) в этой точке.

Матрица Гессе является положительно определенной (или положительно полуопределенной) в точке , если её определитель положителен (неотрицателен) в этой точке.

Множество точек (или область) называется выпуклым в - мерном пространстве, если для всех пар точек (, ), принадлежащих этому множеству, отрезок прямой линии, соединяющей их, также полностью принадлежит множеству. Каждая точка , определяемая выражением = +(1- , , также принадлежит множеству. Группа ограничений , определяет выпуклую область, если все выпуклы.

В [ ] доказана следующая теорема.

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

= 0, ,

= 2 = 0, ,

где определяется формулой (1) п. 1.0.

Здесь можно выделить частный случай теоремы, когда отсутствуют ограничения в виде неравенств, в виде отдельной теоремы.

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

= 0, ,