Функция Лагранжа. Условия Куна – Таккера

С каждой задачей нелинейного программирования связывается так называемая функция Лагранжа

L( ) (5.9)

рассматриваемая на множестве пар векторов =(х₁, х₂,…, х_n) и =(l₁, l₂, …l_m).

Здесь _i - множители Лагранжа.

 

Классическая задача оптимизации состоит в нахождении min (max) целевой функции f( ), где – точка в пространстве R⁽ⁿ⁾ при наличии ограничений типа равенств:

g_i( )=0 (5.10)

В этом случае задача на условный max (min) целевой функции f( ) при наличии ограничений типа равенств сводится к задаче определения стационарных точек функции Лагранжа L( ).

(5.11)

Решая систему (5.11), состоящую из n+m уравнений, определяем стационарную точку в которой может достигаться условный экстремум.

В задачах НЛП имеют место ограничения более общего вида:

(5.12)

 

Cформируем необходимые условия того, что в точке достигается оптимальное решение задачи НЛП, например минимизируется функция f( ) при ограничениях (5.12). Рассмотрим случай, когда i= , то есть g_i( )=0. Пусть – точка, соответствующая оптимальному решению. Она может быть или внутренней, или граничной, то есть каждая из ее компонентов x_j будет удовлетворять условию x_j>0, либо условию x_j=0.

Если х_j находится внутри области, то отклонение от точки х возможны как в сторону увеличения, так и в сторону уменьшения х_j. Но поскольку х – оптимальная точка, то должно быть

.

Если х_j лежит на границе допустимой области (х_j=0), то отклонение от оптимальной точки возможны только в сторону увеличения х_j, при этом f( ) должна увеличиваться, так что

.

 

Таким образом, для этого случая необходимые условия примут вид:

(5.13)

Рассмотрим случай g_i( ) 0, . Заменим ограничения типа неравенства на ограничения типа равенства путем введения дополнительных неотрицательных переменных u_i. При этом ограничения

 

(5.14)

Причем

(5.15)

Функция Лагранжа для этого случая будет иметь вид:

(5.16)

Условия, которым должны удовлетворять значения u_i, x_i, l_i в точке оптимального решения будут выражаться соотношениями (5.13) применительно к функции Лагранжа (5.16)

(5.17)

(5.18)

(5.19)

Условие (5.19) получено с учетом соотношения (5.15).

Соотношение (5.17) вводит ограничения на множители Лагранжа l_i. Из него следует, что в функцию L( ) (5.16) ограничения типа равенств исходить не будут, так как для них l_i=0, а ограничения типа равенств, соответствующие u_i=0 будут входить с l_i>0. Поэтому функция Лагранжа фактически совпадает с функцией Лагранжа , определяемой соотношением (5.19).

Принимая во внимание соотношение (5.17) запишем соотношение (5.19) в виде:

(5.20)

Условия (5.18) и (5.20) называют условием Куна-Таккера. Условие Куна-Таккера можно записать в ином виде:

(5.21)

Рассмотрим случай g_i( )³0, i= . Ограничения типа равенств будут иметь вид

g_i( )-u_i =0 (5.22)

Причем

(5.23)

Функция Лагранжа для этого случая будет иметь вид:

(5.24)

Условия, которым должны удовлетворять u_i, x_i, l_i в стационарной точке применительно к функции Лагранжа (5.24) будут:

(5.25)

(5.26)

(5.27)

Учитывая ограничения (5.25) на множители Лагранжа условия Куна-Таккера запишем в виде:

(5.28)

(5.29)

Или в ином виде:

(5.30)

Аналогично могут быть получены необходимые условия и для случая максимизации целевой функции f( ).

Необходимые условия Куна-Таккера являются также достаточными, если целевая функция и область допустимых решений обладают определенными свойствами, связанными с выпуклостью и вогнутостью (табл. 5.1.)

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

Таблица 5.1.

Тип оптимизации	Требуемые свойства
Целевая функция	Область допустимых решений
Максимизация	Выпуклая	Выпуклое множество
Минимизация	Вогнутая	Выпуклое множество

 

Для метода Лагранжа условия Куна-Таккера сведены в табл.5.2.

Таблица 5.2.

Тип оптими-зации	Тип ограничений	Требования
gi(x)	f(x)	xj	li			xj
max	gi(x)=0, i=1,r	Ли-ней-ная	Вы-пук-лая	³0	Нет огра-нич.	£0	=0	=0	=0
gi(x)<0, i=r+1,k	Вог-ну-тая	£0	£0	£0
gi(x)>0, i=k+1,m	Вы-пук-лая	³0	£0	³0
min	gi(x)=0, i=1,r	Ли-ней-ная	Во-гну-тая	³0	Нет огра-нич.	³0	=0	=0	=0
gi(x)£0, i=r+1,k	Вогнутая	³0	³0	£0
gi(x)³0, i=k+1,m	Вы-пук-лая	£0	³0	³0

В таблице 5.2 L – функция Лагранжа общего вида

(5.31)

где u_i 0 – дополнительные переменные.

Другая интерпретация условия Куна-Таккера связана с понятием седловой точки функции Лагранжа L( ).

Определение 5.9. Седловой точкой функции L( ) называют такую точку в которой функция L( ) достигает минимума по и максимума по для задачи минимизации, и максимума по , но минимума по для задачи максимизации, то есть точку ( _0,, ₀), удовлетворяющую условиям:

(5.32)

(5.33)

Когда целевая функция f( ) и ограничения g_i( ) являются функциями одной переменной, условия (5.32) и (5.33) могут быть проиллюстрированы графически (рис. 5.4.).

L

Седловая точка

 

 

λ_o,(x₀)

x₀, (l₀)

x,(l) λ>0,x>0,

Рис. 5.4. Функция Лагранжа в окрестности седловой точки.

 

Таким образом, с каждой задачей нелинейного выпуклого программирования связывается функция Лагранжа L( ), рассматриваемая на множестве пар векторов , . Нетрудно доказать следующее утверждение (теорема Куна-Таккера).

Теорема 5.7. Если пара векторов и ₀ является седловой точкой для функции Лагранжа, -оптимальный вектор в соответствующей задаче нелинейного программирования.

Если необходимые и достаточные условия Куна-Таккера выполняются, то могут быть найдены эффективные вычислительные методы решения задач НЛП, например, задачи квадратичного программирования.