W tym rozdziale wyprowadzimy warunek konieczny pierwszego rzędu dla problemu optymalizacyjnego w następującej formie:
![]() |
(8.1) |
gdzie jest zbiorem otwartym i
. Zbiór punktów dopuszczalnych zadany jest następująco:
![]() |
(8.2) |
Przypomnijmy, że funkcje nazywane są ograniczeniami nierównościowymi, funkcje
są ograniczeniami równościowymi, zaś cały problem (8.1) nazywa się zadaniem optymalizacyjnym z ograniczeniami mieszanymi.
Rozważmy następujący problem optymalizacyjny:
![]() |
dla pewnego i
. Ograniczenie równościowe możemy zamienić na dwa ograniczenia nierównościowe:
![]() |
Ograniczenia są afiniczne, czyli w każdym punkcie spełniony jest warunek afiniczności. Jeśli jest rozwiązaniem lokalnym, to istnieje wektor mnożników Lagrange'a
i spełnione są warunki Kuhna-Tuckera (5.5):
![]() |
Punkt jest dopuszczalny (jako że jest rozwiązaniem), czyli spełnia ograniczenia:
. Stąd trywialnie spełnione są druga i trzecia równość. Możemy zatem powyższe warunki równoważnie zapisać jako:
![]() |
Oznaczmy . Warunki nieujemności
implikują, że
. Dostajemy więc finalnie:
![]() |
Jest to warunek Kuhna-Tuckera dla ograniczeń równościowych.
Powyższy przykład sugerowałby, że teoria dla problemów z ograniczeniami nierównościowymi, zbudowana w poprzednich rozdziałach, pozwala poradzić sobie z ograniczeniami równościowymi. Niestety nie jest to prawda. Ograniczenia afiniczne są szczególnym przypadkiem. Jeśli któreś z ograniczeń równościowych nie jest afiniczne i rozbijemy je na dwie nierówności, jak powyżej, to w żadnym punkcie zbioru nie jest spełniony ani warunek liniowej zależności ograniczeń ani warunek Slatera.
Teoria wprowadzana w tym podrozdziale jest prostym rozszerzeniem tego, co już zrobiliśmy dla problemu optymalizacyjnego z ograniczeniami nierównościowymi. Rozpoczniemy od rozszerzenia :
Niech ,
różniczkowalne w
dla ograniczeń aktywnych
oraz
są różniczkowalne w
dla
. Stożkiem kierunków stycznych dla ograniczeń zlinearyzowanych nazywamy zbiór
![]() |
Podobnie jak poprzednio zauważmy, że stożek kierunków stycznych dla ograniczeń zlinearyzowanych jest zbiorem wielościennym, a zatem wypukłym i domkniętym. Jeśli jest choć jedno ograniczenie równościowe, to ma on puste wnętrze.
Warunek konieczny istnienia rozwiązania lokalnego problemu z ograniczeniami mieszanymi jest sformułowany poniżej. Identycznie jak w twierdzeniu 5.2 zakładamy równość stożka kierunków stycznych dla ograniczeń oryginalnych i zlinearyzowanych. Później uogólnimy warunki regularności, które będą taką równość pociągały.
Niech będzie rozwiązaniem lokalnym (8.1). Jeśli funkcje
,
,
, oraz
,
, są różniczkowalne w
oraz
, to istnieją
oraz
takie że
![]() |
(8.3) |
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
![]() |
(8.4) |
Stosujemy lemat Farkasa, lemat 5.3, z i macierzą
następującej postaci:
![]() |
Istnieje zatem takie że
lub inaczej
![]() |
(8.5) |
Zdefiniujmy ,
. Przypiszmy współrzędnym
odpowiadającym ograniczeniom aktywnym,
, ostatnie
wartości wektora
. Na pozostałych współrzędnych połóżmy zera. Wówczas równość (8.5) jest równoważna następującej
![]() |
Z definicji oczywiste jest, że
.
Sformułujemy teraz trzy warunki dostateczne równości , zwane warunkami regularności.
W punkcie spełniony jest:
warunek liniowej niezależności, jeśli funkcje ,
, są ciągłe w
, pozostałe ograniczenia nierównościowe i wszystkie równościowe są klasy
na otoczeniu
oraz wektory
dla
i
dla
są liniowo niezależne,
warunek afiniczności, jeśli funkcje ,
, oraz
,
, są afiniczne,
warunek Slatera, jeśli
funkcje ,
są pseudowypukłe w
, funkcje
,
, są ciągłe w
,
funkcje ,
, są afiniczne,
istnieje , dla którego
dla
oraz
dla
.
Zaczniemy od najprostszego przypadku.
Jeśli w punkcie spełniony jest warunek afiniczności, to zachodzi równość
.
Postępując jak w przykładzie 8.1 zamieniamy ograniczenia afiniczne równościowe na ograniczenia afiniczne nierównościowe. Teza wynika z twierdzenia 6.1.
∎Jeśli w punkcie spełniony jest warunek Slatera, to zachodzi równość
.
Zapiszmy najpierw funkcje dla
:
![]() |
Wprowadźmy uogólnienie zbioru do przypadku ograniczeń mieszanych:
![]() |
(1) Weźmy punkt
z warunku Slatera. Na mocy pseudowypukłości, patrz uwaga 4.3, mamy
![]() |
Dla każdego mamy także
![]() |
Wnioskujemy więc, że wektor .
(2) . W tym celu weźmy dowolny
. Wystarczy pokazać, że pewien odcinek o końcu
i kierunku
zawiera się w całości w zbiorze
. Rozważmy w tym celu funkcję
Na mocy ciągłości funkcji opisujących ograniczenia nieaktywne istnieje
taki że
dla
oraz
. Z faktu, że
dostajemy również, że
dla
i dowolnego
. Pozostaje tylko zająć się ograniczeniami aktywnymi. Z faktu, że
są różniczkowalne w
dla
mamy
![]() |
gdzie ostatnia nierówność wynika z tego, że . A zatem
dla dostatecznie małych
.
(3) . Zbiory
i
leżą na hiperpłaszczyźnie
wyznaczonej przez afiniczne ograniczenia liniowe. Możemy zatem znaleźć przekształcenie liniowe
o pełnym rzędzie przekształcające tą hiperpłaszczyznę w przestrzeń
, gdzie
jest wymiarem rzeczonej hiperpłaszczyzny (jeśli funkcje
są parami różne, to
). Przekształcenie to jest wzajemnie jednoznaczne rozpatrywane jako funkcja określona na
. A zatem topologie w
i na
są identyczne. Wystarczy więc udowodnić tezę tego podpunktu na obrazach
i
zbiorów
i
. Zauważmy, że zbiór
jest otwarty. Wykazaliśmy, że jest niepusty. Jest również wnętrzem zbioru
. Na mocy lematu 6.1 mamy
.
(4) . Identycznie jak dowód lematu 5.2.
Pozostaje już tylko przypomnieć, że jest zbiorem domkniętym. A zatem
![]() |
Zanim przejdziemy do rozważań nad trzecim warunkiem regularności, warunkiem liniowej niezależności, przypomnijmy twierdzenie o funkcji uwikłanej, by, korzystając z niego, podać opis stożka kierunków stycznych do powierzchni zadanej przez ograniczenia równościowe.
Niech , gdzie
otwarty, będzie odwzorowaniem klasy
. Załóżmy, że
, gdzie
. Przyjmujemy tutaj notację, że
, zaś
. Oznaczmy przez
macierz pochodnych cząstkowych, w punkcie
, względem pierwszych
zmiennych:
zadana jest wzorem
Jeśli macierz jest odwracalna, to istnieje zbiór otwarty
zawierający
oraz funkcja
klasy
, taka że
dla
,
oraz
dla
. Ponadto,
, gdzie
jest pochodną
w punkcie
względem ostatnich
zmiennych:
zadana jest wzorem
Rozważmy powierzchnię opisaną przez układ równań:
![]() |
gdzie otwarty. Przez
oznaczmy stożek kierunków stycznych do
punkcie
.
Załóżmy, że funkcje ,
są klasy
,
, na otoczeniu
oraz gradienty
,
, są liniowo niezależne. Wówczas
![]() |
Ponadto, dla każdego istnieje
i krzywa
klasy
o tej własności, że
oraz
.
Pokażemy najpierw, że . Niech
. Wówczas
dla
,
. Z definicji pochodnej dostajemy dla każdego
:
![]() |
czyli . Stąd wynika, że
.
Pozostało jeszcze zawieranie w drugą stronę. Dowód tej części będzie zdecydowanie trudniejszy. Ustalmy . Skonstruujemy krzywą przechodzącą przez
i zawartą w
, której pochodna w punkcie
jest równa
. Oznaczmy
i zdefiniujmy funkcję
wzorem
![]() |
Zauważmy, że . Oznaczmy przez
macierz pochodnych cząstkowych względem zmiennych wektora
:
W
mamy
. Przypomnijmy, że zgodnie z założeniem macierz
ma maksymalny rząd (równy
), czyli
jest odwracalna. Na mocy twierdzenia o funkcji uwikłanej istnieje zatem
oraz funkcja
klasy
, taka że
. Połóżmy
![]() |
Krzywa ta, zgodnie z konstrukcją, leży na powierzchni , tzn.
dla
oraz
. Różniczkując złożenie
dostajemy
![]() |
czyli w mamy
![]() |
Z drugiej strony wiemy, że , czyli powyższa pochodna jest równa zero:
. Przypomnijmy, że
, co w naszym zapisie oznacza
. Wynika stąd, że
. Korzystając z faktu, że
ma rząd
dostajemy
. Jesteśmy już teraz gotowi, aby dokończyć dowód. Różniczkując funkcję
dostajemy
![]() |
co w daje
. Możemy stąd już łatwo wywnioskować, że
.
Powyższe twierdzenie dowodzi powszechnie znanego faktu dotyczącego przestrzeni stycznej do rozmaitości. Otóż, z założeń wynika, że jest lokalnie wokół punktu
rozmaitością różniczkową klasy
. Przestrzeń styczna do rozmaitości w punkcie
definiowana jest jako zbiór wektorów, które są pochodnymi (w punkcie
) krzywych leżących na tej rozmaitości i przechodzących przez
(jest to równoważne definicji
). Równość
oznacza, że przestrzeń styczna jest jądrem przekształcenia liniowego
.
Z powyższego twierdzenia będziemy wielokrotnie korzystać w następnych rozdziałach. Będzie ono głównym narzędziem przy dowodzeniu warunku koniecznego drugiego rzędu. W tym rozdziale pozwoli łatwo wykazać równość przy założeniu warunku liniowej niezależności.
Jeśli w punkcie spełniony jest warunek liniowej niezależności, to zachodzi równość
.
Ustalmy . Niech
. Na mocy twierdzenia 8.5 istnieje krzywa
, taka że
,
oraz
,
, i
,
Ustalmy
. Połóżmy
,
. Wówczas
, czyli istnieje
, takie że
dla
. Z ciągłości,
na pewnym otoczeniu
dla
. Podsumowując, istnieje
, takie że
dla
. Stąd trywialnie
.
Dowód zawierania jest identyczny do dowodu lematu 5.2.
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.