Обобщение ММЛ. Теорема Куна-Таккера. Локальные условия Куна-Таккера.

Ранее был изучен ММЛ для решения классической задачи условной оптимизации. Этот метод позволяет исходную задачу классической условной оптимизации преобразовать в задачу безусловной оптимизации путем введения функции Лагранжа вида:

(1)

Действительно, исходная задача условной оптимизации (УО) имеет вид:

(2)

(3)

Введение (1), включающую в себя целевую функцию и функции ограничения , с соответствующими " весами", позволяют далее решать задачу безусловной оптимизации (БО) ; необходимые условия имеют вид:

Из (4), (5) следует, что классическую задачу условной оптимизации (КЗУО) можно рассматривать как задачу о нахождении Седловой точки функции Лагранжа, т.е. имеет место неравенство:

, (6)

 

 

где - -мерная точка минимума, а - -мерная точка максимума.

Нельзя ли применить ММЛ к решению задачи НП общего вида? Например:

(7)

Ответ: можно.

Обоснованием применимости ММЛ к решению задачи НП (7), (8), (9) является теорема Куна-Таккера.

Теорема: Предположим, что существует вектор , такой, что , , тогда необходимым и достаточным условием оптимальности вектора , принадлежащего допустимой области является существование такого вектора , что для всех , , выполняются неравенства:

(6')

(6" )

(6" ')

Для случая, когда , - выпуклые дифференцируемые функции, неравенство (6') легко преобразуется в неравенство. Одно из них (6" ), другое получается из (6" ').

Локальное условие Куна-Таккера:

Из (6" )

Из (6" ')

Докажем, что если исходным является неравенство (10), (11), (12), то справедливо (6" ).

Доказательство: Разложим в окрестности точки функцию в ряд Тейлора:

 

 

ЛК №13

20.11.2003

 

(16)

В разложении учтены только линейные по приращению аргументов слагаемые.

(17)

(18)

Из (18) с очевидностью следует неравенство (6" ).

Аналогично можно доказать, что если в качестве исходного взять (6" ) и (6" '), то можно также просто доказать справедливость условий Куна-Таккера соответственно (10), (11), (12) и (13), (14), (15).

Локальные условия Куна-Таккера – необходимые условия решения задачи НП вида (7), (8), (9). Аналог необходимых условий: , в задаче классической условной оптимизации.

 

Градиентные методы решения задач нелинейного выпуклого программирования (НВП).

Задачи НВП – задачи, в которых целевая функция и функции, представляющие неравенства ограничений (функции, определяющие ОДР ) - - нелинейные выпуклые функции.

Отметим, что если целевая функция содержит единственную экстремальную точку внутри области , то для решения такой задачи НВП можно воспользоваться градиентными методами решения задач безусловной оптимизации.

Если же достигает экстремального значения в точке, находящейся на границе , то градиентные методы применимы также, однако, имеются сложности при применении.

Среди задач НВП различают:

1) задачи с линейными ограничениями;

2) задачи с нелинейными ограничениями.

Задачи с нелинейными ограничениями такие, что - нелинейная выпуклая функция, а - линейные функции.

Задачи НВП с нелинейными ограничениями, такие, что и , - нелинейные выпуклые функции.

 

См. [5].

 

 

Аналитическое выражение и пример решения задачи ИВП с линейными ограничениями градиентным методом приведен в [5].

 

 

См. [6].

 

А. Задачи НВП с линейными ограничениями.

(1)

- нелинейная выпуклая функция.

, (2')

В геометрическая интерпретация этой задачи имеет вид:

, т.к. - острый угол. (4)

Направление находится из условия максимизации скалярного произведения.

- условие экстремальности.

; .

Траектория поиска точки максимума .

Рассмотрим более детально один из методов решения задач (1), (2'), (3) – метод Франка-Вульфа.

 

А1. Метод Франка-Вульфа.

Этот метод позволяет исходную задачу НВП с линейными ограничениями (1), (2'), (3) преобразовать в задачу ЛП и затем, зная решение последней, найти решение исходной задачи.

 

 

Пример решения НВП с линейными ограничениями методом Франка-Вульфа см. [6].

 

 

Аналитические выражения, представляющие этот метод см. в [2].

 

 

Нелинейную выпуклую целевую функцию аппроксимируем линейной функцией переменных , причем, коэффициент этой аппроксимации являющейся проекции ; аппроксимация осуществляется на каждой итерации.

(5)

Теперь очевидно, что (5), (2'), (3) представляют задачу ЛП, которая решается универсальным эффективным СМ.

Итак, на каждой итерации в результате решения задачи ЛП находим оптимальное решение .

Итерационная формула, позволяющая найти решение исходной задачи, имеет вид:

(6)

находится в результате решения уравнения:

(7)

Итерационный поиск точки экстремума исходной целевой функции продолжаются до выполнения условий:

.

 

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: