Лабораторная работа: Методы оптимизации функций многих переменных

g_i (x *) =0, i =1, 2, …, r .

Если при этом выполнено условие регулярности, то для выпуклых функций f, g_{r +1} ,…, g_m и линейных функций g₁ ,…, g_r условия теоремы Куна - Таккера являются одновременно необходимыми и достаточными условиями глобального минимума.

Достаточное условие минимума первого порядка.

Пусть имеется точка (х* ,), удовлетворяющая условию стационарности обобщенной функции Лагранжа по х при ≠0, суммарное число активных ограничений-неравенств в точке х* и ограничений-равенств совпадает с числом переменных n . Если >0 для всех активных ограничений g_j ( x), то точка х* - точка условного локального минимума в задаче (6).

Достаточное условие минимума второго порядка.

Пусть имеется точка (х* ,), удовлетворяющая условию стационарности обобщенной функции Лагранжа по х при ≠0. Если в этой точке d ² L (х* ,) >0 для всех ненулевых dx таких, что для активных в точке х* ограничений-неравенств dg_j (x* ) =0, >0 и dg_j (x* ) ≤0, =0, то точка х* является точкой локального минимума.

Общая схема решения задачи условной минимизации функции:

Составляется обобщенная функция Лагранжа вида (7).

Выписываются необходимые условия минимума, сформулированные в теореме Куна - Таккера. К этим условиям добавляются ограничения, задающие допустимое множество Х . Полученная система алгебраических уравнений и неравенств используется для поиска условно-стационарных (подозрительных на экстремум) точек. Целесообразно проанализировать отдельно случаи λ₀ =0 и λ₀ =1 (или λ₀ - любое положительное число). Однако если выполнено одно из условий регулярности, то вариант λ₀ =0 рассматривать не надо.

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

Чувствительность решения ЗНП.

Множители Лагранжа могут быть использованы для оценивания влияния малых изменений правых частей ограничений на оптимальное решение задачи нелинейного программирования. Пусть х ^* =х * (b ) - решение ЗНП

f ( x) → min, (8)

x Î X= { x Î Eⁿ : g_i ( x) ≤ b_i , i =1,2,…, m; х ≥0}

при некотором векторе b свободных членов в ограничениях - неравенствах, а v ( b) соответственно значение целевой функции при этом решении ЗНП, т.е. v ( b) = f ( x^* ). Тогда справедлива следующая оценка изменения целевой функции: ∆ v =f (b+∆ b ) - f (b ) при изменении вектора b на некоторый малый вектор-приращение ∆ b :

∆ f ≈ (∆ b, λ* ), (9)

где λ* - вектор множителей Лагранжа, соответствующий решению х^* (b ).

1.2 Седловые точки функции Лагранжа

Существование экстремума тесно связано с наличием у функции Лагранжа (6) так называемой седловой точки.

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

f (x ) → min, (10)

x Î X = {x Î Eⁿ : g_i (x) ≤ 0, i =1,2,…, m ; х ≥0}.

Предполагается, что выполнено условие регулярности, т.е. можно рассматривать только вариант λ₀ =1.

Определение. Точка (х* , λ*), где х* Î Х , ÎЕ ^m , λ*≥0, называется седловой точкой функции Лагранжа L (x ,λ), если

L (x*, λ) ≤ L (x* , λ*) ≤ L (x , λ*). (11)

Утверждение 1 (критерий для седловой точки функции Лагранжа). Точка (х* , λ*) - является седловой для функции Лагранжа L (x ,λ) в том и только в том случае, когда выполнены следующие условия:

L (х* , λ*) =min{L (x , λ*) ׀x Î Х }, (12)

L (х* , λ*) =max{L (x*,λ) ׀λ≥0}, (13)

g_i (x*) = 0, i =1, 2,..., m , (14)

х* ≥0,λ*≥0.