С каждой задачей нелинейного программирования связывается так называемая функция Лагранжа
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 является седловой точкой для функции Лагранжа,
-оптимальный вектор в соответствующей задаче нелинейного программирования.
Если необходимые и достаточные условия Куна-Таккера выполняются, то могут быть найдены эффективные вычислительные методы решения задач НЛП, например, задачи квадратичного программирования.
