Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


¬ыпуклое программирование




ќбща€ задача выпуклого программировани€ имеет вид

(6.4.1)

где Ц выпуклые функции, Ц выпуклое множество.

Ѕудем обозначать Ц область определени€ функции, т.е. множество на котором функци€ определена, а за его пределами не определена.

”слови€ экстремума. Ќеобходимые и достаточные услови€ задачи (6.4.1) сформулированы в следующей теореме.

“еорема 17 ( ун-“аккер). ѕусть , i=1,Е,m, Ц выпуклые функции, Ц выпуклое множество, вход€щее в области определени€ функций и выполн€етс€ условие —лейтера: найдетс€ такое, что

(6.4.2)

“огда допустима€ точка €вл€етс€ глобальным решением (6.4.1), если и только если найдутс€ такие, что:

и (6.4.3)

, (6.4.4)

где и

, (6.4.5)

 ак и ранее функцию будем называть функцией Ћагранжа, вектор Ц множител€ми Ћагранжа, Ц пр€мыми переменными, Ц двойственными переменными, условие Ц условием дополн€ющей нежесткости, набор индексов Ц множеством активных ограничений. ≈сли дл€ задачи (6.4.1) выполнены услови€ теоремы 1, то будем говорить о регул€рной точке минимума или регул€рной задаче.

“еорема  уна-“аккера утверждает, что в случае регул€рной точки минимума найдутс€ неотрицательные множители Ћагранжа , удовлетвор€ющие условию дополн€ющей нежесткости, такие, что функци€ Ћагранжа при достигает минимума на в точке . “аким образом по€вл€етс€ возможность свести задачу с неравенствами к задаче минимизации без ограничений.

ѕусть Ц два множества. ѕара называетс€ седловой точкой функции на , если

(6.4.6)

т.е. точка €вл€етс€ точкой минимума по на , а Ц точкой максимума по на . ¬ыражение (6.4.6) эквивалентно равенству

. (6.4.7)

Ќаличие седловой точки означает возможность перестановки операций минимума и максимума.

“еорема 18 ( ун-“аккер). ¬ услови€х теоремы 1 €вл€етс€ решением задачи (6.4.1) тогда и только тогда, когда пара при некотором €вл€етс€ седловой точкой на , т.е.

(6.4.8)

ƒвойственность. —имметри€ относительно переменных и в (6.4.8) дл€ задачи минимизации (6.4.1) по позвол€ет наед€тс€ найти экстремальную задачу относительно переменных дл€ которой также справедливы услови€ (6.4.8). ¬ведем функцию

(6.4.9)

ѕоэтому исходна€ задача (6.4.1) может быть записана

. (6.4.10)

ќбразуем задачу, помен€в роль переменных и операций максимума и минимума. ¬ведем

(6.4.11)

(возможно, что при некоторых ) и рассмотрим задачу

. (6.4.12)

«адача (6.4.12) называетс€ двойственной, а (6.4.1) или (6.4.10) Ц пр€мой.

“еорема 19 (теорема двойственности). —праведливы соотношени€ двойственности:

а) ƒл€ любых допустимых и (т.е. дл€ )

. (6.4.13)

б) ≈сли пр€ма€ задача регул€рна, Ц ее решение, Ц множители Ћагранжа, то Ц решение (6.4.12) и

. (6.4.14)

в) ≈сли дл€ допустимых, , имеет место (6.4.14), то Ц решение пр€мой, а Ц решение двойственной задачи.

ћаксимум y(y) может достигатьс€ лишь в точках, где . ѕоэтому (6.4.12) равносильна задаче

(6.4.15)

«начение теоремы двойственности в том, что при переходе к двойственной задаче при нова€ задача может оказатьс€ существенно более простой, чем исходна€. Ётому способствуют возможность простого вычислени€ и ее производных и правильное распределение ограничений между множеством либо и множеством ограничений

≈динственность решени€ (6.4.1) гарантируетс€ строгой выпуклостью функции .





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-02-12; ћы поможем в написании ваших работ!; просмотров: 697 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

≈сли президенты не могут делать этого со своими женами, они делают это со своими странами © »осиф Ѕродский
==> читать все изречени€...

2079 - | 1993 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.011 с.