Rozważmy problem optymalizacyjny
![]() |
(5.1) |
gdzie i
. Niech
będzie rozwiązaniem lokalnym. Będziemy chcieli powiązać geometrię lokalną zbioru
w punkcie
z zachowaniem funkcji
, czyli kierunkami spadku jej wartości. Przez lokalną geometrię
rozumiemy zbiór kierunków, w których możemy się poruszyć z punktu
nie opuszczając
.
Stożkiem kierunków stycznych do
w punkcie
nazywamy zbiór wektorów
takich że
![]() |
dla pewnych ,
i
.
Powyższa definicja mówi, iż kierunek należy do stożka kierunków stycznych
, jeśli jest on granicą kierunków wyznaczonych przez ciąg punktów dopuszczalnych
zmierzających to
Zapisać możemy to formalnie w następujący sposób:
![]() |
(5.2) |
Dowód tej tożsamości oraz poniższego lematu pozostawiamy jako ćwiczenie.
Zbiór jest stożkiem, tzn.
dla dowolnych
i
. W szczególności,
.
Jeśli jest punktem wewnętrznym zbioru
, to
.
Stożek jest domknięty.
Na rysunku 5.1 znajdują się trzy przykłady zbiorów i stożków do nich stycznych w punkcie . Stożki te są przesunięte o wektor
, by pokazać ich zależność od kształtu zbioru. W przykładzie (a) i (c) zakładamy, że brzeg zbioru
jest gładki, więc stożki te są półprzestrzeniami ograniczonymi przez styczną w
. W przykładzie (b) zbiór
to środek narysowanego stożka (bez brzegu). Wówczas stożek kierunków stycznych jest domknięciem zbioru
.
Jak już wspomnieliśmy, stożek kierunków stycznych jest ściśle związany z rozwiązaniem zagadnienia (5.1). Jeśli w punkcie funkcja
ma minimum lokalne na
, to wówczas kierunki spadku wartości funkcji
nie mogą należeć do zbioru kierunków stycznych w punkcie
. Gdyby tak nie było, to poruszając się w kierunku spadku funkcji
zmniejszalibyśmy jej wartość jednocześnie pozostając w zbiorze
. Intuicje te formalizujemy poniżej.
Niech będzie różniczkowalna w
. Zbiorem kierunków spadku funkcji
w punkcie
nazywamy
![]() |
Weźmy . Wówczas
dla pewnego ciągu punktów
zbieżnego do
oraz ciągu liczb
. Z definicji różniczkowalności
w
mamy
![]() |
Z faktu, że jest rozwiązaniem lokalnym
dla dostatecznie dużych
. W połączeniu z powyższym wzorem daje to następujące oszacowanie:
![]() |
Mnożąc obie strony powyższej nierówności przez dostajemy
![]() |
Zrobimy teraz sztuczkę, aby rozwiązać problem z i przejdziemy z
to nieskończoności:
![]() |
Udowodniliśmy zatem, że , czyli
. Kończy to dowód twierdzenia.
Rozważmy następujący problem optymalizacyjny:
![]() |
Oznaczmy i
. Zbadamy zbiory
i
w następujących punktach:
.
. Punkt ten leży wewnątrz zbioru
, czyli
. Zbiór kierunków spadku funkcji
dany jest następująco:
![]() |
W oczywisty sposób część wspólna powyższych zbiorów nie jest pusta, czyli w punkcie nie ma minimum.
. Punkt ten leży na brzegu zbioru
. Łatwo można zauważyć, że
![]() |
Zbiory te mają niepuste przecięcie (patrz podwójna kratka na rys. 5.2), więc w punkcie nie ma minimum.
. Zauważmy, że
![]() |
Zbiory te mają zatem puste przecięcie, więc w punkcie może być minimum.
Bezpośrednie wykorzystanie twierdzenia 5.1 do szukania kandydatów na rozwiązania zadań z ograniczeniami nie wygląda zachęcająco. Dlatego postaramy się opisać prościej zbiór oraz warunek
.
Zajmiemy się problemem optymalizacyjnym w następującej formie:
![]() |
(5.3) |
gdzie jest zbiorem otwartym i
. A zatem
![]() |
(5.4) |
Funkcje nazywane są ograniczeniami nierównościowymi, zaś cały problem (5.3) zadaniem optymalizacyjnym z ograniczeniami nierównościowymi.
Ustalmy i załóżmy, że funkcje
są ciągłe. Wówczas ruch wokół
ograniczają lokalnie tylko te warunki, dla których
. W przypadku pozostałych, z ciągłości
wynika, iż istnieje pewne otoczenie
, na którym mamy
. Okazuje się, że ta obserwacja będzie pełnić ważną rolę w procesie optymalizacji z ograniczeniami nierównościowymi.
Zbiorem ograniczeń aktywnych w punkcie nazywamy zbiór
![]() |
Głównym wynikiem tego rozdziału będzie powiązanie własności ograniczeń aktywnych w danym punkcie z lokalną geometrią tego zbioru wokół
. W tym celu wprowadźmy następującą definicję.
Niech i
różniczkowalne w
dla ograniczeń aktywnych
. Stożkiem kierunków stycznych dla ograniczeń zlinearyzowanych nazywamy zbiór
![]() |
Stożek kierunków stycznych dla ograniczeń zlinearyzowanych jest zbiorem wielościennym, a zatem wypukłym i domkniętym.
Jeśli , to
![]() |
Dowód przebiega bardzo podobnie do dowodu twierdzenia 5.1. Weźmy . Wówczas
dla pewnego ciągu punktów
zbieżnego do
oraz ciągu liczb dodatnich
. Ustalmy
. Z definicji różniczkowalności
w
mamy
![]() |
Ograniczenie -te jest aktywne w
. Zatem
. Oczywiście,
, ponieważ
. W połączeniu w powyższym wzorem daje to następujące oszacowanie:
![]() |
Mnożąc obie strony powyższej nierówności przez dostajemy
![]() |
Zrobimy teraz sztuczkę, aby rozwiązać problem i przejdziemy z
to nieskończoności:
![]() |
Udowodniliśmy zatem, że . Analogicznie wynik otrzymujemy dla każdego ograniczenia aktywnego
. A zatem
Rozważmy zbiór , patrz rysunek 5.3. Zapiszmy go w kanonicznej formie (5.4):
![]() |
Zbadajmy trzy punktu tego zbioru ,
i
.
:
i
.
:
,
,
![]() |
:
,
,
![]() |
![]() |
||
![]() |
Rozważmy ten sam zbiór co w powyższym przykładzie, lecz zapiszmy go nieco inaczej:
![]() |
Zmianie uległo drugie ograniczenie: z na
. Nowy opis zbioru
odpowiada ograniczeniom
,
. Rozważmy zbiory
i
w punkcie
. Stożek kierunków stycznych jest identyczny, gdyż zbiór się nie zmienił:
![]() |
Natomiast stożek kierunków stycznych dla ograniczeń zlinearyzowanych jest następujący:
![]() |
![]() |
||
![]() |
|||
![]() |
Widzimy zatem, że nie zawsze zachodzi równość pomiędzy i
.
W lemacie 5.2 wykazaliśmy, że . Pokazaliśmy w przykładach, że dość często mamy równość tych dwóch zbiorów. Okazuje się, że to bardzo ważna własność, która będzie punktem wyjścia dla całej teorii optymalizacji nieliniowej Kuhna-Tucker'a. Zanim jednak przejdziemy do głównego twierdzenia dowiedziemy pomocniczy, lecz bardzo ważny lemat.
Niech będzie macierzą
i
. Wówczas dokładnie jeden z układów ma rozwiązanie:
![]() |
Pokażemy najpierw, że jeśli układ (2) ma rozwiązanie, to układ (1) go nie ma. Weźmy zatem spełniające (2). Zatem
. Wstawiamy to do układu (1) i otrzymujemy
![]() |
Pierwsza nierówność oznacza, że każda współrzędna wektora jest niedodatnia. Ponieważ współrzędne
są nieujemne, to iloczyn skalarny
jest niedodatni. Przeczy to drugiej nierówności, a zatem dowodzi, że (1) nie ma rozwiązania.
Załóżmy teraz, że układ (2) nie ma rozwiązania. Zdefiniujmy zbiór
![]() |
Łatwo sprawdzić, że jest to zbiór wypukły i domknięty. Z faktu, że układ (2) nie ma rozwiązania wynika, że . Zastosujmy więc mocne twierdzenia o oddzielaniu, tw. 3.2 do zbiorów
i
. Istnieje więc wektor
taki że
![]() |
Pokażemy, że jest rozwiązaniem układu (1). Oznaczmy
. Ponieważ
, to
, co pociąga
. Pozostaje tylko udowodnić, że
. Przypuśćmy, że
-ta współrzędna
jest dodatnia. Z definicji zbioru
wynika, że dla dowolnego
zachodzi
. Zdefiniujmy ciąg
, gdzie
jest na
-tej współrzędnej. Na mocy założenia o dodatniości
dostajemy
![]() |
co przeczy temu, że . Sprzeczność ta dowodzi, że
.
Niech będzie rozwiązaniem lokalnym (5.3). Jeśli funkcje
oraz
,
, są różniczkowalne w
oraz
, to istnieje
, takie że
![]() |
(5.5) |
Często tezę powyższego twierdzenia zapisuje się biorąc sumę po wszystkich :
![]() |
Jest to naginanie notacji, gdyż funkcje opisujące ograniczenia nieaktywne nie muszą być różniczkowalne w punkcie . Z drugiej strony są one mnożone przez zerowe współczynniki
. Jest to pewne usprawiedliwienie powyższej notacji, którą należy rozumieć tak, jak zapisane zostało w twierdzeniu 5.2.
Na mocy twierdzenia 5.1 mamy . Dalej, korzystając z założenia, dostajemy
, co innymi słowy oznacza, że nie istnieje rozwiązanie
układu
![]() |
Stosujemy lemat Farkasa z i macierzą
złożoną wierszowo z gradientów ograniczeń aktywnych
,
. Istnieje zatem
takie że
lub inaczej
![]() |
Zdefiniujmy następująco:
i
. Wówczas powyższa równość jest równoważna następującej
![]() |
Z definicji oczywiste jest, że
.
Założenia twierdzenia Kuhna-Tuckera są trywialnie spełnione, gdy , tzn. gdy
. Wówczas warunki (5.5) sprowadzają się do
![]() |
Na zakończenie zwróćmy jeszcze raz uwagę na tezę twierdzenia Kuhna-Tuckera. Warunki (5.5) nazywane są warunkami koniecznymi pierwszego rzędu. Wektor będzie pojawiał się jeszcze wiele razy na tym wykładzie. Nadajmy mu zatem nazwę:
Wektor spełniający (5.5) nazywa się wektorem mnożników Lagrange'a w punkcie
.
Wykaż, że zbiór dla
jest stożkiem.
Udowodnij, że stożek kierunków stycznych jest zbiorem domkniętym.
Udowodnij tożsamość (5.2).
Znajdź stożek kierunków stycznych do zbioru w punkcie
, gdy
Udowodnić, że dla zadania
![]() |
warunek konieczny pierwszego rzędu przyjmuje postać:
![]() |
Nierówność dla wektorów oznacza nierówność po współrzędnych.
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.