W tym rozdziale omówimy elementy teorii dualności, tzn. innej charakteryzacji optymalności rozwiązania zadania optymalizacyjnego z ograniczeniami nierównościowymi. Teoria ta odróżnia się od poprzednio opisywanego podejścia Kuhna-Tucker'a tym, że nie wymagamy różniczkowalności funkcji celu i funkcji ograniczeń
. Ponadto, przy odpowiednich założeniach, rozwiązanie pierwotnego zadania optymalizacyjnego możemy łatwo uzyskać z rozwiązania tzw. zadania do niego dualnego. Niezależnie od zadania pierwotnego, zadanie dualne polega na maksymalizacji wklęsłej funkcji celu po nieujemnym oktancie. Jak zobaczymy w następnych rozdziałach, wklęsłość jest cechą gwarantującą dobrą zbieżność metod numerycznych. Prosty zbiór punktów dopuszczalnych dodatkowo przyspiesza działanie i ułatwia implementację algorytmów numerycznych. Nie należy zapominać także o tym, że zadanie dualne jest czasami łatwiejsze do rozwiązania metodami analitycznymi, czego przykłady zobaczymy w zadaniach na końcu niniejszego rozdziału.
Niech będą dowolnymi zbiorami, zaś
funkcją. Punkt
nazywamy punktem siodłowym funkcji
, jeśli
![]() |
Najprostszym przykładem punktu siodłowego jest ”środek siodła” (patrz rys. 10.1): ,
ma punkt siodłowy w
. Funkcja
ma minimum w
ze względu na zmienną
i maksimum ze względu na
.
Okazuje się, że punkt siodłowy funkcji Lagrange'a jest związany z rozwiązaniem globalnym problemu optymalizacji z ograniczeniami nierównościowymi:
![]() |
(10.1) |
Przypomnijmy, że przez oznaczamy zbiór punktów dopuszczalnych, tj.
![]() |
Jeśli jest punktem siodłowym funkcji Lagrange'a na
![]() |
tzn.
![]() |
to jest rozwiązaniem globalnym problemu (10.1) oraz
dla
.
Udowodnimy najpierw, że dla
. Nierówność
możemy rozwinąć następująco:
![]() |
Zatem dla każdego mamy
![]() |
W szczególności, dla dostajemy
![]() |
Wiemy, że jest punktem dopuszczalnym (
), czyli
dla
. Pamiętając, że
ma wszystkie współrzędne nieujemne wnioskujemy, iż
oraz każdy wyraz jest niedodatni. Stąd już wynika, że
dla
.
Skorzystamy teraz z drugiej nierówności dla
, aby wykazać globalną optymalność
. Nierówność tą rozpisujemy następująco:
![]() |
Z pierwszej części dowodu mamy . Z faktu, że
dostajemy
. Czyli
![]() |
W powyższym twierdzeniu nie zakładamy otwartości ani ciągłości funkcji
i
.
Zbiór punktów dopuszczalnych nie musi być wypukły.
Nie ma żadnych warunków regularności.
W tym podrozdziale zakładamy, że w problemie (10.1) zbiór jest wypukły oraz funkcje
,
są wypukłe. Dla takiego zadania optymalizacyjnego warunek punktu siodłowego funkcji Lagrange'a jest warunkiem koniecznym dla rozwiązania globalnego. Zaczniemy od prostszego przypadku, gdy wszystkie funkcje są różniczkowalne, by przejść później do twierdzenia nie wymagającego różniczkowalności. Jak wspomnieliśmy wcześniej, brak wymagania różniczkowalności odróżnia metodę punktu siodłowego od opisanej wcześniej metody Kuhn'a-Tucker'a.
Załóżmy, że zbiór w problemie programowania wypukłego jest otwarty oraz funkcje
i
,
są różniczkowalne w punkcie
. Jeśli
jest rozwiązaniem lokalnym (10.1) i spełniony jest jeden z warunków regularności: liniowej niezależności, afiniczności lub Slatera, to istnieje
, taki że
jest punktem siodłowym funkcji Lagrange'a na przestrzeni
Na mocy twierdzenia 5.2 istnieje wektor mnożników Langrange'a , dla których spełniony jest warunek optymalności pierwszego rzędu (spełnienie założeń tego twierdzenia wynika z regularności punktu
oraz rozważań rozdziału 6). Teza wynika teraz z ćwiczenia 10.1.
Na mocy twierdzenia 7.6 każdy punkt spełniający warunki pierwszego rzędu jest rozwiązaniem globalnym zadania programowania wypukłego. Nie jest zatem ważne, czy wymagać będziemy w powyższym lemacie, aby był rozwiązaniem lokalnym czy globalnym.
Przechodzimy teraz do głównego twierdzenia.
Niech będzie rozwiązaniem globalnym problemu programowania wypukłego (10.1) oraz istnieje
, taki że
dla
Wówczas istnieje
o tej własności, że
jest punktem siodłowym funkcji Lagrange'a na przestrzeni
, tzn.
![]() |
Ponadto, dla
Punkt siodłowy funkcji Langrange'a jest rozpatrywany na różnych przestrzeniach w tw. 10.1 i 10.2. W drugim ze wspomnianych twierdzeń przestrzeń jest większa, gdyż pierwsza zmienna przebiega cały zbiór , a nie tylko zbiór punktów dopuszczalnych
. W sumie, dostajemy równoważność istnienia punktu siodłowego funkcji Lagrange'a i rozwiązania globalnego zadania optymalizacji wypukłej.
Podobnie jak w dowodzie warunku koniecznego pierwszego rzędu, tw. 5.2, główną rolę będzie tutaj odgrywać twierdzenie o oddzielaniu zbiorów wypukłych. Wskaże nam ono wektor mnożników Lagrange'a .
Oznaczmy Zdefiniujmy następujące podzbiory
:
![]() |
![]() |
||
![]() |
![]() |
||
![]() |
![]() |
Zauważmy, że ostatni ze zbiorów jest ”oszukany”: jest on produktem półprostej kończącej się w minimum i ujemnego oktantu. Łatwo widzimy, że jest on wypukły. Z optymalności
dostajemy, że
Zbiór
nie jest jednak wypukły, więc nie możemy stosować twierdzeń o oddzielaniu. Radą na to jest spostrzeżenie, że zamiast
można brać zbiór wypukły
, który ma również puste przecięcie z
. Przypuśćmy przeciwnie: niech
Mamy zatem dla pewnego
następujące nierówności:
![]() |
Wnioskujemy z nich, że oraz
. A zatem punkt
jest dopuszczalny, zaś funkcja
przyjmuje w nim wartość mniejszą od
. Przeczy to optymalności
.
Przed przystąpieniem do dalszej części dowodu popatrzmy na zbiory dla następującego problemu optymalizacyjnego:
![]() |
Rozwiązaniem tego zagadnienia jest . Mamy jedno ograniczenie, więc szukane zbiory leżą w przestrzeni
. Na rysunku 10.2 znajduje się ich szkic. Zwróćmy uwagę na zależność między zbiorami
i
. Zbiór
jest brzegiem
dla
, lecz znajduje się w jego wnętrzu dla
Powróćmy do dowodu. Wypukłość zbioru już została uzasadniona. Wypukłość
dowodzimy bezpośrednio. Weźmy dwa punkty
oraz
. Istnieją wówczas punkty
o następującej własności:
![]() |
|||
![]() |
Zdefiniujmy . Z wypukłości
wynika, że
Mamy również
![]() |
gdzie pierwsza nierówność wynika z powyższych własności i
, zaś druga nierówność z wypukłości
. Podobnie, korzystając z wypukłości
, pokazujemy, że
![]() |
Stąd , ponieważ
![]() |
dla zdefiniowanego powyżej punktu Kończy to dowód wypukłości zbioru
.
Na mocy słabego twierdzenia o oddzielaniu, tw. 3.1, istnieje ,
i takie że
![]() |
Z faktu, że wynika, że
. Z ciągłości funkcji liniowej wnioskujemy, że
można brać z domknięcia
:
![]() |
Zatem dla mamy
![]() |
W szczególności powyższa nierówność zachodzi dla i
dla
:
![]() |
(10.2) |
Wykażemy teraz, że , co razem z obserwacją
będzie implikować
. Dowód przeprowadzimy przez zaprzeczenie: załóżmy
. Wówczas z nierówności (10.2) wynika, że
![]() |
W szczególności zachodzi to dla punktu z założenia twierdzenia. W tym punkcie mamy jednak
dla każdego
To, w połączeniu z faktem, iż
pociąga
. Przypomnijmy, że
, czyli
, a to przeczy wyborowi
z twierdzenia o oddzielaniu.
Wiemy zatem, że . Zdefiniujmy
![]() |
Oczywiście Ponieważ
, jako rozwiązanie, jest punktem dopuszczalnym, to
,
i
Dodajemy tą sumę do prawej strony nierówności (10.2) podzielonej przez
:
![]() |
Inaczej,
![]() |
Pozostaje jeszcze wykazanie drugiej nierówności punktu siodłowego. Biorąc i dzieląc obie strony nierówności (10.2) przez
dostajemy
Z drugiej strony punkt
jest dopuszczalny, czyli
Pamiętając, że
wnioskujemy, że każdy składnik tej sumy jest niedodatni. Stąd już mamy
![]() |
Dla dowolnego innego mamy
, czyli
![]() |
Ta nierówność jest równoważna
![]() |
Z teorią puntów siodłowych związane są pojęcia zadania pierwotnego i dualnego. Rozważmy zadanie optymalizacyjne (10.1) i związaną z nim funkcję Lagrange'a . Zdefiniujmy funkcję
![]() |
Zauważmy, że
![]() |
A zatem zadanie (10.1) można zapisać w wydawałoby się prostszej postaci
![]() |
Niestety powyższe przeformułowanie sprowadza się do rozwiązania oryginalnego zadania, a więc nie zawiera żadnej ,,wartości dodanej”; ale tylko do czasu. Zanim zdradzimy jego zastosowanie, zdefiniujmy kolejną funkcję
![]() |
Dla dowolnego i
mamy
.
Jeśli jest punktem siodłowym funkcji Lagrange'a na
, to
.
Powyższe spostrzeżenia kierują nas we właściwą stronę. Będziemy wykorzystywać funkcje i
do znajdowania punktów siodłowych.
Zadaniem pierwotnym nazywamy problem optymalizacyjny
![]() |
Zadaniem dualnym do niego jest problem optymalizacyjny
![]() |
Z własności wspomnianych w uwadze 10.4 wynika, że wartość rozwiązania zadania pierwotnego jest nie mniejsza niż wartość rozwiązania zadania dualnego:
![]() |
Co więcej, rozwiązanie zadania dualnego daje dolne oszacowanie na wartość funkcji :
Dla dowolnego punktu dopuszczalnego oraz dowolnego
mamy
![]() |
A zatem
![]() |
Dowód pozostawiamy jako ćwiczenie.
∎Luką dualności nazwiemy różnicę między wartością rozwiązania zadania pierwotnego i dualnego:
![]() |
Zapiszmy w języku funkcji pierwotnej i dualnej warunek punktu siodłowego: jest punktem siodłowym, jeśli
![]() |
Innymi słowy, jeśli funkcja Lagrange'a posiada punkt siodłowy, to luka dualności jest zerowa. Ma to miejsce, na przykład, jeśli spełnione są założenia tw. 10.2.
Możemy teraz zaproponować algorytm rozwiązywania zagadnienia (10.1) przy pomocy metod dualnych.
Rozwiąż zadanie dualne. Jego wartość daje dolne ograniczenie na wartość rozwiązania problemu pierwotnego na mocy lematu 10.2.
Wyjaśnijmy warunki punktu drugiego. Z faktu wynika, że
dla dowolnego
Zatem mamy prawą nierówność warunku punktu siodłowego. Pozostaje jeszcze nierówność lewa. Przypomnijmy, że
dla punktu dopuszczalnego
i
dla dowolnego
W punkcie drugim zakładamy, że
, co pociąga
![]() |
a zatem jest punktem siodłowym.
Udowodnij, że jeśli w problemie optymalizacyjnym (10.1) funkcje i
,
, są wypukłe, to punkt spełniający warunek konieczny pierwszego rzędu jest punktem siodłowym funkcji Lagrange'a na przestrzeni
Uzasadnij, że dla dowolnego
i
.
Uzasadnij nierówność:
![]() |
Udowodnij, że jeśli jest punktem siodłowym funkcji Lagrange'a, to
lub, innymi słowy, luka dualności jest zerowa.
Udowodnij lemat 10.2.
Wykaż, że funkcja dualna jest wklęsła.
Podaj przykład problemu optymalizacyjnego, dla którego luka dualności jest dodatnia.
Rozwiąż metodą dualną zadanie
![]() |
gdzie Zwróć uwagę na umieszczenie jednego z ograniczeń w zbiorze
.
Rozwiąż metodą dualną zadanie
![]() |
gdzie oraz
Rozważ zbiór
Znajdź zadanie dualne (czyli formę zadania ) dla zadania optymalizacji liniowej
![]() |
gdzie ,
jest macierzą
i
Znajdź zadanie dualne do zadania programowania kwadratowego
![]() |
gdzie jest macierzą symetryczną dodatnio określoną,
jest macierzą
i
Niech . Transformatą Legendre'a-Fenchela funkcji
nazywamy funkcję
daną wzorem
![]() |
Rozważmy problem optymalizacyjny:
![]() |
gdzie ,
,
, zaś
są dowolnymi macierzami o odpowiednich wymiarach. Udowodnij, że problem do niego dualny ma następującą postać:
![]() |
Rozbij ograniczenie równościowe na dwa ograniczenia nierównościowe.
Znajdź transformatę Legendre'a-Fenchela następujących funkcji:
![]() |
|||
![]() |
|||
![]() |
|||
![]() |
|||
![]() |
Udowodnij, że transformata Legendre'a-Fenchela jest wypukła dla dowolnej funkcji
.
Wykaż równoważność następujących dwóch zadań optymalizacyjnych:
![]() |
oraz
![]() |
(10.3) |
gdzie przez oznaczamy rzędy macierzy
Udowodnij następnie, że zadaniem dualnym do (10.3) jest
![]() |
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
Projekt współfinansowany przez Unię Europejską w ramach
Europejskiego Funduszu Społecznego.
Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.