Методы оптимизации функций многих переменных (стр. 4 из 6)

При выполнении условия регулярности λ₀≠0 и можно положить этот коэффициент равным 1.

Теорема Куна - Таккера (дифференциальная форма необходимого условия минимума). Пусть точка х* - точка локального минимума в задаче математического программирования (6), функцииf,g_r+1,…,g_m дважды непрерывно дифференцируемы в точке х, функции g₁,…,g_r дважды непрерывно дифференцируемы в некоторой окрестности точки x. Тогда существует число

и вектор такие, что выполняются следующие условия:

условие стационарности обобщенной функции Лагранжа по х:

grad_xL (x*,

, ) =0;

условие нетривиальности:

²+ ²>0,т.е. хотя бы один из множителей Лагранжа отличен от нуля;

условие неотрицательности:

≥0, ≥0, i=1, …, r,

т.е. множители Лагранжа, соответствующие целевой функции и ограничениям - неравенствам, неотрицательны;

условия дополняющей нежесткости:

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.

Условие (12) минимума функции Лагранжа по х эквивалентно выполнению в точке (х*, λ*) неравенства

≥0. (12′)

Условие (13) максимума функции Лагранжа по λ эквивалентно выполнению в точке (х*, λ*) неравенства

≤0. (13′)

Утверждение 2. х* - оптимальное решение задачи (3) в том и только в том случае, когда существует такой вектор λ* ≥0, что (х*, λ*) - седловая точка функции Лагранжа L (x,λ).

1.3 Решение задач квадратичного программирования методом седловой точки

Рассмотрим задачу квадратичного программирования, т.е.

f (x) = (Сx,x) + (d,x)

min, (15), g (x) =Ax ≤ b,

где С - матрица размера n*n; d, х - векторы-столбцы n*1; А - матрица размера m*n; b - вектор-столбец m*1. Для задачи квадратичного программирования критерий существования седловой точки приобретает вид задачи решения СЛАУ. Действительно, функция Лагранжа в этом случае запишется в виде

L=

d_kx_k+ c_kjx_kx_j+ λ_i ( a_ijx_j-b_i), (16)

где c_kj- элементы матрицы С; d_k- элементы вектора d; b_i- элементы вектора свободных членов b; a_ij- элементы матрицы А; λ_i- коэффициенты Лагранжа. Необходимые и достаточные условия оптимальности решения х* принимают вид

v_j

d_j+2 c_kjx_k+ λ_ia_ij, v_j≥0, (j=1,…,n), (17)

y_i

a_ijx_j-b_{i, -} y_i≤0, (i=1,...,m), (18)

x_jv_j=0, x_j≥0, (j=1,...,n), (19)

λ_i (-y_i) =0, λ_i≥0. (20)

Равенства (17), (18) образуют систему n+m линейных уравнений с 2 (n+m) неизвестными x_1,…,x_n,v₁,…,v_n, λ₁,…, λ_m,y_1,…,y_m. Решения этой системы, при которых выполняются равенства (19), (20), дают координаты седловой точки (х*,λ*). Соответственно n координат х* дают оптимальное решение задачи (15).

2. Порядок выполнения лабораторной работы

Построить допустимую область задачи и линии уровня.

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