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 – 11. Teoria wrażliwości – MIM UW

Zagadnienia

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

\

  1. Zbiór D_{M} jest wypukły.

  2. Funkcja M:D_{M}\to\mathbb{R}\cup\{-\infty\} jest wypukła.

  3. 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

  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.

  2. 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.

  3. 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

  1. 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.

  2. 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}
  1. Znaleźć D_{M}.

  2. Znaleźć wektor wrażliwości.

  3. 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}
  1. Podaj warunki konieczne istnienia rozwiązania powyższego problemu.

  2. 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.

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.