Файл: Теорема КунаТаккера. Рассмотрим основную задачу выпуклого программирования (1).doc
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 08.11.2023
Просмотров: 20
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
§ 1. Теорема Куна-Таккера.
Рассмотрим основную задачу выпуклого программирования:
(1)
,
(2)
, (3)где
и 
- выпуклые функции.В теории нелинейного программирования центральное место занимает теорема Куна-Таккера, которая обобщает метод множителей Лагранжа на случай, когда в З.Н.П., кроме ограничений равенств, содержатся также ограничения-неравенства.
Теорема Куна-Таккера устанавливает связь между оптимальным планом задачи (1) – (3) и седловой точкой функции Лагранжа для этой задачи:
(4)где
; 
.Теорема Куна-Таккера. Пусть существует вектор
, такой что < 0, . Вектор
тогда и только тогда является оптимальным решением задачи (1) – (3), когда существует вектор 
, такой что, при 
, для всех и выполняется условие:
(5)
Точка
называется седловой точкой функции Лагранжа, а теорема Куна-Таккера – теоремой о седловой точке. Точка
называется седловой точкой функции Лагранжа (4), если вектор 
минимизирует функцию 
, а вектор 
максимизирует функцию 
, так что для всех 
, 
выполняется условие:
.Доказательство:
Достаточность. Пусть
- седловая точка функции 
и для нее выполняются условия (5). С учетом (4) эти условия имеют вид: 
Учитывая левую часть неравенства получим: для всех
= 0, а это возможно тогда, когда 
= 0. Тогда из правого неравенства получим: 
, но
, следовательно 
, таким образом, удовлетворяет условиям исходной задачи и во всех других точках функция принимает значение больше, чем в точке .Достаточность доказана.
Доказательство необходимости является громоздким, и его не приводим.
§ 2. Градиентный метод
(случай, когда оптимум находится на границе).
Рассмотрим задачу Н.П. следующего вида:
(1)
, (2)
. (3)Рассмотрим геометрическую интерпретацию задачи.
Пусть область решения задачи и линии уровня изображены на чертеже:
Если точка оптимума находится на границе области, то вектор-градиент Z в этой точке не равен нулю.
Найдем начальную точку А принадлежащую области решений. Из этой точки будем двигаться в направлении qradZ(A) до тех пор, пока Z не достигнет max значение в данном направлении. В данном случае, двигаясь в направлении qradZ(A) мы попадаем в точку находящуюся за границей области. Например, в точку B. Уменьшение значения параметра t приведет к тому, что мы будем двигаться по прямой AB и точку максимума не найдем. В этом случае в область решений надо вернуться иначе, а именно в направлении вектора qradZ(B). Пусть двигаясь в направлении этого вектора, мы попадем в точку С. Затем из точки С двигаемся в направлении вектора qradZ(С), попадаем в точку D из точки D в направлении qradZ(D) и т.д. такими зигзагообразными движениями мы, наконец, попадем в точку K.
При нахождении точек надо их находить так, чтобы значение Z возрастало. Из K попадем в точку L. Из чертежа видим, что точки K, L и
находится на одной прямой. Как проверить то, что точкиK иL находятся на одной прямой?
Отношения их координат приблизительно будут равны между собой. В этом случае находим точку пересечения
прямой KL с линией
или, изменяя значение t, постараемся, двигаясь вдоль прямой KL попасть в область решений по возможности ближе к границе = 0.Градиентные методы являются приближенными методами и применяются для решения задач с помощью вычислений техники: ПК. Как правило, с их помощью находится только локальные оптимумы и лишь в частных случаях, для задач выпуклого программирования находим глобальный оптимум. При этом функции f и qi должны быть непрерывными и дифференцированными функциями.
Замечание, Часто можно ограничиваться нахождением приближенного решения (не искать
) близко к . Критерием в этом случаем служит малое изменение Z при движении по прямой KL (для точек принадлежащих области решений).