Zagadnienia

5.1 Stożek kierunków stycznych
5.2 Ograniczenia nierównościowe
5.3 Warunki konieczne Kuhna-Tuckera
5.4 Zadania

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

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}}})$ .
Jeśli ${\bar{\mathbf{x}}}$ jest punktem wewnętrznym zbioru $W$ , to $T({\bar{\mathbf{x}}})=\mathbb{R}^{n}$ .
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

$W=\{(x_{1},x_{2})\in\mathbb{R}^{2}:\ x_{2}\ge-x_{1}^{3}\},$
$W=\{(x_{1},x_{2})\in\mathbb{R}^{2}:\ x_{1}\in\mathbb{Z},\ x_{2}=0\},$
$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.

Optymalizacja II

Zagadnienia

5. Warunek konieczny I rzędu

5.1. Stożek kierunków stycznych

Definicja 5.1

Lemat 5.1

Przykład 5.1

Definicja 5.2

Twierdzenie 5.1

Dowód

Przykład 5.2

5.2. Ograniczenia nierównościowe

Definicja 5.3

Definicja 5.4

Lemat 5.2

Dowód

Przykład 5.3

Przykład 5.4

5.3. Warunki konieczne Kuhna-Tuckera

Lemat 5.3 (Farkas (1901))

Dowód

Twierdzenie 5.2 (Twierdzenie Kuhna-Tuckera)

Dowód twierdzenia 5.2

Uwaga 5.1

Definicja 5.5

5.4. Zadania

Ćwiczenie 5.1

Ćwiczenie 5.2

Ćwiczenie 5.3

Ćwiczenie 5.4

Ćwiczenie 5.5