Zagadnienia

11.1 Ograniczenia równościowe
11.2 Ograniczenia nierównościowe
11.3 Zadania

11. Teoria wrażliwości

Dotychczas mnożniki Lagrange'a wydawały się techniczną sztuczką służącą do znajdowania rozwiązania problemu optymalizacyjnego z ograniczeniami. W tym rozdziale pokażemy, że pełnią one rolę kosztu związanego ze zmianą ograniczeń. Oddzielnie zajmiemy się ograniczeniami równościowymi i nierównościowymi.

11.1. Ograniczenia równościowe

Rozważmy problem optymalizacyjny z ograniczeniami równościowymi:

$\begin{cases}f(\mathbf{x})\to\min,&\\ h_{j}(\mathbf{x})=0,\quad j=1,\ldots,l,&\\ \mathbf{x}\in\mathbb{X},\end{cases}$

(11.1)

gdzie $\mathbb{X}\in\mathbb{R}^{n}$ jest zbiorem otwartym i $f,h_{1},\ldots,h_{l}:\mathbb{X}\to\mathbb{R}$ . Dla uproszczenia notacji połóżmy $h(\mathbf{x})=[h_{1}(\mathbf{x}),\ldots,h_{l}(\mathbf{x})]^{T}$ . Rozważmy problem zaburzony, tzn.

$\begin{cases}f(\mathbf{x})\to\min,&\\ h(\mathbf{x})=\mathbf{z},&\\ \mathbf{x}\in\mathbb{X},\end{cases}$

(11.2)

gdzie $\mathbf{z}\in\mathbb{R}^{l}.$

Twierdzenie 11.1

Niech ${\bar{\mathbf{x}}}$ będzie rozwiązaniem lokalnym problemu (11.1), zaś $\bar{\lambda}$ wektorem jego mnożników Lagrange'a. Załóżmy, że funkcje $f,h_{1},\ldots,h_{l}$ są klasy $C^{2}$ na otoczeniu ${\bar{\mathbf{x}}}$ , gradienty ograniczeń są liniowo niezależne (spełniony jest warunek liniowej niezależności) oraz

$\mathbf{d}^{T}D^{2}_{\mathbf{x}}L({\bar{\mathbf{x}}},\bar{\lambda})\mathbf{d}>0$

(11.3)

dla $\mathbf{d}\in\mathbb{R}^{n}\setminus\mathbf{0}$ spełniających $Dh_{j}({\bar{\mathbf{x}}})\mathbf{d}=0$ , $j=1,\ldots,l.$ Wówczas istnieje otoczenie $\tilde{O}$ punktu $\mathbf{0}\in\mathbb{R}^{l}$ oraz funkcja $\mathbf{x}:\tilde{O}\to\mathbb{X}$ klasy $C^{1}$ , taka że $\mathbf{x}(\mathbf{0})={\bar{\mathbf{x}}}$ oraz $\mathbf{x}(\mathbf{z})$ jest ścisłym rozwiązaniem lokalnym problemu zaburzonego (11.2). Ponadto,

$D(f\circ\mathbf{x})(\mathbf{0})=-\bar{\lambda}^{T}.$

Dowód

Na mocy tw. 8.1 punkt ${\bar{\mathbf{x}}}$ rozwiązuje układ równań:

$\begin{cases}D_{\mathbf{x}}L({\bar{\mathbf{x}}},\bar{\lambda})=\mathbf{0}^{T},\\ h({\bar{\mathbf{x}}})=\mathbf{0},\end{cases}$

gdzie

$D_{\mathbf{x}}L({\bar{\mathbf{x}}},\bar{\lambda})=Df({\bar{\mathbf{x}}})+\bar{\lambda}^{T}Dh({\bar{\mathbf{x}}})=Df({\bar{\mathbf{x}}})+\sum _{{j=1}}^{l}\bar{\lambda}_{j}Dh_{j}({\bar{\mathbf{x}}}).$

Zaburzając prawą stronę drugiej równości przez $\mathbf{z}$ będziemy chcieli pokazać, że istnieje rozwiązanie, które jest funkcją $\mathbf{z}$ klasy $C^{1}$ . Rozważmy więc układ:

$D_{\mathbf{x}}L(\mathbf{x},\lambda)=\mathbf{0}^{T},\qquad h(\mathbf{x})=\mathbf{z},$

gdzie niewiadomymi są $\lambda$ oraz $\mathbf{x}$ . Zdefiniujmy funkcję $G:\mathbb{R}^{n}\times\mathbb{R}^{l}\times\mathbb{R}^{l}\to\mathbb{R}^{n}\times\mathbb{R}^{l}$ wzorem

$G(\mathbf{x},\lambda,\mathbf{z})=\begin{bmatrix}\big(D_{\mathbf{x}}L(\mathbf{x},\lambda)\big)^{T}\\ h(\mathbf{x})-\mathbf{z}\end{bmatrix}.$

Zaburzony układ możemy wówczas zapisać jako

$G(\mathbf{x},\lambda,\mathbf{z})=\mathbf{0}.$

Wiemy, że $G({\bar{\mathbf{x}}},\bar{\lambda},\mathbf{0})=\mathbf{0}.$ Skorzystamy z twierdzenia o funkcji uwikłanej, aby rozwikłać pierwsze dwie zmienne w zależności od trzeciej. W tym celu rozważamy macierz pochodnych $DG({\bar{\mathbf{x}}},\bar{\lambda},\mathbf{0})$ :

$DG({\bar{\mathbf{x}}},\bar{\lambda},\mathbf{0})=\begin{bmatrix}D^{2}_{\mathbf{x}}L({\bar{\mathbf{x}}},\bar{\lambda}),&\big(Dh({\bar{\mathbf{x}}})\big)^{T},&\mathbf{0}\\ Dh({\bar{\mathbf{x}}}),&\mathbf{0},&-I\end{bmatrix}.$

Warunek liniowej niezależności gradientów ograniczeń implikuje nieosobliwość podmacierzy

$\begin{bmatrix}D^{2}_{\mathbf{x}}L({\bar{\mathbf{x}}},\bar{\lambda}),&\big(Dh({\bar{\mathbf{x}}})\big)^{T}\\ Dh({\bar{\mathbf{x}}}),&\mathbf{0}\end{bmatrix}.$

Spełnione są zatem założenia twierdzenia 8.4 i istnieje otoczenie $O$ punktu $\mathbf{0}\in\mathbb{R}^{l}$ oraz funkcje $\mathbf{x}:O\to\mathbb{X}$ i $\lambda:O\to\mathbb{R}^{l}$ klasy $C^{1}$ , takie że dla $\mathbf{z}\in O$ zachodzi $G\big(\mathbf{x}(\mathbf{z}),\lambda(\mathbf{z}),\mathbf{z}\big)=\mathbf{0}$ , czyli

$D_{\mathbf{x}}L\big(\mathbf{x}(\mathbf{z}),\lambda(\mathbf{z})\big)=\mathbf{0}^{T},\qquad h\big(\mathbf{x}(\mathbf{z})\big)=\mathbf{z}.$

Korzystając z faktu, iż funkcje $D^{2}_{\mathbf{x}}L,Dh,\mathbf{x},\lambda$ są ciągłe oraz nierówność (11.3) spełniona jest dla niezaburzonego problemu, wnioskujemy, że istnieje być może mniejsze otoczenie $\tilde{O}$ punktu $\mathbf{0}\in\mathbb{R}^{l}$ , takie że

$\mathbf{d}^{T}D^{2}_{\mathbf{x}}L\big(\mathbf{x}(\mathbf{z}),\lambda(\mathbf{z})\big)\mathbf{d}>0$

dla $\mathbf{z}\in\tilde{O}$ i $\mathbf{d}\in\mathbb{R}^{n}\setminus\mathbf{0}$ spełniających $Dh_{j}\big(\mathbf{x}(\mathbf{z})\big)\mathbf{d}=0$ , $j=1,\ldots,l.$ Kluczowa dla tego wyniku jest ostra nierówność w warunku (11.3). Na mocy tw. 9.3 punkt $\mathbf{x}(\mathbf{z})$ jest zatem ścisłym rozwiązaniem lokalnym problemu zaburzonego (11.2). Przypomnijmy, że funkcja $\mathbf{x}$ jest klasy $C^{1}$ . Możemy zatem zdefiniować pochodną złożenia

$D(f\circ\mathbf{x})(\mathbf{0})=Df({\bar{\mathbf{x}}})D\mathbf{x}(\mathbf{0}).$

Od zakończenia dowodu dzielą nas dwa spostrzeżenia. Po pierwsze, mnożąc obie strony warunku koniecznego pierwszego rzędu dla problemu niezaburzonego

$Df({\bar{\mathbf{x}}})+\bar{\lambda}^{T}Dh({\bar{\mathbf{x}}})=\mathbf{0}^{T}.$

przez $D\mathbf{x}(\mathbf{0})$ dostajemy

$Df({\bar{\mathbf{x}}})D\mathbf{x}(\mathbf{0})+\bar{\lambda}^{T}Dh({\bar{\mathbf{x}}})D\mathbf{x}(\mathbf{0})=\mathbf{0}^{T}.$

Po drugie, rózniczkując $h\big(\mathbf{x}(\mathbf{z})\big)=\mathbf{z}$ po $\mathbf{z}$ otrzymujemy w punkcie $\mathbf{z}=\mathbf{0}$ następującą pochodną $D(h\circ\mathbf{x})(\mathbf{0})=I$ , czyli $Dh({\bar{\mathbf{x}}})D\mathbf{x}(\mathbf{0})=I.$ Upraszcza to powyższe równanie do

$Df({\bar{\mathbf{x}}})D\mathbf{x}(\mathbf{0})+\bar{\lambda}^{T}=\mathbf{0}^{T}.$

Stąd już teza wynika natychmiast.

∎

Twierdzenie 11.1 można rozumieć następująco: nieznaczna zmiana $j$ -tego ograniczenia z zera do $\varepsilon$ prowadzi do zmiany optymalnej wartości funkcji $f$ o $-\bar{\lambda}_{j}\varepsilon+o(\varepsilon)$ , tzn. dla małych $\varepsilon$ zmiana ta jest w przybliżeniu równa $-\bar{\lambda}_{j}\varepsilon.$

11.2. Ograniczenia nierównościowe

W przypadku ograniczeń nierównościowych zastosujemy inne podejście. Skoncentrujemy się na zadaniu optymalizacji wypukłej:

$\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}$

(11.4)

gdzie $\mathbb{X}\subset\mathbb{R}^{n}$ jest wypukły, $f,g_{1},\ldots,g_{m}:\mathbb{X}\to\mathbb{R}$ są wypukłe. Dla uproszczenia notacji będziemy pisać $g(\mathbf{x})=[g_{1}(\mathbf{x}),\ldots,g_{m}(\mathbf{x})]^{T}$ . Problem (11.4) zapisujemy więc jako

$\begin{cases}f(\mathbf{x})\to\min,&\\ g(\mathbf{x})\le\mathbf{0},\quad\mathbf{x}\in\mathbb{X}.&\end{cases}$

(11.5)

Rozważmy zadanie zaburzone: dla $\mathbf{z}\in\mathbb{R}^{m}$

$\begin{cases}f(\mathbf{x})\to\min,&\\ g(\mathbf{x})\le\mathbf{z},\quad\mathbf{x}\in\mathbb{X},&\end{cases}$

(11.6)

Definicja 11.1

Niech $D_{M}$ będzie zbiorem takich $\mathbf{z}\in\mathbb{R}^{m}$ , dla których zbiór punktów dopuszczalnych $W_{\mathbf{z}}=\{\mathbf{x}\in\mathbb{X}:\ g(\mathbf{x})\le\mathbf{z}\}$ jest niepusty. Funkcją perturbacji nazywamy funkcję

$M(\mathbf{z})=\inf _{{\mathbf{x}\in\mathbb{X},\ g(\mathbf{x})\le\mathbf{z}}}f(\mathbf{x})$

określoną dla $\mathbf{z}$ należących do dziedziny $D_{M}$ .

Zauważmy, że $M(\mathbf{z})<\infty$ dla $\mathbf{z}\in D_{M}$ , ale może się zdarzyć, że $M(\mathbf{z})=-\infty$ .

Twierdzenie 11.2

$\$

Zbiór $D_{M}$ jest wypukły.
Funkcja $M:D_{M}\to\mathbb{R}\cup\{-\infty\}$ jest wypukła.
Jeśli istnieje punkt $\mathbf{x}^{*}\in\mathbb{X}$ , taki że $g_{i}(\mathbf{x}^{*})<0$ , $i=1,\ldots,m,$ to $\mathop{\rm int}D_{M}\ne\emptyset$ i $\mathbf{0}\in\mathop{\rm int}D_{M}$ .

Dowód

Z wypukłości $g$ wynika następująca implikacja:

$g(\mathbf{x}^{1})\le\mathbf{z}^{1},\quad g(\mathbf{x}^{2})\le\mathbf{z}^{2}\qquad\implies\qquad\forall\ \lambda\in[0,1]\quad g\big(\lambda\mathbf{x}^{1}+(1-\lambda)\mathbf{x}^{2}\big)\le\lambda\mathbf{z}^{1}+(1-\lambda)\mathbf{z}^{2}.$

(11.7)

Będziemy korzystać z tego spostrzeżenia wielokrotnie w dowodzie.

(1) Niech $\mathbf{z}^{1},\mathbf{z}^{2}\in D_{M}$ i $\lambda\in(0,1).$ Wówczas istnieją $\mathbf{x}^{1},\mathbf{x}^{2}\in\mathbb{X}$ takie że $g(\mathbf{x}^{1})\le\mathbf{z}^{1}$ i $g(\mathbf{x}^{2})\le\mathbf{z}^{2}.$ Z wzoru (11.7) dostajemy $g\big(\lambda\mathbf{x}^{1}+(1-\lambda)\mathbf{x}^{2}\big)\le\lambda\mathbf{z}^{1}+(1-\lambda)\mathbf{z}^{2}$ , skąd wynika $\lambda\mathbf{z}^{1}+(1-\lambda)\mathbf{z}^{2}\in D_{M}.$

(2) Niech $\mathbf{z}^{1},\mathbf{z}^{2}\in D_{M}$ i $\lambda\in(0,1).$ Wówczas

	$\displaystyle\lambda M(\mathbf{z}^{1})+(1-\lambda)M(\mathbf{z}^{2})$	$\displaystyle=\inf _{{\mathbf{x}^{1}\in\mathbb{X},\ g(\mathbf{x}^{1})\le\mathbf{z}^{1}}}\big(\lambda f(\mathbf{x}^{1})\big)+\inf _{{\mathbf{x}^{2}\in\mathbb{X},\ g(\mathbf{x}^{2})\le\mathbf{z}^{2}}}\big((1-\lambda)f(\mathbf{x}^{2})\big)$
		$\displaystyle=\inf _{{\mathbf{x}^{1}\in\mathbb{X},\ g(\mathbf{x}^{1})\le\mathbf{z}^{1},\ \mathbf{x}^{2}\in\mathbb{X},\ g(\mathbf{x}^{2})\le\mathbf{z}^{2}}}\big(\lambda f(\mathbf{x}^{1})+(1-\lambda)f(\mathbf{x}^{2})\big)$
		$\displaystyle\ge\inf _{{\mathbf{x}^{1}\in\mathbb{X},\ g(\mathbf{x}^{1})\le\mathbf{z}^{1},\ \mathbf{x}^{2}\in\mathbb{X},\ g(\mathbf{x}^{2})\le\mathbf{z}^{2}}}f\big(\lambda\mathbf{x}^{1}+(1-\lambda)\mathbf{x}^{2}\big)$
		$\displaystyle\ge\inf _{{\mathbf{x}\in\mathbb{X},\ g(\mathbf{x})\le\lambda\mathbf{z}^{1}+(1-\lambda)\mathbf{z}^{2}}}f(\mathbf{x}),$

gdzie pierwsza nierówność wynika z wypukłości $f$ , zaś ostatnia – z własności (11.7):

$\big\{\lambda\mathbf{x}^{1}+(1-\lambda)\mathbf{x}^{2}:\ \mathbf{x}^{1}\in\mathbb{X},\ g(\mathbf{x}^{1})\le\mathbf{z}^{1},\ \mathbf{x}^{2}\in\mathbb{X},\ g(\mathbf{x}^{2})\le\mathbf{z}^{2}\big\}\subseteq\big\{\mathbf{x}\in\mathbb{X}:\ g(\mathbf{x})\le\lambda\mathbf{z}^{1}+(1-\lambda)\mathbf{z}^{2}\big\}.$

(3) Musimy udowodnić, że zbiór dopuszczalny $W_{\mathbf{z}}$ jest niepusty dla $\mathbf{z}$ z pewnego otoczenia $\mathbf{0}\in\mathbb{R}^{m}$ . Wiemy, że istnieje punkt $\mathbf{x}^{*}\in\mathbb{X}$ , taki że $g_{i}(\mathbf{x}^{*})<0$ , $i=1,\ldots,m.$ Weźmy $a=\min\{-g_{i}(\mathbf{x}^{*}):\ i=1,\ldots,m\}.$ Wówczas dla każdego $\mathbf{z}\in[-a,a]^{m}$ mamy $\mathbf{x}^{*}\in W_{\mathbf{z}}.$ Zatem $[-a,a]^{m}\subset D_{M}$ .

∎

Uwaga 11.1

Jeśli $M({\bar{\mathbf{z}}})=-\infty$ dla pewnego ${\bar{\mathbf{z}}}\in D_{M}$ , to dla dowolnego $\mathbf{z}\in D_{M}$ i $\lambda\in(0,1)$ mamy z wypukłości $M\big(\lambda{\bar{\mathbf{z}}}+(1-\lambda)\mathbf{z}\big)=-\infty.$
Jeśli $M({\bar{\mathbf{z}}})=-\infty$ dla pewnego ${\bar{\mathbf{z}}}\in D_{M}$ , to $M(\mathbf{z})=-\infty$ dla $\mathbf{z}\in\mathop{\rm int}D_{M}.$ Wynika to wprost z powyższej uwagi.
Jeśli istnieje ${\bar{\mathbf{z}}}\in\mathop{\rm int}D_{M}$ taki że $M({\bar{\mathbf{z}}})>-\infty$ , to $M(\mathbf{z})>-\infty$ dla każdego $\mathbf{z}\in D_{M}.$ Inaczej mielibyśmy sprzeczność z punktem (2).

Twierdzenie 11.3

Jeśli w problemie optymalizacji wypukłej istnieje punkt $\mathbf{x}^{*}\in\mathbb{X}$ , taki że $g_{i}(\mathbf{x}^{*})<0$ , $i=1,\ldots,m,$ oraz $M(\mathbf{0})>-\infty$ , to $M(\mathbf{z})>-\infty$ dla każdego $\mathbf{z}\in D_{M}$ oraz istnieje wektor $\mu\in[0,\infty)^{m}$ wyznaczający płaszczyznę podpierającą $M$ :

$M(\mathbf{z})\ge M(\mathbf{0})-\mu^{T}\mathbf{z},\qquad\mathbf{z}\in D_{M}.$

Dowód

Z tw. 11.2 wynika, że $M$ jest funkcją wypukłą i $\mathbf{0}\in\mathop{\rm int}D_{M}.$ Zatem na mocy ostatniej z powyższych uwag mamy $M(\mathbf{z})>-\infty$ dla $\mathbf{z}\in D_{M}.$ Istnienie płaszczyzny podpierającej wynika z tw. 3.8:

$M(\mathbf{z})\ge M(\mathbf{0})-\mu^{T}\mathbf{z},\qquad\mathbf{z}\in D_{M},$

dla pewnego $\mu\in\mathbb{R}^{m}.$ Udowodnimy teraz, że wszystkie współrzędne $\mu$ muszą być nieujemne. Przypuśćmy przeciwnie, tzn. $\mu _{i}<0$ dla pewnego $i\in\{ 1,\ldots,m\}.$ Ponieważ $\mathbf{0}\in\mathop{\rm int}D_{M}$ , to dla dostatecznie małego $a>0$ punkt ${\bar{\mathbf{z}}}=[0,\ldots,0,a,0,\ldots,0]^{T}$ , gdzie $a$ jest na $i$ -tej pozycji, należy do $D_{M}$ . Korzystając z ujemności $\mu _{i}$ mamy

$M({\bar{\mathbf{z}}})\ge M(\mathbf{0})-\mu _{i}a>M(\mathbf{0}).$

Z drugiej strony $W_{\mathbf{0}}\subseteq W_{{\bar{\mathbf{z}}}}$ , czyli $M({\bar{\mathbf{z}}})\le M(\mathbf{0}).$ To daje sprzeczność, czyli dowiedliśmy, że $\mu\in[0,\infty)^{m}.$

∎

Wektor $\mu$ nazywamy wektorem wrażliwości dla problemu (11.4). Z tw. 3.8 wynika, że jeśli funkcja $M$ jest różniczkowalna w punkcie $\mathbf{0}$ , to $\mu=-\big(DM(\mathbf{0})\big)^{T}.$ Zatem $\mu$ oznacza szybkość i kierunek zmian wartości minimalnej $f$ przy zmianie ograniczeń, podobnie jak w przypadku ograniczeń równościowych omawianych wcześniej w tym rozdziale.

Zbadajmy teraz relacje pomiędzy wektorem wrażliwości a punktem siodłowym i warunkiem pierwszego rzędu. Zauważmy, że powiązanie punktu siodłowego z wektorem wrażliwości nie wymaga wypukłości problemu optymalizacyjnego.

Twierdzenie 11.4

Jeśli $({\bar{\mathbf{x}}},{\bar{\mu}})$ jest punktem siodłowym funkcji Lagrange'a na zbiorze $\mathbb{X}\times[0,\infty)^{m}$ , to ${\bar{\mu}}$ jest wektorem wrażliwości (tzn. wyznacza płaszczyznę podpierającą). Teza ta nie wymaga założenia o wypukłości problemu optymalizacyjnego.
Załóżmy, że funkcje $f,g_{1},\ldots,g_{m}$ są różniczkowalne w ${\bar{\mathbf{x}}}$ , i wypukłe. Jeśli w ${\bar{\mathbf{x}}}$ spełniony jest warunek pierwszego rzędu z mnożnikami Lagrange'a ${\bar{\mu}}\in[0,\infty)^{m}$ , to ${\bar{\mu}}$ jest wektorem wrażliwości.

Dowód

(1) Oznaczmy przez $L_{z}(\mathbf{x},\mu)$ funkcję Langrange'a dla problemu zaburzonego. Wówczas

$L_{z}(\mathbf{x},\mu)=f(\mathbf{x})+\sum _{{i=1}}^{m}\mu _{i}\big(g_{i}(\mathbf{x})-z_{i}\big)=L(\mathbf{x},\mu)-\mu^{T}\mathbf{z}.$

Z faktu, że $({\bar{\mathbf{x}}},{\bar{\mu}})$ jest punktem siodłowym wynika, że

$M(\mathbf{0})=L({\bar{\mathbf{x}}},{\bar{\mu}})=\inf _{{\mathbf{x}\in\mathbb{X}}}L(\mathbf{x},{\bar{\mu}}).$

Zatem

$M(\mathbf{0})=\inf _{{\mathbf{x}\in\mathbb{X}}}L(\mathbf{x},{\bar{\mu}})=\inf _{{\mathbf{x}\in\mathbb{X}}}\big(L_{z}(\mathbf{x},{\bar{\mu}})+{\bar{\mu}}^{T}\mathbf{z}\big)=\inf _{{\mathbf{x}\in\mathbb{X}}}L_{z}(\mathbf{x},{\bar{\mu}})+{\bar{\mu}}^{T}\mathbf{z}.$

(11.8)

Zauważmy, że dla dowolnego $\mathbf{x}\in W_{\mathbf{z}}$ i $\mu\in[0,\infty)^{m}$ mamy $f(\mathbf{x})\ge L_{z}(\mathbf{x},\mu),$ czyli, w szczególności,

$M(\mathbf{z})=\inf _{{\mathbf{x}\in W_{\mathbf{z}}}}f(\mathbf{x})\ge\inf _{{\mathbf{x}\in W_{\mathbf{z}}}}L_{z}(\mathbf{x},{\bar{\mu}})\ge\inf _{{\mathbf{x}\in\mathbb{X}}}L_{z}(\mathbf{x},{\bar{\mu}}).$

Wstawiając tą zależność do (11.8) otrzymujemy

$M(\mathbf{0})\le M(\mathbf{z})+{\bar{\mu}}^{T}\mathbf{z}.$

(2) Z zadania 10.1 wynika, iż punkt $({\bar{\mathbf{x}}},{\bar{\mu}})$ jest punktem siodłowym funkcji Lagrange'a. Tezę dostajemy z pierwszej części niniejszego twierdzenia.

∎

11.3. Zadania

Ćwiczenie 11.1

Dla problemu

$\begin{cases}x_{1}^{2}+2x_{2}^{2}\to\min,&\\ x_{1}^{2}+x_{2}^{2}\le 0,&\\ \mathbf{x}_{1}\le 0.&\end{cases}$

Znaleźć $D_{M}$ .
Znaleźć wektor wrażliwości.
Znaleźć funkcję perturbacji.

Wskazówka:

Umieszczenie ograniczenia $x_{1}^{2}+x_{2}^{2}\le 0$ było intencją autora zadania.

Ćwiczenie 11.2

Znajdź funkcję perturbacji i wektor wrażliwości dla problemu

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

Ćwiczenie 11.3

Załóżmy, że w zadaniu optymalizacyjnym (11.4) funkcje $f$ i $g_{i}$ są klasy $C^{1}$ oraz $\mathbb{X}=\mathbb{R}^{n}$ . Czy funkcja perturbacji musi być wówczas klasy $C^{1}$ ? Udowodnij lub podaj kontrprzykład.

Ćwiczenie 11.4

Załóżmy, że w zadaniu optymalizacyjnym (11.4) funkcje $f$ i $g_{i}$ są ciągłe oraz $\mathbb{X}=\mathbb{R}^{n}$ . Czy funkcja perturbacji musi być wówczas ciągła? Udowodnij lub podaj kontrprzykład.

Ćwiczenie 11.5

Rozważmy problem producenta. Dysponuje on budżetem $b>0$ , który może spożytkować na wytworzenie dwóch rodzajów towarów. Pierwszy z towarów sprzedaje po cenie $p_{1}>0$ , zaś drugi – po cenie $p_{2}>0.$ Cena produkcji opisana jest funkcją $c(x_{1},x_{2})$ , gdzie wektor $\mathbf{x}$ opisuje wielkość produkcji każdego z towarów. Celem producenta jest maksymalizacja przychodów ze sprzedaży bez przekroczenia budżetu produkcyjnego:

$\begin{cases}p_{1}x_{1}+p_{2}x_{2}\to\max,&\\ c(x_{1},x_{2})\le b.&\end{cases}$

Podaj warunki konieczne istnienia rozwiązania powyższego problemu.
Załóżmy, że $c$ jest funkcją wypukłą. Jak należy zmodyfikować wielkość produkcji, jeśli budżet produkcyjny $b$ wrośnie nieznacznie?

Ćwiczenie 11.6

Rozważmy funkcję $f:[0,\infty)\to\mathbb{R}$ zadaną wzorem

$f(t)=\min _{{x,y\in\mathbb{R}}}\big\{ e^{{x^{2}-y}}+y^{2}-x:\ x^{2}+x^{4}-2xy+3y^{2}\le t\big\}.$

Uzasadnij, że funkcja $f$ jest dobrze określona i wypukła.

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

Optymalizacja II

Zagadnienia

11. Teoria wrażliwości

11.1. Ograniczenia równościowe

Twierdzenie 11.1

Dowód

11.2. Ograniczenia nierównościowe

Definicja 11.1

Twierdzenie 11.2

Dowód

Uwaga 11.1

Twierdzenie 11.3

Dowód

Twierdzenie 11.4

Dowód

11.3. Zadania

Ćwiczenie 11.1

Ćwiczenie 11.2

Ćwiczenie 11.3

Ćwiczenie 11.4

Ćwiczenie 11.5

Ćwiczenie 11.6