Zagadnienia

6.1 Warunki regularności
6.2 Przykłady
6.3 Zadania

6. Warunki regularności i przykłady

W tym rozdziale podamy warunki dostateczne równości stożka kierunków stycznych $T({\bar{\mathbf{x}}})$ i stożka kierunków stycznych dla ograniczeń zlinearyzowanych $T_{{lin}}({\bar{\mathbf{x}}})$ . 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).

6.1. Warunki regularności

Sformułujemy teraz trzy warunki dostateczne równości $T({\bar{\mathbf{x}}})=T_{{lin}}({\bar{\mathbf{x}}})$ , zwane warunkami regularności. Dowody dostateczności podamy w kolejnych twierdzeniach.

Definicja 6.1

W punkcie ${\bar{\mathbf{x}}}\in W$ spełniony jest:

warunek liniowej niezależności, jeśli funkcje $g_{i}$ , $i\notin I({\bar{\mathbf{x}}})$ , są ciągłe w ${\bar{\mathbf{x}}}$ oraz wektory $Dg_{i}({\bar{\mathbf{x}}})$ , dla $i\in I({\bar{\mathbf{x}}})$ , są liniowo niezależne,
warunek afiniczności, jeśli funkcje $g_{i}$ , $i\in I({\bar{\mathbf{x}}})$ , są afiniczne oraz funkcje $g_{i}$ , $i\notin I({\bar{\mathbf{x}}})$ , są ciągłe w ${\bar{\mathbf{x}}}$ ,
warunek Slatera, jeśli funkcje $g_{i}$ , $i\in I({\bar{\mathbf{x}}})$ są pseudowypukłe w ${\bar{\mathbf{x}}}$ , funkcje $g_{i}$ , $i\notin I({\bar{\mathbf{x}}})$ , są ciągłe w ${\bar{\mathbf{x}}}$ oraz istnieje $\mathbf{x}\in\mathbb{X}$ , dla którego $g_{i}(\mathbf{x})<0$ dla $i\in I({\bar{\mathbf{x}}})$ .

Zauważmy, że w warunku Slatera nie wymagamy, aby punkt $\mathbf{x}$ spełniał warunki ograniczeń nieaktywnych, tzn. $\mathbf{x}$ nie musi być w zbiorze $W$ .

Twierdzenie 6.1

Jeśli w punkcie ${\bar{\mathbf{x}}}\in W$ spełniony jest warunek afiniczności, to $T({\bar{\mathbf{x}}})=T_{{lin}}({\bar{\mathbf{x}}})$ .

Dowód

Zawieranie $T({\bar{\mathbf{x}}})\subset T_{{lin}}({\bar{\mathbf{x}}})$ wynika z lematu 5.2. Wystarczy zatem wykazać zawieranie w drugą stronę.

Niech $\mathbf{d}\in T_{{lin}}({\bar{\mathbf{x}}})$ . Udowodnimy, że istnieje $\lambda^{*}>0$ , taka że cały odcinek ${\bar{\mathbf{x}}}+\lambda\mathbf{d}$ , $\lambda\in[0,\lambda^{*}]$ , zawarty jest w $W$ :

$\big\{{\bar{\mathbf{x}}}+\lambda\mathbf{d}:\lambda\in[0,\lambda^{*})\big\}\subset W.$

(6.1)

Zauważmy, że $g_{i}({\bar{\mathbf{x}}})<0$ dla $i\notin I({\bar{\mathbf{x}}})$ . Z ciągłości tych funkcji w ${\bar{\mathbf{x}}}$ wynika, że istnieje $\lambda^{*}>0$ , dla której $g_{i}({\bar{\mathbf{x}}}+\lambda\mathbf{d})\le 0$ , $i\notin I({\bar{\mathbf{x}}})$ , $\lambda\in[0,\lambda^{*}]$ . Pozostaje jeszcze wykazać, że nierówność taka zachodzi dla ograniczeń aktywnych. Ustalmy $i\in I({\bar{\mathbf{x}}})$ . Z definicji $\mathbf{d}$ wiemy, że $Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}\le 0$ . Ograniczenie $g_{i}$ jest afiniczne, czyli postaci $g_{i}(\mathbf{x})=\mathbf{a}_{i}^{T}\mathbf{x}+b_{i}$ , gdzie $\mathbf{a}_{i}\in\mathbb{R}^{n}$ , $b_{i}\in\mathbb{R}$ . Zatem $Dg_{i}({\bar{\mathbf{x}}})d=\mathbf{a}_{i}^{T}\mathbf{d}$ . Z faktu, że $g_{i}$ jest aktywne w ${\bar{\mathbf{x}}}$ dostajemy również $0=g_{i}({\bar{\mathbf{x}}})=\mathbf{a}_{i}^{T}{\bar{\mathbf{x}}}+b_{i}$ . Stąd dla dowolnego $\lambda\ge 0$ mamy

$0\ge\lambda\mathbf{a}_{i}^{T}\mathbf{d}=\lambda\mathbf{a}_{i}^{T}\mathbf{d}+\underset{0}{\underbrace{\mathbf{a}_{i}^{T}{\bar{\mathbf{x}}}+b_{i}}}=\mathbf{a}_{i}^{T}({\bar{\mathbf{x}}}+\lambda\mathbf{d})+b_{i}=g_{i}({\bar{\mathbf{x}}}+\lambda\mathbf{d}).$

Dowodzi to (6.1).

Pozostaje już tylko skonstruować ciąg $(\mathbf{x}_{k})\subset W$ , $\mathbf{x}_{k}\to{\bar{\mathbf{x}}}$ i $(\lambda _{k})\subset(0,\infty)$ . Kładziemy

$\mathbf{x}_{k}={\bar{\mathbf{x}}}+\frac{\lambda^{*}}{k}\mathbf{d},\qquad\lambda _{k}=\frac{k}{\lambda^{*}}.$

Wówczas $\mathbf{x}_{k}\in W$ , $\mathbf{x}_{k}\to\mathbf{x}$ oraz $\lambda _{k}(\mathbf{x}_{k}-\mathbf{x})=\mathbf{d}$ , czyli trywialnie

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

a zatem $\mathbf{d}\in T({\bar{\mathbf{x}}})$ .

∎

Przed przystąpieniem do dowodu analogicznych twierdzeń dla pozostałych warunków regularności sformułujemy pomocniczy lemat. Wprowadźmy zbiór

$T_{{int}}({\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}<0\big\}.$

Uwaga 6.1

Zauważmy, że jeśli w punkcie ${\bar{\mathbf{x}}}\in W$ funkcje $g_{i}$ , $i\in I({\bar{\mathbf{x}}})$ , są różniczkowalne w ${\bar{\mathbf{x}}}$ , zaś funkcje $g_{i}$ , $i\notin I({\bar{\mathbf{x}}})$ są ciągłe w ${\bar{\mathbf{x}}}$ , to $\mathbf{d}\in T_{{int}}({\bar{\mathbf{x}}})$ oznacza, że ${\bar{\mathbf{x}}}+\lambda\mathbf{d}\in\mathop{\rm int}W$ dla dostatecznie małych $\lambda>0$ .

Lemat 6.1

Niech ${\bar{\mathbf{x}}}\in W$ oraz funkcje $g_{i}$ , $i\in I({\bar{\mathbf{x}}})$ , są różniczkowalne w ${\bar{\mathbf{x}}}$ , zaś funkcje $g_{i}$ , $i\notin I({\bar{\mathbf{x}}})$ są ciągłe w ${\bar{\mathbf{x}}}$ . Wówczas

I) $T_{{int}}({\bar{\mathbf{x}}})\subset T({\bar{\mathbf{x}}})$ ,
II) Jeśli $T_{{int}}({\bar{\mathbf{x}}})\ne\emptyset$ , to $\mathop{\rm cl}(T_{{int}}({\bar{\mathbf{x}}}))=T_{{lin}}({\bar{\mathbf{x}}})$ .

Dowód

Dowód (I) zostawiamy jako ćwiczenie. Do dowodu (II) zauważmy, że $T_{{int}}({\bar{\mathbf{x}}})$ jest wnętrzem zbioru $T_{{lin}}({\bar{\mathbf{x}}})$ . Ponadto $T_{{lin}}({\bar{\mathbf{x}}})$ jest zbiorem wielościennym, a zatem wypukłym (patrz lemat 4.5). Zastosowanie lematu 3.2 kończy dowód.

∎

Twierdzenie 6.2

Jeśli w punkcie ${\bar{\mathbf{x}}}\in W$ spełniony jest warunek Slatera, to $T({\bar{\mathbf{x}}})=T_{{lin}}({\bar{\mathbf{x}}})$ .

Dowód

Pokażemy najpierw, że $T_{{int}}({\bar{\mathbf{x}}})\ne\emptyset$ . Niech $\mathbf{x}\in\mathbb{X}$ taki że $g_{i}(\mathbf{x})<0$ dla $i\in I({\bar{\mathbf{x}}})$ . Z pseudowypukłości $g_{i}$ w punkcie ${\bar{\mathbf{x}}}$ dostajemy $Dg_{i}({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})<0$ dla $i\in I({\bar{\mathbf{x}}})$ , czyli $(\mathbf{x}-{\bar{\mathbf{x}}})\in T_{{int}}({\bar{\mathbf{x}}})$ .

Na mocy lematu 6.1 mamy $T_{{lin}}({\bar{\mathbf{x}}})=\mathop{\rm cl}(T_{{int}}({\bar{\mathbf{x}}}))$ . Udowodniliśmy także, że $T_{{int}}({\bar{\mathbf{x}}})\subset T({\bar{\mathbf{x}}})\subset T_{{lin}}({\bar{\mathbf{x}}})$ oraz, że $T({\bar{\mathbf{x}}})$ jest domknięty. A zatem $T_{{lin}}({\bar{\mathbf{x}}})=T({\bar{\mathbf{x}}})$ .

∎

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.

Lemat 6.2 (Gordan, 1873)

Niech $A$ będzie macierzą $m\times n$ . Wówczas dokładnie jeden z układów ma rozwiązanie:

$\text{(1)}\ \begin{cases}A\mathbf{x}<\mathbf{0},&\\ \mathbf{x}\in\mathbb{R}^{n},&\end{cases}\qquad\text{(2)}\ \begin{cases}A^{T}\mathbf{y}=\mathbf{0},&\\ \mathbf{y}\ge\mathbf{0},\ \mathbf{y}\ne\mathbf{0}&\\ \mathbf{y}\in\mathbb{R}^{m}.&\end{cases}$

Dowód

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ą $\mathbf{x},\mathbf{y}$ spełniające (1)-(2). Z faktu, że $\mathbf{y}$ rozwiązuje (2), dostajemy, że $y^{T}A\mathbf{x}=0$ . Z drugiej strony $\mathbf{x}$ rozwiązuje (1), czyli $(Ax)_{i}<0$ dla każdego $i=1,\ldots,n$ . Pamiętając, że $y_{j}\ge 0$ , $j=1,\ldots,m$ , i $\mathbf{y}\ne\mathbf{0}$ mamy $\mathbf{y}^{T}A\mathbf{x}<0$ . 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:

$U=(-\infty,0)^{m},\qquad V=\{\mathbf{z}\in\mathbb{R}^{m}:\ \mathbf{z}=A\mathbf{x}\text{ dla pewnego $\mathbf{x}\in\mathbb{R}^{n}$}\}.$

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 $\mathbf{a}\in\mathbb{R}^{m}$ , $\mathbf{a}\ne\mathbf{0}$ , takiego że

$\sup _{{\mathbf{z}\in U}}\mathbf{a}^{T}\mathbf{z}\le\inf _{{\mathbf{z}\in V}}\mathbf{a}^{T}\mathbf{z}.$

Wykażemy, że $\mathbf{a}\ge\mathbf{0}$ . Przypuśćmy przeciwnie, że istnieje współrzędna $a_{i}<0$ . Rozważmy ciąg $\mathbf{z}_{n}=[-\frac{1}{n},-\frac{1}{n},\ldots,-n,\ldots,-\frac{1}{n}]^{T}$ , gdzie $(-n)$ jest na $i$ -tej pozycji. Wówczas $\mathbf{z}_{n}\in U$ oraz $\lim _{{n\to\infty}}\mathbf{a}^{T}\mathbf{z}_{n}=\infty$ , a zatem dostaliśmy sprzeczność, gdyż $\sup _{{\mathbf{z}\in U}}\mathbf{a}^{T}\mathbf{z}$ jest skończone.

Wiemy zatem, że wektor $\mathbf{a}$ ma wszystkie współrzędne nieujemne. Pociąga to $\sup _{{\mathbf{z}\in U}}\mathbf{a}^{T}\mathbf{z}=0$ . Weźmy $\mathbf{z}=A(-A^{T}\mathbf{a})$ . Wówczas $\mathbf{z}\in V$ , czyli $\mathbf{a}^{T}\mathbf{z}\ge 0$ . A zatem

$0\le\mathbf{a}^{T}\mathbf{z}=\mathbf{a}^{T}A(-A^{T}\mathbf{a})=-\| A^{T}\mathbf{a}\|^{2},$

co implikuje, że $\| A^{T}\mathbf{a}\|=0$ , czyli $A^{T}\mathbf{a}=\mathbf{0}$ . Rozwiązaniem układu (2) jest zatem $\mathbf{y}=\mathbf{a}$ .

∎

Twierdzenie 6.3

Jeśli w punkcie ${\bar{\mathbf{x}}}\in W$ spełniony jest warunek liniowej niezależności, to $T({\bar{\mathbf{x}}})=T_{{lin}}({\bar{\mathbf{x}}})$ .

Dowód

Identycznie jak w dowodzie tw. 6.2 wystarczy pokazać, że $T_{{int}}({\bar{\mathbf{x}}})\ne\emptyset$ . Niech $A$ będzie macierzą składającą się z gradientów $Dg_{i}({\bar{\mathbf{x}}})$ ograniczeń aktywnych (jako rzędów). Na mocy liniowej niezależności nie istnieje wektor $\mu\in\mathbb{R}^{{|I({\bar{\mathbf{x}}})|}}$ , $\mu\ne\mathbf{0}$ , o tej własności, że $A^{T}\mu=\mathbf{0}$ . Nie istnieje więc rozwiązanie układu (2) w lemacie 6.2. A zatem ma rozwiązanie układ (1), czyli istnieje $\mathbf{d}\in\mathbb{R}^{n}$ , takie że $A\mathbf{d}<\mathbf{0}$ :

$Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}<0,\qquad\forall\ i\in I({\bar{\mathbf{x}}}).$

Stąd $\mathbf{d}\in T_{{int}}({\bar{\mathbf{x}}})$ .

∎

6.2. Przykłady

Przykład 6.1

Rozważmy problem optymalizacji na zbiorze:

$W=\big\{\mathbf{x}\in\mathbb{R}^{2}:\ x_{1}^{2}+x_{2}^{2}\le 1,\quad x_{1}+2x_{2}\le 1,\quad x_{1}-3x_{2}\le 1\big\}.$

Zbiór $\mathbb{X}=\mathbb{R}^{2}$ . Ograniczenia są opisane przez trójkę funkcji

$g_{1}(x_{1},x_{2})=x_{1}^{2}+x_{2}^{2}-1,\qquad g_{2}(x_{1},x_{2})=x_{1}+2x_{2}-1,\qquad g_{3}(x_{1},x_{2})=x_{1}-3x_{2}-1.$

W punkcie ${\bar{\mathbf{x}}}=[1,0]^{T}$ wszystkie ograniczenia są aktywne i mamy

$Dg_{1}({\bar{\mathbf{x}}})=[2,0],\qquad Dg_{2}({\bar{\mathbf{x}}})=[1,2],\qquad Dg_{3}({\bar{\mathbf{x}}})=[1,-3].$

Warunek liniowej niezależności ograniczeń nie jest spełniony w ${\bar{\mathbf{x}}}$ . 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 $\mathbf{x}=[0,0]^{T}$ mamy $g_{i}(\mathbf{x})=-1<0$ dla $i=1,2,3$ . Zachodzi więc warunek Slatera.

Przykład 6.2 (Kuhn, Tucker (1951))

Rozważmy zadanie optymalizacyjne:

$\begin{cases}x_{1}\to\min,&\\ x_{2}\le x_{1}^{3},&\\ x_{2}\ge 0,&\end{cases}$

Rys. 6.1. Zbiór punktów dopuszczalnych dla przykładu Kuhna-Tuckera.

Zbiór punktów dopuszczalnych $W$ naszkicowany jest na rysunku 6.1. Zapiszmy funkcje opisujące ograniczenia:

$g_{1}(x_{1},x_{2})=-x_{1}^{3}+x_{2},\qquad g_{2}(x_{1},x_{2})=-x_{2}.$

Zauważmy, że w każdym punkcie dopuszczalnym, poza $[0,0]^{T}$ , spełniony jest warunek liniowej niezależności. Widać jednak, że rozwiązaniem powyższego problemu optymalizacyjnego jest ${\bar{\mathbf{x}}}=[0,0]^{T}$ . Niestety w tym punkcie $T({\bar{\mathbf{x}}})\ne T_{{lin}}({\bar{\mathbf{x}}})$ :

$T({\bar{\mathbf{x}}})=\big\{\mathbf{d}\in\mathbb{R}^{2}:\ d_{1}\ge 0,\quad d_{2}=0\big\},\qquad T_{{lin}}({\bar{\mathbf{x}}})=\big\{\mathbf{d}\in\mathbb{R}^{2}:\ d_{2}=0\big\}.$

Przykład 6.3

Niech $A$ będzie macierzą symetryczną $n\times n$ . Rozważmy zadanie optymalizacyjne:

$\begin{cases}\mathbf{x}^{T}A\mathbf{x}\to\max,&\\ \|\mathbf{x}\|\le 1,&\\ \mathbf{x}\in\mathbb{R}^{n}.&\end{cases}$

Zapiszmy najpierw problem optymalizacyjny w kanonicznej formie. Zauważmy przy tym, że warunek $\|\mathbf{x}\|\le 1$ jest równoważny $\|\mathbf{x}\|^{2}=\mathbf{x}^{T}\mathbf{x}\le 1$ .

$\begin{cases}-\mathbf{x}^{T}A\mathbf{x}\to\min,&\\ \mathbf{x}^{T}\mathbf{x}-1\le 0,&\\ \mathbf{x}\in\mathbb{R}^{n}.&\end{cases}$

Oznaczmy przez $W$ 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ć:

$\begin{cases}-2\mathbf{x}^{T}A+2\mu\mathbf{x}^{T}=\mathbf{0}^{T},&\\ \mu(\mathbf{x}^{T}\mathbf{x}-1)=0,&\\ \mu\ge 0,\quad x\in\mathbb{R}^{n}.&\end{cases}$

Przypadek $\mathbf{x}^{T}\mathbf{x}-1<0$ . Wówczas $\mu=0$ (z powodu drugiego równania) i pierwsze równanie przyjmuje postać $\mathbf{x}^{T}A=\mathbf{0}^{T}$ , którą poprzez transponowanie obu stron sprowadzamy do

$A\mathbf{x}=\mathbf{0}.$

Równanie to spełnione jest przez wszystkie $\mathbf{x}\in\ker A$ , $\| x\|<1$ . W szczególności ma ono co najmniej jedno rozwiązanie ( $\mathbf{x}=\mathbf{0}$ ).

Przypadek $\mathbf{x}^{T}\mathbf{x}-1=0$ . Teraz nic nie możemy powiedzieć o $\mu$ . Może być zerowe lub dodatnie. Pierwsze równanie przyjmuje jednak postać $\mu\mathbf{x}^{T}=\mathbf{x}^{T}A$ , które po stransponowaniu wygląda następująco:

$\mu\mathbf{x}=A\mathbf{x}.$

Rozwiązaniami są zatem wektory własne ( $\mathbf{x}$ ) odpowiadające nieujemnym wartościom własnym ( $\mu$ ). 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ć:

$\big\{\mathbf{x}\in\ker A:\ \| x\|<1\big\}\\ \cup\big\{\mathbf{x}\in\mathbb{R}^{2}:\ \text{$\| x\|=1$ oraz $\mathbf{x}$ jest wektorem własnym $A$ dla nieujemnej wartości własnej}\big\}.$

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 $\mathbf{x}\in\ker A$ , to wartość funkcji celu $\mathbf{x}^{T}A\mathbf{x}$ 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 $A$ nie ma wartości własnych większych od zera, to rozwiązaniem jest dowolny punkt z jądra $A$ o normie nie większej niż $1$ .

6.3. Zadania

Ćwiczenie 6.1

Uzasadnij prawdziwość stwierdzenia umieszczonego w uwadze 6.1, by później udowodnić, że $T_{{int}}({\bar{\mathbf{x}}})\subset T({\bar{\mathbf{x}}})$ , gdzie $T_{{int}}({\bar{\mathbf{x}}})$ zdefiniowane jest w lemacie 6.1.

Ćwiczenie 6.2

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:

$\begin{cases}x^{2}-6x+y^{2}+2y\to\min,&\\ x+2y-10=0,&\\ 25-x^{2}-y^{2}\ge 0.&\end{cases}$

Czy w którymś z nich jest rozwiązanie? Jeśli tak, to w którym? Odpowiedź uzasadnij.

Ćwiczenie 6.3

Znajdź zbiór rozwiązań problemu optymalizacyjnego

$\begin{cases}\sum _{{i=1}}^{n}c_{i}x_{i}^{2}\to\min,&\\ \sum _{{i=1}}^{n}x_{i}=b,&\end{cases}$

gdzie $b,(c_{i})>0$ . Uzasadnij, że są to wszystkie rozwiązania.

Ćwiczenie 6.4

Znajdź rozwiązania globalne problemu optymalizacyjnego

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

Ćwiczenie 6.5

Znajdź minima i maksima globalne funkcji

$f(x_{1},x_{2})=4x_{1}^{2}+2x_{2}^{2}-6x_{1}x_{2}+x_{1}$

na zbiorze

$W=\big\{(x_{1},x_{2})\in\mathbb{R}^{2}:\ -2x_{1}+2x_{2}\ge 1,\ 2x_{1}-x_{2}\le 0,\ x_{1}\le 0,\ x_{2}\ge 0\big\}.$

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Optymalizacja II

Zagadnienia

6. Warunki regularności i przykłady

6.1. Warunki regularności

Definicja 6.1

Twierdzenie 6.1

Dowód

Uwaga 6.1

Lemat 6.1

Dowód

Twierdzenie 6.2

Dowód

Lemat 6.2 (Gordan, 1873)

Dowód

Twierdzenie 6.3

Dowód

6.2. Przykłady

Przykład 6.1

Przykład 6.2 (Kuhn, Tucker (1951))

Przykład 6.3

6.3. Zadania

Ćwiczenie 6.1

Ćwiczenie 6.2

Ćwiczenie 6.3

Ćwiczenie 6.4

Ćwiczenie 6.5