С каждой задачей нелинейного программирования связывается так называемая функция Лагранжа
L () (5.9)
рассматриваемая на множестве пар векторов =(х 1, х 2,…, х n) и =(l 1, l 2, …lm).
Здесь i - множители Лагранжа.
Классическая задача оптимизации состоит в нахождении min (max) целевой функции f (), где – точка в пространстве R (n) при наличии ограничений типа равенств:
gi ()=0 (5.10)
В этом случае задача на условный max (min) целевой функции f () при наличии ограничений типа равенств сводится к задаче определения стационарных точек функции Лагранжа L ().
(5.11)
Решая систему (5.11), состоящую из n + m уравнений, определяем стационарную точку в которой может достигаться условный экстремум.
В задачах НЛП имеют место ограничения более общего вида:
(5.12)
Cформируем необходимые условия того, что в точке достигается оптимальное решение задачи НЛП, например минимизируется функция f () при ограничениях (5.12). Рассмотрим случай, когда i = , то есть gi ()=0. Пусть – точка, соответствующая оптимальному решению. Она может быть или внутренней, или граничной, то есть каждая из ее компонентов xj будет удовлетворять условию xj >0, либо условию xj =0.
Если хj находится внутри области, то отклонение от точки х возможны как в сторону увеличения, так и в сторону уменьшения хj. Но поскольку х – оптимальная точка, то должно быть
.
Если хj лежит на границе допустимой области (хj =0), то отклонение от оптимальной точки возможны только в сторону увеличения хj , при этом f () должна увеличиваться, так что
.
Таким образом, для этого случая необходимые условия примут вид:
(5.13)
Рассмотрим случай gi () 0, . Заменим ограничения типа неравенства на ограничения типа равенства путем введения дополнительных неотрицательных переменных ui. При этом ограничения
(5.14)
Причем
(5.15)
Функция Лагранжа для этого случая будет иметь вид:
(5.16)
Условия, которым должны удовлетворять значения ui, xi, li в точке оптимального решения будут выражаться соотношениями (5.13) применительно к функции Лагранжа (5.16)
(5.17)
(5.18)
(5.19)
Условие (5.19) получено с учетом соотношения (5.15).
Соотношение (5.17) вводит ограничения на множители Лагранжа li. Из него следует, что в функцию L () (5.16) ограничения типа равенств исходить не будут, так как для них li= 0, а ограничения типа равенств, соответствующие ui= 0 будут входить с li> 0. Поэтому функция Лагранжа фактически совпадает с функцией Лагранжа , определяемой соотношением (5.19).
Принимая во внимание соотношение (5.17) запишем соотношение (5.19) в виде:
(5.20)
Условия (5.18) и (5.20) называют условием Куна-Таккера. Условие Куна-Таккера можно записать в ином виде:
(5.21)
Рассмотрим случай gi ()³0, i = . Ограничения типа равенств будут иметь вид
gi ()- ui = 0 (5.22)
Причем
(5.23)
Функция Лагранжа для этого случая будет иметь вид:
(5.24)
Условия, которым должны удовлетворять ui, xi, li в стационарной точке применительно к функции Лагранжа (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)
где ui 0 – дополнительные переменные.
Другая интерпретация условия Куна-Таккера связана с понятием седловой точки функции Лагранжа L ().
Определение 5.9. Седловой точкой функции L () называют такую точку в которой функция L () достигает минимума по и максимума по для задачи минимизации, и максимума по , но минимума по для задачи максимизации, то есть точку ( 0,, 0), удовлетворяющую условиям:
(5.32)
(5.33)
Когда целевая функция f( ) и ограничения gi( ) являются функциями одной переменной, условия (5.32) и (5.33) могут быть проиллюстрированы графически (рис. 5.4.).
L
Седловая точка
λ o,(x 0)
x 0, (l 0)
x, (l) λ> 0, x> 0,
Рис. 5.4. Функция Лагранжа в окрестности седловой точки.
Таким образом, с каждой задачей нелинейного выпуклого программирования связывается функция Лагранжа L(), рассматриваемая на множестве пар векторов , . Нетрудно доказать следующее утверждение (теорема Куна-Таккера).
Теорема 5.7. Если пара векторов и 0 является седловой точкой для функции Лагранжа, -оптимальный вектор в соответствующей задаче нелинейного программирования.
Если необходимые и достаточные условия Куна-Таккера выполняются, то могут быть найдены эффективные вычислительные методы решения задач НЛП, например, задачи квадратичного программирования.