Zagadnienia

14.1 Algorytm Zoutendijk'a dla ograniczeń liniowych
14.2 Algorytm Zoutendijk'a dla ograniczeń nieliniowych
14.3 Modyfikacja Topkis'a-Veinott'a
14.4 Podsumowanie
14.5 Zadania

14. Metody optymalizacji z ograniczeniami

W tym rozdziale skupimy się na metodach numerycznych rozwiązywania problemów optymalizacyjnych z ograniczeniami nierównościowymi. Pokażemy problemy z zastosowaniem metody największego spadku i jej naiwnych modyfikacji oraz zaproponujemy skuteczne aczkolwiek bardziej skomplikowane podejście.

Problem optymalizacyjny na następującą postać:

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

(14.1)

gdzie $f,g_{1},\ldots,g_{m}:\mathbb{R}^{n}\to\mathbb{R}$ . A zatem zbiór punktów dopuszczalnych jest zadany przez

$W=\big\{\mathbf{x}\in\mathbb{R}^{n}:g_{1}(\mathbf{x})\le 0,\ldots,g_{m}(\mathbf{x})\le 0\big\}.$

(14.2)

W rozważaniach tego rozdziału będziemy odwoływać się często do pojęcia zbioru kierunków dopuszczalnych zdefiniowanego następująco

$A(\mathbf{x})=\{\mathbf{d}\in\mathbb{R}^{n}:\ \text{$\mathbf{d}\ne\mathbf{0}$ oraz istnieje $\lambda^{*}>0$ taka że $\mathbf{x}+\lambda\mathbf{d}\in W$ $\ \forall\,\lambda\in[0,\lambda^{*}]$}\}.$

14.1. Algorytm Zoutendijk'a dla ograniczeń liniowych

Rozważmy bardzo prostą modyfikację algorytmu największego spadku. Otóż jeśli punkt znajduje się wewnątrz zbioru $W$ , to istnieje możliwość poruszania się wzdłuż kierunku największego spadku aż do uderzenia w brzeg. Jeśli punkt już jest na brzegu, to naturalne jest wybrać taki kierunek ruchu, by pozwalał on na jak największy spadek wartości funkcji celu a jednocześnie na ruch w jego kierunku. Kierunek taki nazywamy dopuszczalnym kierunkiem spadku w punkcie $\mathbf{x}$ i definiujemy jako kierunek dopuszczalny $\mathbf{d}$ , taki że $Df(\mathbf{x})\mathbf{d}<0.$

Okazuje się, że pomysł ten działa całkiem dobrze, jeśli ograniczenia są liniowe i nosi nazwę algorytm Zoutendijk'a. Przypomnijmy, że liniowość ograniczeń znacznie upraszcza problem, co pozwoli nam na rozszerzenie analizy w tym podrozdziale do zagadnień z ograniczeniami nierównościowymi i równościowymi, tzn.

$\begin{cases}f(\mathbf{x})\to\min,&\\ A\mathbf{x}\le\mathbf{b},&\\ Q\mathbf{x}=\mathbf{a},&\\ \mathbf{x}\in\mathbb{R}^{n}.&\end{cases}$

(14.3)

Tutaj $A$ jest macierzą $m\times n$ , $Q$ jest macierzą $l\times n$ , zaś $\mathbf{b}\in\mathbb{R}^{m}$ i $\mathbf{a}\in\mathbb{R}^{l}.$ Poniższy lemat charakteryzuje zbiór dopuszczalnych kierunków spadku. Jego dowód pozostawiamy jako ćwiczenie.

Lemat 14.1

Niech $\mathbf{x}$ będzie punktem dopuszczalnym dla zagadnienia (14.3) i załóżmy, że macierz $A$ i wektor $\mathbf{b}$ mogą być podzielone w zależności od aktywności ograniczeń na $A_{1}$ , $A_{2}$ i $\mathbf{b}_{1},\mathbf{b}_{2}$ (z dokładnością do przenumerowania ograniczeń), tzn. $A_{1}\mathbf{x}=\mathbf{b}_{1}$ oraz $A_{2}\mathbf{x}<\mathbf{b}_{2}.$ Wektor $\mathbf{d}\in\mathbb{R}^{n}$ jest kierunkiem dopuszczalnym w $\mathbf{x}$ , jeśli $A_{1}\mathbf{d}\le\mathbf{b}_{1}$ oraz $Q\mathbf{d}=\mathbf{0}.$ Jeśli, ponadto, $Df(\mathbf{x})\mathbf{d}<0$ , to $\mathbf{d}$ jest dopuszczalnym kierunkiem spadku.

Jak wybrać najlepszy dopuszczalny kierunek spadku w punkcie $\mathbf{x}$ ? Najprościej byłoby rozwiązać zagadnienie

$Df(\mathbf{x})\mathbf{d}\to\min,\qquad\mathbf{d}\in A(\mathbf{x}),\quad\|\mathbf{d}\|\le 1.$

(14.4)

Ograniczenie na normę wektora $\mathbf{d}$ jest konieczne. Jeśli byśmy je opuścili, to dla dowolnego dopuszczalnego kierunku spadku $\mathbf{d}$ jego wielokrotność $\lambda\mathbf{d}$ , $\lambda>0$ , jest również kierunkiem spadku. Co więcej, $Df(\mathbf{x})\mathbf{d}<0$ , czyli $\lim _{{\lambda\to\infty}}Df(\mathbf{x})\lambda\mathbf{d}=-\infty$ i problem powyższy nie ma jednoznacznego rozwiązania.

Korzystając z lematu 14.1 powyższe zagadnienie (14.4) można wyrazić jako

$\begin{cases}Df(\mathbf{x})\mathbf{d}\to\min,&\\ A_{1}\mathbf{d}\le\mathbf{0},&\\ Q\mathbf{d}=\mathbf{0},&\\ \mathbf{d}^{T}\mathbf{d}\le 1.&\end{cases}$

Zauważmy, że jedyna nieliniowość związana jest z ograniczeniem na normę wektora $\mathbf{d}$ . W praktyce, bez większych strat dla jakości algorytmu, zamienia się ją na ograniczenia liniowe, które pozwalają skorzystać z szybkich metod optymalizacji liniowej (np. algorytmu sympleks – patrz monografie Bazaraa, Jarvis'a, Shetty [2], Gass'a [8] lub Luenberger'a [9]). Najpopularniejsze są następujące dwa zamienniki normy euklidesowej $\|\mathbf{d}\|$ :

norma $l^{\infty}$ , tzn. $\sup _{{i}}|d_{i}|\le 1$ , co zapisuje się jako

$-1\le d_{i}\le 1,\qquad i=1,\ldots,n.$
norma $l^{1}$ , tzn. $\sum _{{i}}|d_{i}|\le 1$ , co zapisuje się jako

$\begin{cases}\sum _{{i=1}}^{n}\eta _{i}\le 1,&\\ -\eta _{i}\le d_{i}\le\eta _{i},\qquad i=1,\ldots,n,&\end{cases}$

gdzie $\eta _{1},\ldots,\eta _{n}$ są nowymi zmiennymi (pomocniczymi).

Oto pełny algorytm:

Inicjalizacja: Wybierz punkt początkowy $\mathbf{x}_{0}$ .
Krok $k$ -ty:
1. Wybierz kierunek ruchu $\mathbf{d}_{k}$ jako rozwiązanie problemu optymalizacyjnego:
  
  $\begin{cases}Df(\mathbf{x})\mathbf{d}\to\min,&\\ A_{1}\mathbf{d}\le\mathbf{0},&\\ Q\mathbf{d}=\mathbf{0},&\\ -1\le d_{i}\le 1,\quad i=1,\ldots,n.&\end{cases}$ (14.5)
2. Jeśli $\mathbf{d}_{k}=\mathbf{0}$ , to zakończ działanie algorytmu. Punkt $\mathbf{x}_{k}$ spełnia warunek konieczny pierwszego rzędu. W przeciwnym przypadku kontynuuj.
3. Połóż $\alpha _{k}=\text{argmin}_{{\alpha\in[0,A_{k}]}}f(\mathbf{x}_{k}+\alpha\mathbf{d}_{k})$ , gdzie $A_{k}$ jest największą liczbą o tej własności, że odcinek łączący $\mathbf{x}_{k}$ i $\mathbf{x}_{k}+A_{k}\mathbf{d}_{k}$ zawarty jest w $W$ .
4. Połóż $x_{{k+1}}=\mathbf{x}_{k}+\alpha _{k}\mathbf{d}_{k}.$

Przyjrzyjmy się jeszcze raz wyborowi kierunku $\mathbf{d}_{k}$ . Wektor $\mathbf{d}=\mathbf{0}$ spełnia wszystkie ograniczenia, a zatem optymalna wartość funkcji celu $Df(\mathbf{x})\mathbf{d}_{k}$ jest co najwyżej równa zeru. Wówczas punkt $\mathbf{x}_{k}$ spełnia warunek konieczny pierwszego rzędu, czego dowodzimy w poniższym lemacie.

Lemat 14.2

W $\mathbf{x}_{k}$ spełniony jest warunek konieczny pierwszego rzędu wtw, gdy $\mathbf{d}_{k}=\mathbf{0}$ .

Dowód

Przypomnijmy najpierw notację. Przez $D(\mathbf{x}_{k})$ oznaczamy stożek kierunków spadku, tzn.

$D(\mathbf{x}_{k})=\{\mathbf{d}\in\mathbb{R}^{n}:\ Df(\mathbf{x}_{k})\mathbf{d}<0\},$

zaś przez $T_{{lin}}(\mathbf{x}_{k})$ – stożek kierunków stycznych dla ograniczeń zlinearyzowanych w punkcie $\mathbf{x}_{k}$ , który dla ograniczeń liniowych danych jest wzorem

$T_{{lin}}(\mathbf{x}_{k})=\{\mathbf{d}\in\mathbb{R}^{n}:\ A_{1}\mathbf{d}\le\mathbf{0},\quad Q\mathbf{d}=\mathbf{0}\}.$

Zauważmy, że $\mathbf{d}_{k}=\mathbf{0}$ jest rozwiązaniem zagadnienia (14.5) wtw, gdy $D(\mathbf{x}_{k})\cap T_{{lin}}(\mathbf{x}_{k})=\emptyset$ . Postępując dalej jak w dowodzie twierdzenia 8.1 dostajemy implikację w lewo. Implikacja w drugą stronę wynika faktu, że na mocy lematu Farkasa, lemat 5.3, istnienie rozwiązania (8.5) pociąga brak rozwiązania (8.4), co jest równoważne temu, że $D(\mathbf{x}_{k})\cap T_{{lin}}(\mathbf{x}_{k})=\emptyset.$

∎

14.2. Algorytm Zoutendijk'a dla ograniczeń nieliniowych

Zastanówmy się, czy algorytm Zoutendijk'a działa równie dobrze dla ograniczeń nieliniowych:

Inicjalizacja: Wybierz punkt początkowy $\mathbf{x}_{0}$ .
Krok $k$ -ty:
1. Wybierz kierunek ruchu $\mathbf{d}_{k}$ jako rozwiązanie problemu optymalizacyjnego:
  
  $Df(\mathbf{x})\mathbf{d}\to\min,\qquad\mathbf{d}\in A(\mathbf{x}),\quad\|\mathbf{d}\|\le 1.$
2. Jeśli $\mathbf{d}_{k}=\mathbf{0}$ , to zakończ działanie algorytmu. Punkt $\mathbf{x}_{k}$ spełnia warunek konieczny pierwszego rzędu. W przeciwnym przypadku kontynuuj.
3. Połóż $\alpha _{k}=\text{argmin}_{{\alpha\in[0,A_{k}]}}f(\mathbf{x}_{k}+\alpha\mathbf{d}_{k})$ , gdzie $A_{k}$ jest największą liczbą o tej własności, że odcinek łączący $\mathbf{x}_{k}$ i $\mathbf{x}_{k}+A_{k}\mathbf{d}_{k}$ zawarty jest w $W$ .
4. Połóż $x_{{k+1}}=\mathbf{x}_{k}+\alpha _{k}\mathbf{d}_{k}.$

Rys. 14.1. Ilustracja szybkiej zbieżności metody największego spadku.

Rys. 14.2. Ilustracja zakleszczenia metody największego spadku dla zbioru niewypukłego.

Rys. 14.3. Ilustracja problemu ze znalezieniem kierunku dopuszczalnego największego spadku.

W poniższych przykładach rozważamy minimalizowanie funkcji $f(x_{1},x_{2})=-2x_{1}-x_{2}$ na różnych zbiorach. Punkt minimum oznaczamy zawsze przez ${\bar{\mathbf{x}}}$ . Na rysunku 14.1 widać, że już w kroku drugim osiągamy minimum. Jeśli zbiór $W$ nie jest wypukły algorytm prowadzi nas w kozi róg, z którego już nie możemy się uwolnić, patrz 14.2. Jest to niestety cecha wszystkich algorytmów tego typu, więc musimy zawsze wymagać, by zbiór punktów dopuszczalnych był wypukły. Czy to już wystarczy? Niestety nie. Na rysunku 14.3 możemy zobaczyć, że nawet w przypadku zbioru wypukłego algorytm nie działa. Problem wyboru kierunku $\mathbf{d}_{1}$ nie ma rozwiązania, gdyż zbiór $D(\mathbf{x}_{1})$ nie jest domknięty. Intuicyjnie łatwo jest podać rozwiązanie tego problemu. Należy wybrać taki kierunek $\mathbf{d}_{k}$ , aby nie tylko spadek był jak największy, ale również, żeby dość duży fragment półprostej poprowadzonej w tym kierunku zawierał się w zbiorze $W$ . Co więcej, zależy nam na prostocie, czytaj liniowości, zagadnienia optymalizacyjnego wyznaczającego kierunek $\mathbf{d}_{k}$ . Rozwiązanie podpowiada następujący lemat, którego dowód pozostawiamy jako ćwiczenie.

Lemat 14.3

Niech $\mathbf{x}$ będzie punktem dopuszczalnym. Jeśli $f,g_{i}$ , $i\in I(\mathbf{x})$ są różniczkowalne w $\mathbf{x}$ i $g_{i}$ , $i\notin I(\mathbf{x})$ są ciągłe w $\mathbf{x}$ , to kierunek $\mathbf{d}\in\mathbb{R}^{n}$ spełniający $Df(\mathbf{x})\mathbf{d}<0$ i $Dg_{i}(\mathbf{x})\mathbf{d}<0$ , $i\in I(\mathbf{x})$ , jest dopuszczalnym kierunkiem spadku.

Lemat powyższy podaje tylko warunek dostateczny. Łatwo znaleźć przykład zagadnienia optymalizacyjnego z ograniczeniami nierównościowymi, dla którego jeden z dopuszczalnym kierunków spadku nie spełnia założeń lematu (ćwiczenie 14.5).

Znalezienie wektora $\mathbf{d}\in\mathbb{R}^{n}$ spełniającego $Df(\mathbf{x})\mathbf{d}<0$ i $Dg_{i}(\mathbf{x})\mathbf{d}<0$ , $i\in I(\mathbf{x})$ sprowadza się do rozwiązania zagadnienia

$\begin{cases}\max\big\{ Df(\mathbf{x})\mathbf{d},\quad Dg_{i}(\mathbf{x})\mathbf{d},i\in I(\mathbf{x})\big\}\to\min,&\\ -1\le d_{k}\le 1,\quad k=1,\ldots,n.&\end{cases}$

Trudną w implementacji funkcję celu można sprowadzić do znacznie prostszej formy problemu optymalizacji liniowej:

$\begin{cases}\eta\to\min,&\\ Df(\mathbf{x})\mathbf{d}\le\eta,&\\ Dg_{i}(\mathbf{x})\mathbf{d}\le\eta,\quad i\in I(\mathbf{x}),&\\ -1\le d_{k}\le 1,\quad k=1,\ldots,n.&\end{cases}$

(14.6)

Optymalizacji dokonuje się tutaj względem dwóch zmiennych: $\mathbf{d}\in\mathbb{R}^{n}$ oraz $\eta\in\mathbb{R}.$ Zauważmy, że $\eta\le 0$ , gdyż para $\mathbf{d}=\mathbf{0}$ , $\eta=0$ rozwiązuje powyższy układ. Jeśli wartość funkcji celu jest mniejsza od zera, to, na mocy lematu 14.1, rozwiązanie jest dopuszczalnym kierunkiem spadku. Jeśli $\eta=0$ jest rozwiązaniem i w punkcie $\mathbf{x}$ spełniony jest warunek liniowej niezależności ograniczeń, to wówczas w $\mathbf{x}$ zachodzi warunek konieczny pierwszego rzędu. Prawdziwa jest również odwrotna implikacja.

Lemat 14.4

Jeśli w punkcie dopuszczalnym $\mathbf{x}$ spełniony jest warunek liniowej niezależności ograniczeń i rozwiązaniem problemu (14.6) jest $\eta=0$ , to w $x$ zachodzi warunek konieczny pierwszego rzędu. I odwrotnie, jeśli w $\mathbf{x}$ spełniony jest warunek konieczny pierwszego rzędu, to rozwiązaniem (14.6) jest $\eta=0$ (nie jest tu konieczne założenie o regularności punktu $\mathbf{x}$ ).

Dowód

Jeśli $\eta=0$ jest rozwiązaniem, to układ $A\mathbf{d}<0$ , gdzie $A$ składa się wierszowo z gradientów $Df(\mathbf{x})$ i $Dg_{i}(\mathbf{x})$ , $i\in I(\mathbf{x})$ , nie ma rozwiązania. Na mocy lematu 6.2 istnieje $\mathbf{y}\ge 0$ , $y\ne\mathbf{0}$ , dla którego $A^{T}\mathbf{y}=\mathbf{0}$ . Połóżmy $(\hat{\mu}_{0},\ \hat{\mu}_{i},i\in I(\mathbf{x}))=\mathbf{y}$ i $\hat{\mu}_{i}=0$ , $i\notin I(\mathbf{x}).$ Równość $A^{T}\mathbf{y}=\mathbf{0}$ zapisać można w następujący sposób:

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

Z założenia o liniowej niezależności gradientów ograniczeń aktywnych wnioskujemy, że $\hat{\mu}_{0}\ne 0$ . Kładąc $\mu _{i}=\hat{\mu}_{i}/\hat{\mu}_{0}$ , $i=1,\ldots,m,$ dostajemy wektor mnożników Lagrange'a z warunku koniecznego pierwszego rzędu.

Aby dowieść implikacji odwrotnej, zauważmy, że jeśli w $\mathbf{x}$ spełniony jest warunek konieczny pierwszego rzędu, to $\mathbf{y}=\big(1,\mu _{i},\ i\in I(\mathbf{x})\big)$ spełnia następujące warunki: $\mathbf{y}\ge 0$ , $y\ne\mathbf{0}$ i $A^{T}\mathbf{y}=\mathbf{0}$ . Na mocy lematu 6.2 nie istnieje $\mathbf{d}\in\mathbb{R}^{n}$ , dla którego $A\mathbf{d}<0.$ A zatem rozwiązaniem 14.6 jest $\eta=0.$

∎

Zapiszmy w pełni algorytm zaproponowany przez Zoutendijka dla problemów z nieliniowymi ograniczeniami nierównościowymi:

Inicjalizacja: Wybierz punkt początkowy $\mathbf{x}_{0}$ .
Krok $k$ -ty:
1. Wybierz kierunek ruchu $\mathbf{d}_{k}$ jako rozwiązanie problemu optymalizacyjnego (14.6)
2. Jeśli $\eta=\mathbf{0}$ , to zakończ działanie algorytmu. Punkt $\mathbf{x}_{k}$ spełnia warunek konieczny pierwszego rzędu. W przeciwnym przypadku kontynuuj.
3. Połóż $\alpha _{k}=\text{argmin}_{{\alpha\in[0,A_{k}]}}f(\mathbf{x}_{k}+\alpha\mathbf{d}_{k})$ , gdzie $A_{k}$ jest największą liczbą o tej własności, że odcinek łączący $\mathbf{x}_{k}$ i $\mathbf{x}_{k}+A_{k}\mathbf{d}_{k}$ zawarty jest w $W$ .
4. Połóż $x_{{k+1}}=\mathbf{x}_{k}+\alpha _{k}\mathbf{d}_{k}.$

Przykład 14.1

Rozważmy problem optymalizacji z ograniczeniami nieliniowymi:

$\begin{cases}2x_{1}^{2}+2x_{2}^{2}-2x_{1}x_{2}-4x_{1}-6x_{2}\to min,&\\ x_{1}+5x_{2}\le 5,&\\ 2x_{1}^{2}-x_{2}\le 0,&\\ x_{1}\ge 0,\quad x_{2}\ge 0.&\end{cases}$

Pokażemy, w jaki sposób postępując iteracje metody Zoutendijka. Weźmy punkt startowy $\mathbf{x}_{0}=(0,0.75)^{T}.$ Dostajemy następujący ciąg punktów:

		$\displaystyle\mathbf{x}_{1}=(0,2083,0.5477)^{T},\quad\mathbf{x}_{2}=(0.5555,0.8889)^{T},$
		$\displaystyle\mathbf{x}_{3}=(0.6479,0.8397)^{T},\quad\mathbf{x}_{4}=(0.6302,0.8740)^{T}.$

Widzimy, że ciąg ten dość znacznie oscyluje w zbiorze punktów dopuszczalnych, patrz rys. 14.4. Jest to charakterystyczne zachowanie metody kierunków spadku dla problemów z ograniczeniami.

Rys. 14.4. Oscylacja ciągu generowanego przez metodę Zoutendijka.

Rys. 14.5. Ilustracja zbieżności algorytmu Zoutendijka do punktu nie będącego rozwiązaniem.

Algorytm Zoutendijka może polec nawet na dość prostych prostych problemach optymalizacyjnych. Rozważmy minimalizowanie funkcji liniowej $f(\mathbf{x})=-2x_{1}-x_{2}$ na zbiorze zaznaczonym na rysunku 14.5. Minimum znajduje się w punkcie ${\bar{\mathbf{x}}}=(1,1)^{T}$ . Rozpoczynając od punktu $\mathbf{x}_{0}=(-1,0)^{T}$ , kolejne iteracje algorytmu Zoutendijka wygenerują ciąg punktów zbiegający do $(1,0)^{T}$ . Algorytm ten nie pozwoli nam na przybliżenie właściwego rozwiązania ${\bar{\mathbf{x}}}$ . Co więcej, wartość funkcji celu w punkcie $(1,0)^{T}$ wynosi $-2$ , w porównaniu do $f({\bar{\mathbf{x}}})=-3.$ W następnym podrozdziale pokażemy jak mała modyfikacja pozwoli naprawić algorytm Zoutendijka.

14.3. Modyfikacja Topkis'a-Veinott'a

Topkis i Veinott zaproponowali w roku 1967 niewielką modyfikację wyznaczania kierunku $\mathbf{d}_{k}$ w algorytmie Zoutendijka:

$\begin{cases}\eta\to\min,&\\ Df(\mathbf{x})\mathbf{d}\le\eta,&\\ Dg_{i}(\mathbf{x})\mathbf{d}\le\eta-g_{i}(\mathbf{x}),\quad i=1,\ldots,m,&\\ -1\le d_{k}\le 1,\quad k=1,\ldots,n.&\end{cases}$

(14.7)

Linia dotycząca warunku na gradienty ograniczeń obejmuje teraz wszystkie ograniczenia. Dla ograniczeń aktywnych, $i\in I(\mathbf{x})$ , mamy $g_{i}(\mathbf{x})=0$ , a więc warunki te są identyczne jak w (14.6). W przypadku ograniczeń nieaktywnych $g_{i}(\mathbf{x})<0$ , czyli prawa strona jest większa niż $\eta.$ O ile dla dużych wartości $g_{i}(\mathbf{x})$ ograniczenie takie jest prawie niezauważalne, to dla ograniczeń, które są ”prawie aktywne”, odgrywa znaczną rolę. Poza tym, z punktu widzenia implementacji, rozwiązuje to kwestię znajdowania zbioru ograniczeń aktywnych (ze względu na niedokładności zapisu liczb, prawie nigdy nie będzie spełniony warunek $g_{i}(\mathbf{x})=0$ ).

O skuteczności modyfikacji (14.7) świadczy następujące twierdzenie, które podamy bez dowodu:

Twierdzenie 14.1

Załóżmy, że $f,g_{i}$ , $i=1,\ldots,m$ , są klasy $C^{1}$ . Jeśli ciąg $(\mathbf{x}_{k})$ wygenerowany przez algorytm Zoutendijka z modyfikacją Topkis'a-Veinott'a posiada punkt skupienia, w którym spełniony jest warunek liniowej niezależności, to zachodzi w nim warunek konieczny pierwszego rzędu.

14.4. Podsumowanie

Metody numeryczne opisane w tym rozdziale pozwalają na znalezienie aproksymacji punktów, w których spełniony jest warunek konieczny pierwszego rzędu. Twierdzenie 7.6 zagwarantuje dopiero optymalność tych punktów. W szczególności, jeśli ograniczenia są liniowe, to wystarczy założyć pseudowypukłość funkcji $f$ . Zwróćmy uwagę, że wymagaliśmy podobnych założeń w poprzednim rozdziale, dla optymalizacji bez ograniczeń. Wymóg wypukłości okazuje się bardzo naturalnym i, co więcej, koniecznym dla sprawnego działania tych metod.

14.5. Zadania

Ćwiczenie 14.1

Znajdź graficznie zbiór dopuszczalnych kierunków spadku w punkcie $\mathbf{x}=(2,3)^{T}$ dla zagadnienia

$\begin{cases}(x_{1}-6)^{2}+(x_{2}-2)^{2}\to\min,&\\ -x_{1}+2x_{2}\le 4,&\\ 3x_{1}+2x_{2}\le 12,&\\ x_{1}\ge 0,\quad x_{2}\ge 0.&\end{cases}$

Ćwiczenie 14.2

Udowodnij lemat 14.1.

Ćwiczenie 14.3

Rozwiąż następujące zagadnienie optymalizacyjne z ograniczeniami liniowymi:

$\begin{cases}2x_{1}^{2}+2x_{2}^{2}-2x_{1}x_{2}-4x_{1}-6x_{2}\to min,&\\ x_{1}+x_{2}\le 2,&\\ x_{1}+5x_{2}\le 5,&\\ x_{1}\ge 0,\quad x_{2}\ge 0.&\end{cases}$

Zastosuj algorytm Zoutendijka i weź jako punkt początkowy $\mathbf{x}_{0}=\mathbf{0}.$

Wskazówka:

Algorytm kończy się w trzeciej iteracji (optymalna wartość funkcji celu w zagadnieniu poszukiwania kierunku $\mathbf{d}_{k}$ wynosi wówczas $0$ ).

Ćwiczenie 14.4

Udowodnij lemat 14.3.

Ćwiczenie 14.5

Podaj przykład problemu optymalizacyjnego z ograniczeniami nierównościowymi, dla którego istnieje dopuszczalny kierunek spadku, który nie spełnia założeń lematu 14.3.

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

Optymalizacja II

Zagadnienia

14. Metody optymalizacji z ograniczeniami

14.1. Algorytm Zoutendijk'a dla ograniczeń liniowych

Lemat 14.1

Lemat 14.2

Dowód

14.2. Algorytm Zoutendijk'a dla ograniczeń nieliniowych

Lemat 14.3

Lemat 14.4

Dowód

Przykład 14.1

14.3. Modyfikacja Topkis'a-Veinott'a

Twierdzenie 14.1

14.4. Podsumowanie

14.5. Zadania

Ćwiczenie 14.1

Ćwiczenie 14.2

Ćwiczenie 14.3

Ćwiczenie 14.4

Ćwiczenie 14.5