W tym rozdziale podamy warunki dostateczne równości stożka kierunków stycznych i stożka kierunków stycznych dla ograniczeń zlinearyzowanych
. Przypomnijmy, że jest to główne założenie twierdzenia Kuhna-Tuckera, tw. 5.2, opisującego warunek konieczny pierwszego rzędu dla lokalnego rozwiązania problemu optymalizacyjnego z ograniczeniami nierównościowymi (5.3).
Sformułujemy teraz trzy warunki dostateczne równości , zwane warunkami regularności. Dowody dostateczności podamy w kolejnych twierdzeniach.
W punkcie spełniony jest:
warunek liniowej niezależności, jeśli funkcje ,
, są ciągłe w
oraz wektory
, dla
, są liniowo niezależne,
warunek afiniczności, jeśli funkcje ,
, są afiniczne oraz funkcje
,
, są ciągłe w
,
warunek Slatera, jeśli funkcje ,
są pseudowypukłe w
, funkcje
,
, są ciągłe w
oraz istnieje
, dla którego
dla
.
Zauważmy, że w warunku Slatera nie wymagamy, aby punkt spełniał warunki ograniczeń nieaktywnych, tzn.
nie musi być w zbiorze
.
Jeśli w punkcie spełniony jest warunek afiniczności, to
.
Zawieranie wynika z lematu 5.2. Wystarczy zatem wykazać zawieranie w drugą stronę.
Niech . Udowodnimy, że istnieje
, taka że cały odcinek
,
, zawarty jest w
:
![]() |
(6.1) |
Zauważmy, że dla
. Z ciągłości tych funkcji w
wynika, że istnieje
, dla której
,
,
. Pozostaje jeszcze wykazać, że nierówność taka zachodzi dla ograniczeń aktywnych. Ustalmy
. Z definicji
wiemy, że
. Ograniczenie
jest afiniczne, czyli postaci
, gdzie
,
. Zatem
. Z faktu, że
jest aktywne w
dostajemy również
. Stąd dla dowolnego
mamy
![]() |
Dowodzi to (6.1).
Pozostaje już tylko skonstruować ciąg ,
i
. Kładziemy
![]() |
Wówczas ,
oraz
, czyli trywialnie
![]() |
a zatem .
Przed przystąpieniem do dowodu analogicznych twierdzeń dla pozostałych warunków regularności sformułujemy pomocniczy lemat. Wprowadźmy zbiór
![]() |
Zauważmy, że jeśli w punkcie funkcje
,
, są różniczkowalne w
, zaś funkcje
,
są ciągłe w
, to
oznacza, że
dla dostatecznie małych
.
Niech oraz funkcje
,
, są różniczkowalne w
, zaś funkcje
,
są ciągłe w
.
Wówczas
I) ,
II) Jeśli , to
.
Dowód (I) zostawiamy jako ćwiczenie. Do dowodu (II) zauważmy, że jest wnętrzem zbioru
. Ponadto
jest zbiorem wielościennym, a zatem wypukłym (patrz lemat 4.5). Zastosowanie lematu 3.2 kończy dowód.
Jeśli w punkcie spełniony jest warunek Slatera, to
.
Pokażemy najpierw, że . Niech
taki że
dla
. Z pseudowypukłości
w punkcie
dostajemy
dla
, czyli
.
Na mocy lematu 6.1 mamy . Udowodniliśmy także, że
oraz, że
jest domknięty. A zatem
.
Dowód analogicznego twierdzenia dla warunku liniowej niezależności wymaga pomocniczego lematu w stylu lematu Farkasa. Wynik ten jest jednak wcześniejszy i został uzyskany przez Paul'a Gordana w 1873 roku.
Niech będzie macierzą
. Wówczas dokładnie jeden z układów ma rozwiązanie:
![]() |
Dowód rozpoczniemy od uzasadnienia, że oba te układy nie mogą mieć rozwiązania jednocześnie. Załóżmy więc przez sprzeczność, że istnieją spełniające (1)-(2). Z faktu, że
rozwiązuje (2), dostajemy, że
. Z drugiej strony
rozwiązuje (1), czyli
dla każdego
. Pamiętając, że
,
, i
mamy
. Dostaliśmy więc sprzeczność, co dowodzi, że nie może istnieć jednocześnie rozwiązanie (1) i (2).
Następnym krokiem dowodu będzie wykazanie, że zawsze któryś z układów ma rozwiązanie. W tym celu udowodnimy, że jeśli układ (1) nie ma rozwiązania, to układ (2) ma rozwiązanie. W tym celu zdefiniujmy następujące zbiory wypukłe:
![]() |
Z faktu, że układ (1) nie ma rozwiązania, wynika, iż zbiory te są rozłączne. Słabe twierdzenie o oddzielaniu implikuje istnienie wektora ,
, takiego że
![]() |
Wykażemy, że . Przypuśćmy przeciwnie, że istnieje współrzędna
. Rozważmy ciąg
, gdzie
jest na
-tej pozycji. Wówczas
oraz
, a zatem dostaliśmy sprzeczność, gdyż
jest skończone.
Wiemy zatem, że wektor ma wszystkie współrzędne nieujemne. Pociąga to
. Weźmy
. Wówczas
, czyli
. A zatem
![]() |
co implikuje, że , czyli
. Rozwiązaniem układu (2) jest zatem
.
Jeśli w punkcie spełniony jest warunek liniowej niezależności, to
.
Identycznie jak w dowodzie tw. 6.2 wystarczy pokazać, że . Niech
będzie macierzą składającą się z gradientów
ograniczeń aktywnych (jako rzędów). Na mocy liniowej niezależności nie istnieje wektor
,
, o tej własności, że
. Nie istnieje więc rozwiązanie układu (2) w lemacie 6.2. A zatem ma rozwiązanie układ (1), czyli istnieje
, takie że
:
![]() |
Stąd .
Rozważmy problem optymalizacji na zbiorze:
![]() |
Zbiór . Ograniczenia są opisane przez trójkę funkcji
![]() |
W punkcie wszystkie ograniczenia są aktywne i mamy
![]() |
Warunek liniowej niezależności ograniczeń nie jest spełniony w . Ograniczenia aktywne nie są również afiniczne. Pozostaje zatem sprawdzić warunek Slatera. Wszystkie funkcje ograniczeń są wypukłe, a więc także pseudowypukłe. W punkcie
mamy
dla
. Zachodzi więc warunek Slatera.
Rozważmy zadanie optymalizacyjne:
![]() |
Zbiór punktów dopuszczalnych naszkicowany jest na rysunku 6.1. Zapiszmy funkcje opisujące ograniczenia:
![]() |
Zauważmy, że w każdym punkcie dopuszczalnym, poza , spełniony jest warunek liniowej niezależności. Widać jednak, że rozwiązaniem powyższego problemu optymalizacyjnego jest
. Niestety w tym punkcie
:
![]() |
Niech będzie macierzą symetryczną
. Rozważmy zadanie optymalizacyjne:
![]() |
Zapiszmy najpierw problem optymalizacyjny w kanonicznej formie. Zauważmy przy tym, że warunek jest równoważny
.
![]() |
Oznaczmy przez zbiór punktów dopuszczalnych. Zauważmy, że w każdym punkcie dopuszczalnym spełnione są warunki liniowej niezależności i Slatera. Wynika stąd, że rozwiązanie powyższego zadania spełnia warunki konieczne pierwszego rzędu (warunki Kuhna-Tuckera (5.5)). Znajdziemy teraz wszystkie punkty ,,podejrzane”.
Warunki Kuhna-Tuckera mają następującą postać:
![]() |
Przypadek . Wówczas
(z powodu drugiego równania) i pierwsze równanie przyjmuje postać
, którą poprzez transponowanie obu stron sprowadzamy do
![]() |
Równanie to spełnione jest przez wszystkie ,
. W szczególności ma ono co najmniej jedno rozwiązanie (
).
Przypadek . Teraz nic nie możemy powiedzieć o
. Może być zerowe lub dodatnie. Pierwsze równanie przyjmuje jednak postać
, które po stransponowaniu wygląda następująco:
![]() |
Rozwiązaniami są zatem wektory własne () odpowiadające nieujemnym wartościom własnym (
). Zbiór rozwiązań może być pusty, jeśli wszystkie wartości własne są ujemne.
Podsumowując, zbiór punktów podejrzanych, czyli punktów, w których spełniony jest warunek konieczny pierwszego rzędu, ma postać:
![]() |
Na obecnym etapie nie mamy żadnej techniki pozwalającej na znalezienie rozwiązania. Możemy tylko posłużyć się zdrowym rozsądkiem. Otóż, jeśli , to wartość funkcji celu
jest zerowa. Dla dowolnego elementu drugiego zbioru, wartość funkcji celu jest równa wartości własnej. Możemy zatem wyciągnąć następujący wniosek: jeśli maksymalna wartość własna jest dodatnia, to każdy wektor jej odpowiadający jest rozwiązaniem globalnym. Jeśli macierz
nie ma wartości własnych większych od zera, to rozwiązaniem jest dowolny punkt z jądra
o normie nie większej niż
.
Uzasadnij prawdziwość stwierdzenia umieszczonego w uwadze 6.1, by później udowodnić, że , gdzie
zdefiniowane jest w lemacie 6.1.
Przez ”punkty podejrzane” problemu optymalizacyjnego rozumiemy takie punkty dopuszczalne, w których nie są spełnione warunki regularności albo spełnione są warunki konieczne pierwszego rzędu. Znajdź wszystkie punkty podejrzane dla następującego problemu optymalizacyjnego:
![]() |
Czy w którymś z nich jest rozwiązanie? Jeśli tak, to w którym? Odpowiedź uzasadnij.
Znajdź zbiór rozwiązań problemu optymalizacyjnego
![]() |
gdzie . Uzasadnij, że są to wszystkie rozwiązania.
Znajdź rozwiązania globalne problemu optymalizacyjnego
![]() |
Znajdź minima i maksima globalne funkcji
![]() |
na zbiorze
![]() |
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.