Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Optymalizacja II – 5. Warunek konieczny I rzędu – MIM UW

Zagadnienia

5. Warunek konieczny I rzędu

5.1. Stożek kierunków stycznych

Rozważmy problem optymalizacyjny

\begin{cases}f(\mathbf{x})\to\min,&\\
\mathbf{x}\in W,\end{cases} (5.1)

gdzie W\subset\mathbb{R}^{n} i f:W\to\mathbb{R}. Niech {\bar{\mathbf{x}}} będzie rozwiązaniem lokalnym. Będziemy chcieli powiązać geometrię lokalną zbioru W w punkcie {\bar{\mathbf{x}}} z zachowaniem funkcji f, czyli kierunkami spadku jej wartości. Przez lokalną geometrię W rozumiemy zbiór kierunków, w których możemy się poruszyć z punktu {\bar{\mathbf{x}}} nie opuszczając W.

Definicja 5.1

Stożkiem kierunków stycznych T({\bar{\mathbf{x}}}) do W w punkcie {\bar{\mathbf{x}}}\in\mathop{\rm cl}W nazywamy zbiór wektorów \mathbf{d}\in\mathbb{R}^{n} takich że

\mathbf{d}=\lim _{{k\to\infty}}\lambda _{k}(\mathbf{x}_{k}-{\bar{\mathbf{x}}})

dla pewnych \lambda _{k}>0, \mathbf{x}_{k}\in W i \mathbf{x}_{k}\to{\bar{\mathbf{x}}}.

Powyższa definicja mówi, iż kierunek \mathbf{d} należy do stożka kierunków stycznych T({\bar{\mathbf{x}}}), jeśli jest on granicą kierunków wyznaczonych przez ciąg punktów dopuszczalnych (\mathbf{x}_{k}) zmierzających to {\bar{\mathbf{x}}}. Zapisać możemy to formalnie w następujący sposób:

T({\bar{\mathbf{x}}})=\Big\{\mathbf{d}\in\mathbb{R}^{n}:\  d=\lambda\lim _{{k\to\infty}}\frac{\mathbf{x}_{k}-{\bar{\mathbf{x}}}}{\|\mathbf{x}_{k}-{\bar{\mathbf{x}}}\|}\text{ dla pewnych $\lambda\ge 0$, $(\mathbf{x}_{k})\subset W$ oraz $\mathbf{x}_{k}\to{\bar{\mathbf{x}}}$, $\mathbf{x}_{k}\ne{\bar{\mathbf{x}}}$}\Big\}. (5.2)

Dowód tej tożsamości oraz poniższego lematu pozostawiamy jako ćwiczenie.

Lemat 5.1

  1. Zbiór T({\bar{\mathbf{x}}}) jest stożkiem, tzn. \lambda\mathbf{d}\in T({\bar{\mathbf{x}}}) dla dowolnych \mathbf{d}\in T({\bar{\mathbf{x}}}) i \lambda\ge 0. W szczególności, \mathbf{0}\in T({\bar{\mathbf{x}}}).

  2. Jeśli {\bar{\mathbf{x}}} jest punktem wewnętrznym zbioru W, to T({\bar{\mathbf{x}}})=\mathbb{R}^{n}.

  3. Stożek T({\bar{\mathbf{x}}}) jest domknięty.

Przykład 5.1
Rys. 5.1. Stożki styczne zaczepione w punkcie styczności.

Na rysunku 5.1 znajdują się trzy przykłady zbiorów i stożków do nich stycznych w punkcie {\bar{\mathbf{x}}}. Stożki te są przesunięte o wektor {\bar{\mathbf{x}}}, by pokazać ich zależność od kształtu zbioru. W przykładzie (a) i (c) zakładamy, że brzeg zbioru W jest gładki, więc stożki te są półprzestrzeniami ograniczonymi przez styczną w {\bar{\mathbf{x}}}. W przykładzie (b) zbiór W to środek narysowanego stożka (bez brzegu). Wówczas stożek kierunków stycznych jest domknięciem zbioru W.

Jak już wspomnieliśmy, stożek kierunków stycznych jest ściśle związany z rozwiązaniem zagadnienia (5.1). Jeśli w punkcie {\bar{\mathbf{x}}}\in W funkcja f ma minimum lokalne na W, to wówczas kierunki spadku wartości funkcji f nie mogą należeć do zbioru kierunków stycznych w punkcie {\bar{\mathbf{x}}}. Gdyby tak nie było, to poruszając się w kierunku spadku funkcji f zmniejszalibyśmy jej wartość jednocześnie pozostając w zbiorze W. Intuicje te formalizujemy poniżej.

Definicja 5.2

Niech f:\mathbb{X}\to\mathbb{R} będzie różniczkowalna w {\bar{\mathbf{x}}}\in\mathbb{X}. Zbiorem kierunków spadku funkcji f w punkcie {\bar{\mathbf{x}}} nazywamy

D({\bar{\mathbf{x}}})=\{\mathbf{d}\in\mathbb{R}^{n}:Df({\bar{\mathbf{x}}})\,\mathbf{d}<0\}.
Twierdzenie 5.1

Niech {\bar{\mathbf{x}}} będzie rozwiązaniem lokalnym problemu (5.1). Jeśli f jest różniczkowalna w {\bar{\mathbf{x}}}, to

D({\bar{\mathbf{x}}})\cap T({\bar{\mathbf{x}}})=\emptyset.
Dowód

Weźmy \mathbf{d}\in T({\bar{\mathbf{x}}}). Wówczas \mathbf{d}=\lim _{{k\to\infty}}\lambda _{k}(\mathbf{x}_{k}-{\bar{\mathbf{x}}}) dla pewnego ciągu punktów (\mathbf{x}_{k})\subset W zbieżnego do {\bar{\mathbf{x}}} oraz ciągu liczb (\lambda _{k})\subset(0,\infty). Z definicji różniczkowalności f w {\bar{\mathbf{x}}} mamy

f(\mathbf{x}_{k})=f({\bar{\mathbf{x}}})+Df({\bar{\mathbf{x}}})(\mathbf{x}_{k}-{\bar{\mathbf{x}}})+o(\|\mathbf{x}_{k}-{\bar{\mathbf{x}}}\|).

Z faktu, że {\bar{\mathbf{x}}} jest rozwiązaniem lokalnym f(\mathbf{x}_{k})\ge f({\bar{\mathbf{x}}}) dla dostatecznie dużych k. W połączeniu z powyższym wzorem daje to następujące oszacowanie:

0\le f(\mathbf{x}_{k})-f({\bar{\mathbf{x}}})=Df({\bar{\mathbf{x}}})(\mathbf{x}_{k}-{\bar{\mathbf{x}}})+o(\| x_{k}-{\bar{\mathbf{x}}}\|).

Mnożąc obie strony powyższej nierówności przez \lambda _{k} dostajemy

0\le Df({\bar{\mathbf{x}}})\big(\lambda _{k}(\mathbf{x}_{k}-{\bar{\mathbf{x}}})\big)+\lambda _{k}o(\| x_{k}-{\bar{\mathbf{x}}}\|).

Zrobimy teraz sztuczkę, aby rozwiązać problem z o(\| x_{k}-{\bar{\mathbf{x}}}\|) i przejdziemy z k to nieskończoności:

0\le Df({\bar{\mathbf{x}}})\underset{\to\mathbf{d}}{\underbrace{\big(\lambda _{k}(\mathbf{x}_{k}-{\bar{\mathbf{x}}})\big)}}+\underset{\to\|\mathbf{d}\|}{\underbrace{\lambda _{k}\| x_{k}-{\bar{\mathbf{x}}}\|}}\underset{\to 0}{\underbrace{\frac{o(\| x_{k}-{\bar{\mathbf{x}}}\|)}{\| x_{k}-{\bar{\mathbf{x}}}\|}}}.

Udowodniliśmy zatem, że Df({\bar{\mathbf{x}}})\mathbf{d}\ge 0, czyli \mathbf{d}\notin D({\bar{\mathbf{x}}}). Kończy to dowód twierdzenia.

Przykład 5.2

Rozważmy następujący problem optymalizacyjny:

\begin{cases}x_{1}^{2}+x_{2}^{2}\to\min,&\\
x_{1}+x_{2}\ge 1.&\end{cases}

Oznaczmy f(x_{1},x_{2})=x_{1}^{2}+x_{2}^{2} i W=\{\mathbf{x}\in\mathbb{R}^{2}:\  x_{1}+x_{2}\ge 1\}. Zbadamy zbiory T({\bar{\mathbf{x}}}) i D({\bar{\mathbf{x}}}) w następujących punktach: [1,1]^{T},[1,0]^{T},[\frac{1}{2},\frac{1}{2}]^{T}.

  • {\bar{\mathbf{x}}}=[1,1]^{T}. Punkt ten leży wewnątrz zbioru W, czyli T({\bar{\mathbf{x}}})=\mathbb{R}^{2}. Zbiór kierunków spadku funkcji f dany jest następująco:

    D({\bar{\mathbf{x}}})=\big\{\mathbf{d}\in\mathbb{R}^{2}:\  Df({\bar{\mathbf{x}}})\mathbf{d}<0\big\}=\big\{\mathbf{d}\in\mathbb{R}^{2}:\ [2,2]\mathbf{d}<0\big\}=\big\{\mathbf{d}\in\mathbb{R}^{2}:\  d_{1}+d_{2}<0\big\}.

    W oczywisty sposób część wspólna powyższych zbiorów nie jest pusta, czyli w punkcie [1,1]^{T} nie ma minimum.

  • {\bar{\mathbf{x}}}=[1,0]^{T}. Punkt ten leży na brzegu zbioru W. Łatwo można zauważyć, że

    T({\bar{\mathbf{x}}})=\big\{\mathbf{d}\in\mathbb{R}^{2}:d_{1}+d_{2}\ge 0\big\},\qquad D({\bar{\mathbf{x}}})=\big\{\mathbf{d}\in\mathbb{R}^{2}:d_{1}<0\big\}.
    Rys. 5.2. Stożek kierunków stycznych i stożek kierunków spadku w punkcie {\bar{\mathbf{x}}}=[1,0]^{T}.

    Zbiory te mają niepuste przecięcie (patrz podwójna kratka na rys. 5.2), więc w punkcie [1,0]^{T} nie ma minimum.

  • {\bar{\mathbf{x}}}=[\frac{1}{2},\frac{1}{2}]^{T}. Zauważmy, że

    T({\bar{\mathbf{x}}})=\big\{\mathbf{d}\in\mathbb{R}^{2}:d_{1}+d_{2}\ge 0\big\},\qquad D({\bar{\mathbf{x}}})=\big\{\mathbf{d}\in\mathbb{R}^{2}:\ [1,1]\mathbf{d}<0\big\}=\big\{\mathbf{d}\in\mathbb{R}^{2}:d_{1}+d_{2}<0\big\}.

    Zbiory te mają zatem puste przecięcie, więc w punkcie [\frac{1}{2},\frac{1}{2}]^{T} 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 T({\bar{\mathbf{x}}}) oraz warunek T({\bar{\mathbf{x}}})\cap D({\bar{\mathbf{x}}})=\emptyset.

5.2. Ograniczenia nierównościowe

Zajmiemy się problemem optymalizacyjnym w następującej formie:

\begin{cases}f(\mathbf{x})\to\min,&\\
g_{i}(\mathbf{x})\le 0,\quad i=1,\ldots,m,&\\
\mathbf{x}\in\mathbb{X},\end{cases} (5.3)

gdzie \mathbb{X}\subset\mathbb{R}^{n} jest zbiorem otwartym i f,g_{1},\ldots,g_{m}:\mathbb{X}\to\mathbb{R}. A zatem

W=\big\{\mathbf{x}\in\mathbb{X}:g_{1}(\mathbf{x})\le 0,\ldots,g_{m}(\mathbf{x})\le 0\big\}. (5.4)

Funkcje g_{i} nazywane są ograniczeniami nierównościowymi, zaś cały problem (5.3) zadaniem optymalizacyjnym z ograniczeniami nierównościowymi.

Ustalmy {\bar{\mathbf{x}}}\in W i załóżmy, że funkcje g_{i} są ciągłe. Wówczas ruch wokół {\bar{\mathbf{x}}} ograniczają lokalnie tylko te warunki, dla których g_{i}({\bar{\mathbf{x}}})=0. W przypadku pozostałych, z ciągłości g_{i} wynika, iż istnieje pewne otoczenie {\bar{\mathbf{x}}}, na którym mamy g_{i}<0. Okazuje się, że ta obserwacja będzie pełnić ważną rolę w procesie optymalizacji z ograniczeniami nierównościowymi.

Definicja 5.3

Zbiorem ograniczeń aktywnych w punkcie {\bar{\mathbf{x}}}\in W nazywamy zbiór

I({\bar{\mathbf{x}}})=\big\{ i\in\{ 1,2,\ldots,m\}:\quad g_{i}({\bar{\mathbf{x}}})=0\big\}.

Głównym wynikiem tego rozdziału będzie powiązanie własności ograniczeń aktywnych w danym punkcie {\bar{\mathbf{x}}}\in W z lokalną geometrią tego zbioru wokół {\bar{\mathbf{x}}}. W tym celu wprowadźmy następującą definicję.

Definicja 5.4

Niech {\bar{\mathbf{x}}}\in W i g_{i} różniczkowalne w {\bar{\mathbf{x}}} dla ograniczeń aktywnych i\in I({\bar{\mathbf{x}}}). Stożkiem kierunków stycznych dla ograniczeń zlinearyzowanych nazywamy zbiór

T_{{lin}}({\bar{\mathbf{x}}})=\big\{\mathbf{d}\in\mathbb{R}^{n}:\ \forall i\in I({\bar{\mathbf{x}}})\quad Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}\le 0\big\}.

Stożek kierunków stycznych dla ograniczeń zlinearyzowanych jest zbiorem wielościennym, a zatem wypukłym i domkniętym.

Lemat 5.2

Jeśli {\bar{\mathbf{x}}}\in W, to

T({\bar{\mathbf{x}}})\subset T_{{lin}}({\bar{\mathbf{x}}}).
Dowód

Dowód przebiega bardzo podobnie do dowodu twierdzenia 5.1. Weźmy \mathbf{d}\in T({\bar{\mathbf{x}}}). Wówczas \mathbf{d}=\lim _{{k\to\infty}}\lambda _{k}(\mathbf{x}_{k}-{\bar{\mathbf{x}}}) dla pewnego ciągu punktów (\mathbf{x}_{k})\subset W zbieżnego do {\bar{\mathbf{x}}} oraz ciągu liczb dodatnich (\lambda _{k}). Ustalmy i\in I({\bar{\mathbf{x}}}). Z definicji różniczkowalności g_{i} w {\bar{\mathbf{x}}} mamy

g_{i}(\mathbf{x}_{k})=g_{i}({\bar{\mathbf{x}}})+Dg_{i}({\bar{\mathbf{x}}})(\mathbf{x}_{k}-{\bar{\mathbf{x}}})+o(\|\mathbf{x}_{k}-{\bar{\mathbf{x}}}\|).

Ograniczenie i-te jest aktywne w {\bar{\mathbf{x}}}. Zatem g_{i}({\bar{\mathbf{x}}})=0. Oczywiście, g_{i}(\mathbf{x}_{k})\le 0, ponieważ \mathbf{x}_{k}\in W. W połączeniu w powyższym wzorem daje to następujące oszacowanie:

0\ge g_{i}(\mathbf{x}_{k})-g_{i}({\bar{\mathbf{x}}})=Dg_{i}({\bar{\mathbf{x}}})(\mathbf{x}_{k}-{\bar{\mathbf{x}}})+o(\| x_{k}-{\bar{\mathbf{x}}}\|).

Mnożąc obie strony powyższej nierówności przez \lambda _{k} dostajemy

0\ge Dg_{i}({\bar{\mathbf{x}}})\big(\lambda _{k}(\mathbf{x}_{k}-{\bar{\mathbf{x}}})\big)+\lambda _{k}o(\| x_{k}-{\bar{\mathbf{x}}}\|).

Zrobimy teraz sztuczkę, aby rozwiązać problem o(\| x_{k}-{\bar{\mathbf{x}}}\|) i przejdziemy z k to nieskończoności:

0\ge Dg_{i}({\bar{\mathbf{x}}})\underset{\to\mathbf{d}}{\underbrace{\big(\lambda _{k}(\mathbf{x}_{k}-{\bar{\mathbf{x}}})\big)}}+\underset{\to\|\mathbf{d}\|}{\underbrace{\lambda _{k}\| x_{k}-{\bar{\mathbf{x}}}\|}}\underset{\to 0}{\underbrace{\frac{o(\| x_{k}-{\bar{\mathbf{x}}}\|)}{\| x_{k}-{\bar{\mathbf{x}}}\|}}}.

Udowodniliśmy zatem, że Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}\le 0. Analogicznie wynik otrzymujemy dla każdego ograniczenia aktywnego i\in I({\bar{\mathbf{x}}}). A zatem \mathbf{d}\in T_{{lin}}({\bar{\mathbf{x}}}).

Przykład 5.3
Rys. 5.3. Zbiór punktów dopuszczalnych (zaznaczony na szaro) z przykładu 5.3.

Rozważmy zbiór W=\{\mathbf{x}\in\mathbb{R}^{2}:\  x_{1}^{2}+x_{2}^{2}\le 1,\  x_{2}\ge 0\}, patrz rysunek 5.3. Zapiszmy go w kanonicznej formie (5.4):

\mathbb{X}=\mathbb{R}^{n},\quad g_{1}(x_{1},x_{2})=x_{1}^{2}+x_{2}^{2},\quad g_{2}(x_{1},x_{2})=-x_{2}.

Zbadajmy trzy punktu tego zbioru (\frac{1}{2},\frac{1}{2}), (0,1) i (1,0).

  • {\bar{\mathbf{x}}}=(\frac{1}{2},\frac{1}{2}): I({\bar{\mathbf{x}}})=\emptyset i T({\bar{\mathbf{x}}})=T_{{lin}}=\mathbb{R}^{n}.

  • {\bar{\mathbf{x}}}=(0,1): I({\bar{\mathbf{x}}})=\{ 1\}, T({\bar{\mathbf{x}}})=\{\mathbf{d}\in\mathbb{R}^{n}:\  d_{2}\le 0\},

    T_{{lin}}({\bar{\mathbf{x}}})=\{\mathbf{d}\in\mathbb{R}^{2}:\  Dg_{1}(0,1)\mathbf{d}\le 0\}=\{\mathbf{d}\in\mathbb{R}^{2}:\ [0,2]\mathbf{d}\le 0\}=T({\bar{\mathbf{x}}}).
  • {\bar{\mathbf{x}}}=(1,0): I({\bar{\mathbf{x}}})=\{ 1,2\}, T({\bar{\mathbf{x}}})=\{\mathbf{d}\in\mathbb{R}^{n}:\  d_{1}\le 0,\  d_{2}\ge 0\},

    \displaystyle T_{{lin}}({\bar{\mathbf{x}}}) \displaystyle=\{\mathbf{d}\in\mathbb{R}^{2}:\  Dg_{1}(1,0)\mathbf{d}\le 0,\  Dg_{2}(1,0)\mathbf{d}\le 0\}
    \displaystyle=\{\mathbf{d}\in\mathbb{R}^{2}:\ [2,0]\mathbf{d}\le 0,\ [0,-1]\mathbf{d}\le 0\}=T({\bar{\mathbf{x}}}).
Przykład 5.4

Rozważmy ten sam zbiór W co w powyższym przykładzie, lecz zapiszmy go nieco inaczej:

W=\{\mathbf{x}\in\mathbb{R}^{2}:\  x_{1}^{2}+x_{2}^{2}\le 1,\  x_{2}^{3}\ge 0\}.

Zmianie uległo drugie ograniczenie: z x_{2}\ge 0 na x_{2}^{3}\ge 0. Nowy opis zbioru W odpowiada ograniczeniom g_{1}(x_{1},x_{2})=x_{1}^{2}+x_{2}^{2}, g_{2}(x_{1},x_{2})=-x_{2}^{3}. Rozważmy zbiory T({\bar{\mathbf{x}}}) i T_{{lin}}({\bar{\mathbf{x}}}) w punkcie {\bar{\mathbf{x}}}=(0,1). Stożek kierunków stycznych jest identyczny, gdyż zbiór się nie zmienił:

T({\bar{\mathbf{x}}})=\{\mathbf{d}\in\mathbb{R}^{n}:\  d_{1}\le 0,\  d_{2}\ge 0\}.

Natomiast stożek kierunków stycznych dla ograniczeń zlinearyzowanych jest następujący:

\displaystyle T_{{lin}}({\bar{\mathbf{x}}}) \displaystyle=\{\mathbf{d}\in\mathbb{R}^{2}:\  Dg_{1}(1,0)\mathbf{d}\le 0,\  Dg_{2}(1,0)\mathbf{d}\le 0\}
\displaystyle=\{\mathbf{d}\in\mathbb{R}^{2}:\ [2,0]\mathbf{d}\le 0,\ [0,0]\mathbf{d}\le 0\}
\displaystyle=\{\mathbf{d}\in\mathbb{R}^{2}:\  d_{1}\le 0\}.

Widzimy zatem, że nie zawsze zachodzi równość pomiędzy T({\bar{\mathbf{x}}}) i T_{{lin}}({\bar{\mathbf{x}}}).

5.3. Warunki konieczne Kuhna-Tuckera

W lemacie 5.2 wykazaliśmy, że T({\bar{\mathbf{x}}})\subset T_{{lin}}({\bar{\mathbf{x}}}). 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.

Lemat 5.3 (Farkas (1901))

Niech A będzie macierzą m\times n i \mathbf{d}\in\mathbb{R}^{n}. Wówczas dokładnie jeden z układów ma rozwiązanie:

\text{(1)}\ \begin{cases}A\mathbf{x}\le\mathbf{0},&\\
\mathbf{d}^{T}\mathbf{x}>0,&\\
\mathbf{x}\in\mathbb{R}^{n},&\end{cases}\qquad\text{(2)}\ \begin{cases}A^{T}\mathbf{y}=\mathbf{d},&\\
\mathbf{y}\ge\mathbf{0},&\\
\mathbf{y}\in\mathbb{R}^{m}.&\end{cases}
Dowód

Pokażemy najpierw, że jeśli układ (2) ma rozwiązanie, to układ (1) go nie ma. Weźmy zatem \mathbf{y} spełniające (2). Zatem \mathbf{d}=A^{T}\mathbf{y}. Wstawiamy to do układu (1) i otrzymujemy

\begin{cases}A\mathbf{x}\le\mathbf{0},&\\
\mathbf{y}^{T}A\mathbf{x}>0.&\end{cases}

Pierwsza nierówność oznacza, że każda współrzędna wektora A\mathbf{x} jest niedodatnia. Ponieważ współrzędne \mathbf{y} są nieujemne, to iloczyn skalarny \mathbf{y}^{T}(A\mathbf{x}) 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

V=\{\mathbf{x}\in\mathbb{R}^{n}:\ \mathbf{x}=A^{T}\mathbf{y}\text{ dla pewnego $\mathbf{y}\in\mathbb{R}^{m}$, $\mathbf{y}\ge 0$}\}.

Łatwo sprawdzić, że jest to zbiór wypukły i domknięty. Z faktu, że układ (2) nie ma rozwiązania wynika, że \mathbf{d}\notin V. Zastosujmy więc mocne twierdzenia o oddzielaniu, tw. 3.2 do zbiorów V i U=\{\mathbf{d}\}. Istnieje więc wektor \mathbf{a}\in\mathbb{R}^{n} taki że

\mathbf{a}^{T}\mathbf{d}>\sup _{{\mathbf{x}\in V}}\mathbf{a}^{T}\mathbf{x}.

Pokażemy, że {\bar{\mathbf{x}}}=\mathbf{a} jest rozwiązaniem układu (1). Oznaczmy \alpha=\sup _{{\mathbf{x}\in V}}{\bar{\mathbf{x}}}^{T}\mathbf{x}. Ponieważ \mathbf{0}\in V, to \alpha\ge 0, co pociąga \mathbf{d}^{T}{\bar{\mathbf{x}}}>0. Pozostaje tylko udowodnić, że A{\bar{\mathbf{x}}}\le\mathbf{0}. Przypuśćmy, że i-ta współrzędna A{\bar{\mathbf{x}}} jest dodatnia. Z definicji zbioru V wynika, że dla dowolnego \mathbf{y}\ge 0 zachodzi \alpha\ge{\bar{\mathbf{x}}}^{T}A^{T}\mathbf{y}=\mathbf{y}^{T}A{\bar{\mathbf{x}}}. Zdefiniujmy ciąg \mathbf{y}_{n}=[0,\ldots,0,n,0,\ldots,0]^{T}, gdzie n jest na i-tej współrzędnej. Na mocy założenia o dodatniości (A{\bar{\mathbf{x}}})_{i} dostajemy

\lim _{{n\to\infty}}\mathbf{y}_{n}^{T}A{\bar{\mathbf{x}}}=\lim _{{n\to\infty}}n(A{\bar{\mathbf{x}}})_{i}=\infty,

co przeczy temu, że \mathbf{y}_{n}^{T}A{\bar{\mathbf{x}}}\le\alpha. Sprzeczność ta dowodzi, że A{\bar{\mathbf{x}}}\le\mathbf{0}.

Twierdzenie 5.2 (Twierdzenie Kuhna-Tuckera)

Niech {\bar{\mathbf{x}}} będzie rozwiązaniem lokalnym (5.3). Jeśli funkcje f oraz g_{i}, i\in I({\bar{\mathbf{x}}}), są różniczkowalne w {\bar{\mathbf{x}}} oraz T({\bar{\mathbf{x}}})=T_{{lin}}({\bar{\mathbf{x}}}), to istnieje \mu\in[0,\infty)^{m}, takie że

\begin{cases}Df({\bar{\mathbf{x}}})+\sum _{{i\in I({\bar{\mathbf{x}}})}}\mu _{i}Dg_{i}({\bar{\mathbf{x}}})=\mathbf{0}^{T},&\\
\mu _{i}g_{i}({\bar{\mathbf{x}}})=0,\quad i=1,2,\ldots,m.&\end{cases} (5.5)

Często tezę powyższego twierdzenia zapisuje się biorąc sumę po wszystkich i=1,\ldots,m:

\begin{cases}Df({\bar{\mathbf{x}}})+\sum _{{i=1}}^{m}\mu _{i}Dg_{i}({\bar{\mathbf{x}}})=\mathbf{0}^{T},&\\
\mu _{i}g_{i}({\bar{\mathbf{x}}})=0,\quad i=1,2,\ldots,m.&\end{cases}

Jest to naginanie notacji, gdyż funkcje opisujące ograniczenia nieaktywne nie muszą być różniczkowalne w punkcie {\bar{\mathbf{x}}}. Z drugiej strony są one mnożone przez zerowe współczynniki \mu _{i}. Jest to pewne usprawiedliwienie powyższej notacji, którą należy rozumieć tak, jak zapisane zostało w twierdzeniu 5.2.

Dowód twierdzenia 5.2

Na mocy twierdzenia 5.1 mamy D({\bar{\mathbf{x}}})\cap T({\bar{\mathbf{x}}})=\emptyset. Dalej, korzystając z założenia, dostajemy D({\bar{\mathbf{x}}})\cap T_{{lin}}({\bar{\mathbf{x}}})=\emptyset, co innymi słowy oznacza, że nie istnieje rozwiązanie \mathbf{z}\in\mathbb{R}^{n} układu

\begin{cases}Df({\bar{\mathbf{x}}})\mathbf{z}<0,&\\
Dg_{i}({\bar{\mathbf{x}}})\mathbf{z}\le 0,\quad i\in I({\bar{\mathbf{x}}}).&\end{cases}

Stosujemy lemat Farkasa z \mathbf{d}=-\big(Df({\bar{\mathbf{x}}})\big)^{T} i macierzą A złożoną wierszowo z gradientów ograniczeń aktywnych Dg_{i}({\bar{\mathbf{x}}}), i\in I({\bar{\mathbf{x}}}). Istnieje zatem \mathbf{y}\in[0,\infty)^{{|I({\bar{\mathbf{x}}})|}} takie że \mathbf{y}^{T}A=-Df({\bar{\mathbf{x}}}) lub inaczej

Df({\bar{\mathbf{x}}})+\mathbf{y}^{T}A=\mathbf{0}^{T}.

Zdefiniujmy \mu\in[0,\infty)^{m} następująco: (\mu _{i})_{{i\in I({\bar{\mathbf{x}}})}}=\mathbf{y} i (\mu _{i})_{{i\notin I({\bar{\mathbf{x}}})}}=0. Wówczas powyższa równość jest równoważna następującej

Df({\bar{\mathbf{x}}})+\sum _{{i\in I({\bar{\mathbf{x}}})}}^{m}\mu _{i}Dg_{i}({\bar{\mathbf{x}}})=\mathbf{0}^{T}.

Z definicji \mu _{i} oczywiste jest, że \mu _{i}g_{i}({\bar{\mathbf{x}}})=0.

Uwaga 5.1

Założenia twierdzenia Kuhna-Tuckera są trywialnie spełnione, gdy {\bar{\mathbf{x}}}\in\mathop{\rm int}W, tzn. gdy I({\bar{\mathbf{x}}})=\emptyset. Wówczas warunki (5.5) sprowadzają się do

Df({\bar{\mathbf{x}}})=\mathbf{0}^{T},\qquad\mu=\mathbf{0}.

Na zakończenie zwróćmy jeszcze raz uwagę na tezę twierdzenia Kuhna-Tuckera. Warunki (5.5) nazywane są warunkami koniecznymi pierwszego rzędu. Wektor \mu będzie pojawiał się jeszcze wiele razy na tym wykładzie. Nadajmy mu zatem nazwę:

Definicja 5.5

Wektor \mu spełniający (5.5) nazywa się wektorem mnożników Lagrange'a w punkcie {\bar{\mathbf{x}}}.

5.4. Zadania

Ćwiczenie 5.1

Wykaż, że zbiór T({\bar{\mathbf{x}}}) dla {\bar{\mathbf{x}}}\in\mathop{\rm cl}W jest stożkiem.

Ćwiczenie 5.2

Udowodnij, że stożek kierunków stycznych T({\bar{\mathbf{x}}}) jest zbiorem domkniętym.

Ćwiczenie 5.3

Udowodnij tożsamość (5.2).

Ćwiczenie 5.4

Znajdź stożek kierunków stycznych do zbioru W w punkcie {\bar{\mathbf{x}}}=\mathbf{0}, gdy

  1. W=\{(x_{1},x_{2})\in\mathbb{R}^{2}:\  x_{2}\ge-x_{1}^{3}\},

  2. W=\{(x_{1},x_{2})\in\mathbb{R}^{2}:\  x_{1}\in\mathbb{Z},\  x_{2}=0\},

  3. W=\{(x_{1},x_{2})\in\mathbb{R}^{2}:\  x_{1}\in\mathbb{Q},\  x_{2}=0\}.

Ćwiczenie 5.5

Udowodnić, że dla zadania

\begin{cases}f(\mathbf{x})\to\min,&\\
g_{i}(\mathbf{x})\le 0,\qquad i=1,\ldots,m,&\\
x_{i}\ge 0,\qquad i=1,\ldots,n,&\end{cases}

warunek konieczny pierwszego rzędu przyjmuje postać:

\begin{cases}Df(\mathbf{x})+\sum _{{i\in I(\mathbf{x})}}\mu _{i}Dg_{i}(\mathbf{x})\ge\mathbf{0}^{T},&\\
\Big(Df(\mathbf{x})+\sum _{{i\in I(\mathbf{x})}}\mu _{i}Dg_{i}(\mathbf{x})\Big)\,\mathbf{x}=0,&\\
\mu _{i}g_{i}(\mathbf{x})=0,\qquad i=1,\ldots,m,&\\
\mu _{i}\ge 0,\qquad i=1,\ldots,m.&\end{cases}

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.

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.