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 – 7. Funkcje quasi-wypukłe i warunki dostateczne – MIM UW

Zagadnienia

7. Funkcje quasi-wypukłe i warunki dostateczne

Mogliśmy już zaobserwować na kilku przykładach, że wypukłość znacznie ułatwia rozwiązywanie problemów optymalizacyjnych. W rozdziale 3 zauważyliśmy, że warunkiem koniecznym i dostatecznym minimum funkcji wypukłej jest zerowanie się pochodnej. Później wykazaliśmy, że identyczny warunek zachodzi dla większej rodziny funkcji: funkcji pseudowypukłych. W rozdziale 4 zajmowaliśmy się maksymalizacją funkcji wypukłej na zbiorze wypukłym i zwartym. Udowodniliśmy, że maksimum jest przyjmowane w jednym z punktów ekstremalnych tego zbioru. W tym rozdziale rozszerzymy rodzinę funkcji, dla których jest to prawdą; wprowadzimy własność quasi-wypukłości.

Patrząc na powyższą listę można się domyślać, że wypukłość może również pomagać przy rozwiązywaniu zadań z ograniczeniami nierównościowymi. Jeśli założymy, że funkcje g_{i}, opisujące ograniczenia nierównościowe, są wypukłe lub, ogólniej, quasi-wypukłe oraz funkcja f jest pseudowypukła, to spełnienie warunku pierwszego rzędu w pewnym punkcie {\bar{\mathbf{x}}} jest wystarczające, by stwierdzić jego optymalność. Dowód powyższego faktu przytoczymy pod koniec tego rozdziału.

7.1. Quasi-wypukłość

W tym podrozdziale rozszerzymy rodzinę funkcji, dla których maksimum znajduje się w punktach ekstremalnych dziedziny.

Definicja 7.1

Niech W\subset\mathbb{R}^{n} będzie zbiorem wypukłym, zaś f:W\to\mathbb{R}.

Funkcję f nazywamy quasi-wypukłą, jeśli dla dowolnych \mathbf{x},\mathbf{y}\in W i \lambda\in[0,1] mamy

f\big(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\big)\le\max\big(f(\mathbf{x}),f(\mathbf{y})\big).

Funkcję f nazywamy quasi-wklęsłą, jeśli funkcja (-f) jest quasi-wypukła, tzn. dla dowolnych \mathbf{x},\mathbf{y}\in W i \lambda\in[0,1] zachodzi

f\big(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\big)\ge\min\big(f(\mathbf{x}),f(\mathbf{y})\big).

Funkcję f nazywamy quasi-liniową, jeśli jest ona jednocześnie quasi-wypukła i quasi-wklęsła.

Rys. 7.1. Przykłady funkcji quasi-wypukłych i quasi-wklęsłych.
Rys. 7.2. Przykłady funkcji quasi-liniowych.

Na rys. 7.1 pokazane są przykłady jednowymiarowych funkcji quasi-wypukłych i quasi-wklęsłych. Zwróćmy uwagę na to, że funkcje takie nie muszą być ciągłe, nie mówiąc już o różniczkowalności. Ciekawym jest również uogólnienie rodziny funkcji afinicznych do funkcji quasi-liniowych, patrz rys. 7.2.

Przykład 7.1

Funkcja afiniczna jest quasi-liniowa. Rzeczywiście, niech f(\mathbf{x})=\mathbf{a}^{T}\mathbf{x}+b dla \mathbf{a}\in\mathbb{R}^{n} i b\in\mathbb{R}. Wówczas dla dowolnych \mathbf{x},\mathbf{y}\in W i \lambda\in[0,1] mamy

f\big(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\big)=\lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y}).

Prawa strona jest oczywiście nie mniejsza od minimum z f(\mathbf{x}) i f(\mathbf{y}) i nie większa od maksimum tych liczb, czyli f jest zarówno quasi-wypukła jak i quasi-wklęsła.

Przypomnijmy, że zbiorem poziomicowym funkcji f:W\to\mathbb{R} nazywamy zbiór

W_{\alpha}(f)=\big\{\mathbf{x}\in W:f(\mathbf{x})\le\alpha\big\},\qquad\alpha\in\mathbb{R}.
Twierdzenie 7.1

Niech f:W\to\mathbb{R}, gdzie W\subset\mathbb{R}^{n} wypukły. Wówczas funkcja f jest quasi-wypukła wtw, gdy zbiór poziomicowy W_{\alpha}(f) jest wypukły dla każdego \alpha\in\mathbb{R}.

Dowód

Załóżmy, że funkcja f jest quasi-wypukła i ustalmy \alpha\in\mathbb{R}. Niech \mathbf{x},\mathbf{y}\in W_{\alpha}(f). Wówczas f(\mathbf{x})\le\alpha i f(\mathbf{y})\le\alpha. Dla dowolnego \lambda\in(0,1) dostajemy

f\big(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\big)\le\max\big(f(\mathbf{x}),f(\mathbf{y})\big)\le\alpha.

Wnioskujemy stąd, że \lambda\mathbf{x}+(1-\lambda)\mathbf{y}\in W_{\alpha}(f), czyli W_{\alpha}(f) jest zbiorem wypukłym.

Załóżmy teraz, że W_{\alpha}(f) jest wypukły dla każdego \alpha\in\mathbb{R}. Ustalmy \mathbf{x},\mathbf{y}\in W oraz \lambda\in(0,1). Na mocy założenia zbiór W_{\alpha}(f) jest wypukły dla \alpha=\max\big(f(\mathbf{x}),f(\mathbf{y})\big). Wynika stąd, że \lambda\mathbf{x}+(1-\lambda)\mathbf{y}\in W_{\alpha}(f), czyli

f\big(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\big)\le\alpha=\max\big(f(\mathbf{x}),f(\mathbf{y})\big).
Uwaga 7.1

Analogiczne twierdzenie dla funkcji wypukłej, tw. 3.5, brzmiało: funkcja f jest wypukła wtw, gdy jej epigraf jest zbiorem wypukłym.

Wniosek 7.1

Funkcja wypukła jest quasi-wypukła.

Dowód

Wynika to wprost z twierdzeń 3.6 i 7.1.

Twierdzenie przeciwne nie jest prawdziwe. Poniżej podajemy przykład funkcji quasi-wypukłej, która nie jest wypukła.

Przykład 7.2

Funkcja f(x)=-e^{{x^{2}}}, dla x\ge 0, jest quasi-wypukła choć jest ściśle wklęsła. Dla \alpha\ge-1 zbiór W_{\alpha}(f)=[0,\infty), zaś dla \alpha<-1 mamy W_{\alpha}(f)=[\sqrt{\log(-\alpha)},\infty). Wszystkie te zbiory są wypukłe, więc na mocy twierdzenia 7.1 funkcja f jest quasi-wypukła. W podobny sposób możemy także pokazać, że funkcja f jest quasi-wklęsła, a zatem quasi-liniowa.

Przykład 7.3

Funkcja f(x)=-e^{x}, x\in\mathbb{R}, jest ściśle wklęsła a zarazem quasi-liniowa (czyli, między innymi, quasi-wypukła).

Przykład 7.4

Funkcja f(x)=x^{2} jest quasi-wypukła, lecz nie jest quasi-wklęsła. Quasi-wypukłość wynika z wypukłości f. Quasi-wklęsłość badamy rozpatrując zbiory poziomicowe funkcji (-f). Dla \alpha<0 mamy W_{\alpha}(-f)=(-\infty,-\sqrt{-\alpha}]\cup[\sqrt{-\alpha},\infty). Nie jest to zbiór wypukły, czyli funkcja (-f) nie jest quasi-wypukła.

Dowód poniższego lematu pozostawiamy jako zadanie.

Lemat 7.1

Funkcja f:W\to\mathbb{R}, W\subset\mathbb{R}^{n} wypukły, jest quasi-liniowa wtw, gdy jej obcięcie do dowolnego odcinka jest funkcją monotoniczną.

Na mocy tego lematu możemy od razu zauważyć, że funkcja z przykładu 7.2 jest quasi-liniowa.

Okazuje się, że istnieją funkcje quasi-wypukłe jednej zmiennej, które nie są ani wypukłe ani monotoniczne.

Przykład 7.5

Funkcja f(x)=e^{{-x^{2}}} jest quasi-wypukła. Mamy następujące zbiory poziomicowe w zależności od \alpha:

\displaystyle W_{\alpha}(f)=\emptyset,\qquad\alpha\le 0,
\displaystyle W_{\alpha}(f)=\big[-\sqrt{-\log(-\alpha)},\sqrt{-\log(-\alpha)}],\qquad\alpha\in(0,1],
\displaystyle W_{\alpha}(f)=\mathbb{R},\qquad\alpha>1.

Wszystkie te zbiory są wypukłe, czyli na mocy tw. 7.1 funkcja f jest quasi-wypukła.

Na koniec podamy przykład funkcji quasi-wypukłej wielu zmiennych, która nie jest wypukła.

Przykład 7.6

Funkcja f:[0,\infty)^{2}\to\mathbb{R} zadana wzorem f(x_{1},x_{2})=-x_{1}x_{2} jest quasi-wypukła. Jej zbiory poziomicowe dla \alpha\ge 0 są trywialne: W_{\alpha}(f)=[0,\infty)^{2}, zaś dla \alpha<0 mają formę przedstawioną na rysunku 7.3. Funkcja f nie jest ani wypukła ani wklęsła, gdyż jej hesjan ma wartości własne -1 i 1.

Rys. 7.3. Zbiór poziomicowy dla funkcji z przykładu 7.6.
Przykład 7.7

Niech \mathbf{a},\textbf{c}\in\mathbb{R}^{n} i b,d\in\mathbb{R}. Połóżmy D=\{\mathbf{x}\in\mathbb{R}^{n}:\mathbf{c}^{T}\mathbf{x}+d>0\}. Wówczas funkcja wymierna f:D\to\mathbb{R}

f(\mathbf{x})=\frac{\mathbf{a}^{T}\mathbf{x}+b}{\mathbf{c}^{T}\mathbf{x}+d}

jest quasi-liniowa. Dowód pozostawiamy jako ćwiczenie.

Zbadamy teraz własności różniczkowalnych funkcji quasi-wypukłych.

Twierdzenie 7.2

Niech f:W\to\mathbb{R} dla wypukłego zbioru W\subset\mathbb{R}^{n}.

  • I) Jeśli funkcja f jest quasi-wypukła i różniczkowalna w \mathbf{y}\in W, to

    \forall\ \mathbf{x}\in W\quad f(\mathbf{x})\le f(\mathbf{y})\implies Df(\mathbf{y})(x-y)\le 0.
  • II) Załóżmy, że funkcja f jest różniczkowalna w każdym punkcie W. Wówczas f jest quasi-wypukła wtw, gdy zachodzi następujący warunek:

    \forall\ \mathbf{x},\mathbf{y}\in W\quad f(\mathbf{x})\le f(\mathbf{y})\implies Df(\mathbf{y})(x-y)\le 0.
Uwaga 7.2
  1. Implikacja f(\mathbf{x})\le f(\mathbf{y})\implies Df(\mathbf{x})(\mathbf{x}-\mathbf{y})\le 0 ma równoważną postać:

    Df(\mathbf{y})(\mathbf{x}-\mathbf{y})>0\implies f(\mathbf{x})>f(\mathbf{y}).
  2. Jeśli funkcja f jest quasi-liniowa i f(\mathbf{x})=f(\mathbf{y}), to Df(\mathbf{y})(\mathbf{x}-\mathbf{y})=0.

Dowód tw. 7.2

(I): Ustalmy \mathbf{x},\mathbf{y}\in W, dla których zachodzi warunek f(\mathbf{x})\le f(\mathbf{y}). Dla każdego \lambda\in(0,1) mamy

f\big(\mathbf{y}+\lambda(\mathbf{x}-\mathbf{y})\big)=f\big(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\big)\le\max\big(f(\mathbf{x}),f(\mathbf{y})\big)=f(\mathbf{y}).

Wynika stąd, że

\frac{f\big(\mathbf{y}+\lambda(\mathbf{x}-\mathbf{y})\big)-f(\mathbf{y})}{\lambda}\le 0.

Z definicji pochodnej kierunkowej dostajemy

Df(\mathbf{y})(\mathbf{x}-\mathbf{y})=\lim _{{\lambda\downarrow 0}}\frac{f\big(\mathbf{y}+\lambda(\mathbf{x}-\mathbf{y})\big)-f(\mathbf{y})}{\lambda}\le 0.

Dowód (II) pozostawiamy jako niełatwe ćwiczenie.

Wiemy już, że funkcja wypukła jest quasi-wypukła. Okazuje się, że również funkcja pseudowypukła jest quasi-wypukła.

Twierdzenie 7.3

Jeśli f:W\to\mathbb{R} określona na zbiorze wypukłym W\subset\mathbb{R}^{n} jest pseudowypukła, to f jest quasi-wypukła.

Dowód

Zakładając, że funkcja f nie jest quasi-wypukła doprowadzimy do sprzeczności z pseudowypukłością. Weźmy więc punkty \mathbf{x},\mathbf{y}\in W oraz \lambda\in(0,1) spełniające

f\big(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\big)>\max\big(f(\mathbf{x}),f(\mathbf{y})\big).

Oznaczmy \mathbf{z}=\lambda\mathbf{x}+(1-\lambda)\mathbf{y}. Na mocy pseudowypukłości (wykorzystujemy tu warunek pseudowypukłości zapisany w uwadze 4.3) dostajemy:

\displaystyle f(\mathbf{x})<f(\mathbf{z})\implies Df(\mathbf{z})(\mathbf{x}-\mathbf{z})<0,
\displaystyle f(\mathbf{y})<f(\mathbf{z})\implies Df(\mathbf{z})(\mathbf{y}-\mathbf{z})<0.

Wektory (\mathbf{x}-\mathbf{z}) i (\mathbf{y}-\mathbf{z}) mają ten sam kierunek lecz przeciwne zwroty. Pochodna f w punkcie \mathbf{z} nie może być ujemna w obu kierunkach. Sprzeczność.

Twierdzenie odwrotne nie jest prawdziwe. Możemy jednak podać warunek dostateczny, przy którym funkcja quasi-wypukła jest pseudowypukła.

Twierdzenie 7.4

Niech f:W\to\mathbb{R} określona na zbiorze wypukłym otwartym W\subset\mathbb{R}^{n} będzie quasi-wypukła i ciągła. Jeśli f jest różniczkowalna w {\bar{\mathbf{x}}}\in W oraz Df({\bar{\mathbf{x}}})\ne\mathbf{0}^{T}, to f jest pseudowypukła w {\bar{\mathbf{x}}}.

Dowód

Musimy pokazać, że dla każdego \mathbf{y}\in W warunek Df({\bar{\mathbf{x}}})(\mathbf{y}-{\bar{\mathbf{x}}})\ge 0 pociąga f(\mathbf{y})\ge f({\bar{\mathbf{x}}}). Oznaczmy przez A przestrzeń afiniczną prostopadłą do Df({\bar{\mathbf{x}}}) i przechodzącą przez {\bar{\mathbf{x}}}:

A=\big\{\mathbf{x}\in\mathbb{R}^{n}:\  Df({\bar{\mathbf{x}}})\ (\mathbf{x}-{\bar{\mathbf{x}}})=0\big\}.

Z warunku, że Df({\bar{\mathbf{x}}})\ne\mathbf{0}^{T} wynika, że przestrzeń A ma wymiar n-1, czyli jest właściwą hiperpłaszczyzną w \mathbb{R}^{n}.

Zauważmy najpierw, że jeśli \mathbf{y}\in W\setminus A i Df({\bar{\mathbf{x}}})(\mathbf{y}-{\bar{\mathbf{x}}})\ge 0, to pochodna kierunkowa jest ściśle dodatnia: Df({\bar{\mathbf{x}}})(\mathbf{y}-{\bar{\mathbf{x}}})>0. Na mocy uwagi 7.2 wnioskujemy, że f(\mathbf{y})>f({\bar{\mathbf{x}}}), czyli to, co mieliśmy wykazać. Ustalmy teraz punkt \mathbf{y}\in W\cap A. Z otwartości W i z tego, że A jest hiperpłaszczyzną wynika, że istnieje ciąg punktów (\mathbf{y}_{n})\subset W\setminus A zmierzający do \mathbf{y} i taki że Df({\bar{\mathbf{x}}})\mathbf{y}_{n}>0. Zatem f(\mathbf{y}_{n})>f({\bar{\mathbf{x}}}). Korzystając z ciągłości funkcji f dostajemy f(\mathbf{y})\ge f({\bar{\mathbf{x}}}).

7.2. Maksymalizacja funkcji quasi-wypukłej

Jak zostało zasygnalizowane wcześniej, funkcja quasi-wypukła zachowuje się podobnie jak funkcja wypukła przy maksymalizacji na zbiorze wypukłym zwartym. Dla pełności przytoczymy dowód, który jest prawie identyczny jak dowód twierdzenia 4.5.

Twierdzenie 7.5

Niech f:W\to\mathbb{R} quasi-wypukła, ciągła, określona na wypukłym i zwartym zbiorze W\subset\mathbb{R}^{n}. Wówczas punkt ekstremalny zbioru W jest jednym z rozwiązań globalnych problemu

\begin{cases}f(\mathbf{x})\to\max,&\\
\mathbf{x}\in W.\end{cases}
Dowód

Funkcja ciągła osiąga swoje kresy na zbiorze zwartym. Powyższy problem maksymalizacyjny ma zatem rozwiązanie {\bar{\mathbf{x}}}\in W. Na mocy tw. 4.4 punkt {\bar{\mathbf{x}}} jest kombinacją wypukłą skończonej liczby punktów ekstremalnych, \mathbf{x}_{1},\ldots,\mathbf{x}_{m}, zbioru W, tzn.

{\bar{\mathbf{x}}}=a_{1}\mathbf{x}_{1}+a_{2}\mathbf{x}_{2}+\ldots+a_{m}\mathbf{x}_{m}

dla liczb a_{1},\ldots,a_{m}>0 takich że a_{1}+\ldots+a_{m}=1. Z quasi-wypukłości f dostajemy

f({\bar{\mathbf{x}}})\le\max\big(f(\mathbf{x}_{1}),\ldots,f(\mathbf{x}_{m})\big).

Ponieważ w punkcie {\bar{\mathbf{x}}} jest maksimum f na zbiorze W, to dla któregoś z punktów x_{i} zachodzi równość f(\mathbf{x}_{i})=f({\bar{\mathbf{x}}}).

7.3. Warunki dostateczne

Zajmiemy się problemem optymalizacyjnym, w którym występują zarówno ograniczenia nierównościowe jak i równościowe:

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

gdzie \mathbb{X}\subset\mathbb{R}^{n} jest zbiorem otwartym i f,g_{1},\ldots,g_{m},h_{1},\ldots,h_{l}:\mathbb{X}\to\mathbb{R}. A zatem zbiór punktów dopuszczalnych zadany jest następująco:

W=\big\{\mathbf{x}\in\mathbb{X}:g_{1}(\mathbf{x})\le 0,\ldots,g_{m}(\mathbf{x})\le 0,\  h_{1}(\mathbf{x})=0,\ldots,h_{l}(\mathbf{x})=0\big\}. (7.2)

Funkcje g_{i} nazywane są ograniczeniami nierównościowymi, funkcje h_{j}ograniczeniami równościowymi, zaś cały problem (7.1) nazywa się zadaniem optymalizacyjnym z ograniczeniami mieszanymi.

Podamy teraz warunki dostateczne, by punkt spełniający warunki pierwszego rzędu był rozwiązaniem globalnym.

Twierdzenie 7.6

Rozważmy problem optymalizacyjny w kanonicznej formie (7.1) i punkt {\bar{\mathbf{x}}}\in W. Załóżmy, że

  • funkcje g_{i}, i\notin I({\bar{\mathbf{x}}}) są ciągłe w {\bar{\mathbf{x}}}, funkcje g_{i}, i\in I({\bar{\mathbf{x}}}) są różniczkowalne w {\bar{\mathbf{x}}} i quasi-wypukłe,

  • funkcje h_{j}, j=1,\ldots,m, są quasi-liniowe i różniczkowalne w {\bar{\mathbf{x}}},

  • funkcja f jest pseudowypukła w {\bar{\mathbf{x}}}.

Jeśli istnieją stałe \mu\in[0,\infty)^{m} oraz \lambda\in\mathbb{R}^{l} spełniające warunek pierwszego rzędu:

\begin{cases}Df({\bar{\mathbf{x}}})+\sum _{{i\in I({\bar{\mathbf{x}}})}}\mu _{i}Dg_{i}({\bar{\mathbf{x}}})+\sum _{{j=1}}^{l}\lambda _{j}Dh_{j}({\bar{\mathbf{x}}})=\mathbf{0}^{T},&\\
\mu _{i}g_{i}({\bar{\mathbf{x}}})=0,\quad i=1,\ldots,m,&\end{cases} (7.3)

to punkt {\bar{\mathbf{x}}} jest rozwiązaniem globalnym.

Dowód

Ustalmy dowolny punkt dopuszczalny \mathbf{x}\in W i pomnóżmy obie strony pierwszego równania w warunku (7.3) przez (\mathbf{x}-{\bar{\mathbf{x}}}):

Df({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})+\sum _{{i\in I({\bar{\mathbf{x}}})}}\mu _{i}Dg_{i}({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})+\sum _{{j=1}}^{l}\lambda _{j}Dh_{j}({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})=0.

Na mocy tw. 7.2 mamy Dh_{j}({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})=0 dla każdego j, bo h_{j}(\mathbf{x})=h_{j}({\bar{\mathbf{x}}})=0. To samo twierdzenie implikuje, że Dg_{i}({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})\le 0 dla i\in I({\bar{\mathbf{x}}}), ponieważ 0=g_{i}({\bar{\mathbf{x}}})\ge g_{i}(\mathbf{x}). Korzystając z tych obserwacji wnioskujemy z powyższego równania, że

Df({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})\ge 0.

Z definicji funkcji pseudowypukłej, f(\mathbf{x})\ge f({\bar{\mathbf{x}}}). Punkt \mathbf{x} wybraliśmy dowolnie spośród punktów dopuszczalnych, a zatem {\bar{\mathbf{x}}} jest rozwiązaniem globalnym.

Uwaga 7.3

Jeśli założenia twierdzenia 7.6 są spełnione lokalnie, na pewnym otoczeniu {\bar{\mathbf{x}}}, to {\bar{\mathbf{x}}} jest rozwiązaniem lokalnym.

Uwaga 7.4

Na mocy twierdzenia 7.4 zamiast zakładać pseudowypukłość funkcji f w punkcie {\bar{\mathbf{x}}} możemy założyć jej ciągłość na \mathbb{X}, quasi-wypukłość oraz warunek Df({\bar{\mathbf{x}}})\ne\mathbf{0}^{T}. Jest to jedna z form warunku koniecznego zaprezentowana w pracy Arrowa i Enthovena z 1961 roku [1].

Kenneth Joseph Arrow jest amerykańskim ekonomistą. Wspólnie z John'em Hicks'em otrzymał nagrodę Nobla z ekonomii w 1972 roku.

7.4. Zadania

Ćwiczenie 7.1

Udowodnij, że funkcja f:[a,b]\to\mathbb{R} jest quasi-liniowa wtw, gdy jest monotoniczna.

Ćwiczenie 7.2

Niech f:W\to\mathbb{R}, W\subset\mathbb{R}^{n} wypukły. Udowodnij następujący fakt: funkcja f jest quasi-liniowa wtw, gdy jej obcięcie do każdego odcinka zawartego w W jest funkcją monotoniczną.

Ćwiczenie 7.3

Wykaż, że jeśli funkcja f:W\to\mathbb{R}, W\subset\mathbb{R}^{n} wypukły, jest quasi-wypukła oraz g:\mathbb{R}\to\mathbb{R} jest niemalejąca, to funkcja g\circ f jest quasi-wypukła. Jeśli natomiast funkcja g jest nierosnąca, to g\circ f jest quasi-wklęsła.

Ćwiczenie 7.4

Niech f:(a,b)\to\mathbb{R} będzie funkcją jednej zmiennej. Wykaż, że f jest quasi-wypukła wtw, gdy zachodzi jeden z warunków:

  • f jest monotoniczna,

  • istnieje \bar{x}\in(a,b) taki że f jest nierosnąca dla x<\bar{x} oraz niemalejąca dla x>\bar{x}.

Ćwiczenie 7.5

Dla jakich wartości parametrów a,b,c,d\in\mathbb{R} funkcja f(x)=ax^{3}+bx^{2}+cx+d jest quasi-wypukła?

Ćwiczenie 7.6

Sprawdź, że funkcja f:[0,\infty)^{2}\to\mathbb{R} zadana wzorem f(x_{1},x_{2})=e^{{-x_{1}}}x_{2} jest quasi-wklęsła.

Ćwiczenie 7.7

Znajdź przykład pokazujący, że suma funkcji quasi-wypukłych nie musi być quasi-wypukła.

Ćwiczenie 7.8

Niech \mathbf{a},\textbf{c}\in\mathbb{R}^{n} i b,d\in\mathbb{R}. Wykaż, że funkcja wymierna

f(\mathbf{x})=\frac{\mathbf{a}^{T}\mathbf{x}+b}{\mathbf{c}^{T}\mathbf{x}+d}

jest quasi-liniowa na swojej dziedzinie D=\{\mathbf{x}\in\mathbb{R}^{n}:\mathbf{c}^{T}\mathbf{x}+d>0\}.

Ćwiczenie 7.9

Niech h:\mathbb{R}^{n}\to\mathbb{R} będzie funkcją liniową i W=\{\mathbf{x}\in\mathbb{R}^{n}:\  h(\mathbf{x})>0\}. Wykaż, że jeśli f:W\to\mathbb{R} jest wypukła, to funkcja g(\mathbf{x})=f(\mathbf{x})/h(\mathbf{x}) dla \mathbf{x}\in W jest quasi-wypukła.

Ćwiczenie 7.10

Udowodnij, że jeśli (g_{\alpha})_{{\alpha\in I}} jest rodziną funkcji quasi-wypukłych, w:I\to\mathbb{R} jest funkcją nieujemną, to h(\mathbf{x})=\sup _{{\alpha\in I}}w(\alpha)g_{\alpha}(\mathbf{x}) jest quasi-wypukła, o ile jest skończona dla każdego \mathbf{x}.

Ćwiczenie 7.11

Niech A\subset\mathbb{R}^{n}, C\subset\mathbb{R}^{m} będą zbiorami wypukłymi, zaś f:A\times C\to\mathbb{R} będzie quasi-wypukła. Wykaż, że h(\mathbf{x})=\inf _{{c\in C}}f(\mathbf{x},c) jest quasi-wypukła.

Ćwiczenie 7.12

Niech W\subset\mathbb{R}^{n} zbiór wypukły, f:W\to\mathbb{R}. Udowodnij, że jeśli f quasi-liniowa, to zbiór \{\mathbf{x}\in W:f(\mathbf{x})=\alpha\} jest wypukły dla dowolnego \alpha\in\mathbb{R}.

Ćwiczenie 7.13

Niech f:\mathbb{R}^{n}\to\mathbb{R}, ciągła. Udowodnij następującą równoważność: f jest quasi-liniowa wtw, gdy f(\mathbf{x})=g(\mathbf{a}^{T}\mathbf{x}) dla funkcji monotonicznej, ciągłej g:\mathbb{R}\to\mathbb{R} oraz wektora \mathbf{a}\in\mathbb{R}^{n}.

Wykaż, że powyższa równoważność nie musi być prawdziwa, gdy funkcję f rozważamy na wypukłym podzbiorze właściwym \mathbb{R}^{n}.

Ćwiczenie 7.14

Przeprowadź dowód punktu (II) twierdzenia 7.2.

Wskazówka: 

Dla dowolnych punktów \mathbf{x},\mathbf{y}\in W uporządkowanych tak, że f(\mathbf{x})\le f(\mathbf{y}) rozważ funkcję

g(\lambda)=f\big(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\big),\qquad\lambda\in[0,1]

oraz zbiór

A=\big\{\lambda\in[0,1]:\  g(\lambda)>g(0)\big\}.

Pokaż, że jeśli zbiór ten jest niepusty, to prowadzi to do sprzeczności z ciągłością funkcji f. Oznacz przez \hat{A} spójną składową A, tzn. przedział.

  1. Udowodnij, że \forall\ \lambda\in A\quad g^{{\prime}}(\lambda)=0.

  2. Wykaż, że \hat{A} ma niepuste wnętrze.

  3. Wykaż, że funkcja f jest stała na \hat{A} oraz ściśle większa od g(0).

  4. Wykaż, że istnieje przedział otwarty I\subset[0,1] taki że I\cap A=\hat{A}.

  5. Zauważ sprzeczność z ciągłością funkcji f, bo f|_{{\hat{A}}}>f|_{{I\setminus\hat{A}}}.

Ćwiczenie 7.15

Wykaż, że funkcja quasi-wypukła (niekoniecznie ciągła) określona na zbiorze wielościennym zwartym przyjmuje swoje maksimum globalne w jednym z punktów ekstremalnych.

Ćwiczenie 7.16

Rozważmy problem optymalizacyjny (7.1). Niech {\bar{\mathbf{x}}} będzie punktem dopuszczalnym, w którym spełnione są warunki pierwszego rzędu z mnożnikami Lagrange'a \mu i \lambda.

  1. Załóżmy, że f jest pseudowypukła w {\bar{\mathbf{x}}}, zaś funkcja

    \phi(\mathbf{x})=\sum _{{i=1}}^{m}\mu _{i}g_{i}(\mathbf{x})+\sum _{{j=1}}^{l}\lambda _{j}h_{j}(\mathbf{x})

    jest quasi-wypukła w {\bar{\mathbf{x}}}. Udowodnij, że {\bar{\mathbf{x}}} jest rozwiązaniem globalnym.

  2. Przypomnijmy, że L(\mathbf{x},\mu,\lambda) jest funkcją Lagrange'a. Udowodnij, że jeśli \mathbf{x}\mapsto L(\mathbf{x},\mu,\lambda) jest pseudowypukła w {\bar{\mathbf{x}}}, to {\bar{\mathbf{x}}} jest rozwiązaniem globalnym.

  3. Wykaż, że warunki zawarte w powyższych punktach nie są równoważne. Znajdź zależności pomiędzy nimi a założeniami twierdzenia 7.6.

Ćwiczenie 7.17

Niech {\bar{\mathbf{x}}} będzie rozwiązaniem globalnym problemu optymalizacyjnego (7.1). Załóżmy, że g_{k}({\bar{\mathbf{x}}})<0 dla pewnego k\in\{ 1,\ldots,m\}. Wykaż, że jeśli ograniczenie g_{k}(\mathbf{x})\le 0 zostanie usunięte, to {\bar{\mathbf{x}}} może nie być nawet lokalnym rozwiązaniem otrzymanego problemu. Udowodnij natomiast, że jeśli funkcja g_{k} jest ciągła w {\bar{\mathbf{x}}}, to po usunięciu tego ograniczenia {\bar{\mathbf{x}}} pozostaje rozwiązaniem lokalnym.

Ćwiczenie 7.18

Dla jakich wartości parametru \alpha\in\mathbb{R} problem

\begin{cases}x_{1}+x_{2}+\alpha(x_{1}-1)^{2}\to\min,&\\
x_{1}-x_{2}\le 0,&x_{1}\ge 0\end{cases}

ma rozwiązanie? Jak zależy ono od wartości \alpha?

Ćwiczenie 7.19

Rozwiąż zadanie optymalizacyjne:

\begin{cases}\mathbf{b}^{T}\mathbf{x}\to\min,&\\
\|\mathbf{x}\| _{p}\le 1,&\end{cases}

gdzie \mathbf{b}\in\mathbb{R}^{n}, zaś \|\mathbf{x}\| _{p}=\big(\sum _{{i=1}}^{n}|x_{i}|^{p}\big)^{{1/p}} i p>1.

Ćwiczenie 7.20

Niech u:[0,\infty)^{n}\to\mathbb{R} będzie funkcją quasi-wklęsłą o pochodnej Du(\mathbf{x})>\mathbf{0} dla każdego \mathbf{x}. Ustalmy liczbę w>0 i wektor \mathbf{p}\in(0,\infty)^{n}. Rozważmy problem optymalizacyjny

\begin{cases}u(\mathbf{x})\to\max,&\\
\sum _{{i=1}}^{n}p_{i}x_{i}\le w,&\\
\mathbf{x}\ge\mathbf{0}.&\end{cases}

Wektor \mathbf{p} pełni rolę cen produktów, \mathbf{x} ich ilości, w jest wielkością budżetu, zaś funkcja u ocenia satysfakcję z decyzji zakupowej \mathbf{x}.

Zapisz warunki Kuhn'a-Tucker'a dla powyższego problemu.

  1. Załóżmy, że {\bar{\mathbf{x}}} jest rozwiązaniem. Czy będzie wówczas istniał wektor mnożników Lagrange'a, dla którego warunki Kuhn'a-Tucker'a są spełnione w {\bar{\mathbf{x}}}?

  2. Załóżmy, że warunki Kuhn'a-Tucker'a są spełnione w {\bar{\mathbf{x}}}. Czy {\bar{\mathbf{x}}} jest rozwiązaniem problemu optymalizacyjnego?

  3. Niech {\bar{\mathbf{x}}} będzie rozwiązaniem. Co możesz powiedzieć o związku pomiędzy p_{i}/p_{j} a u^{{\prime}}_{i}({\bar{\mathbf{x}}})/u^{{\prime}}_{j}({\bar{\mathbf{x}}}), gdy

    • \bar{x}_{i}>0 i \bar{x}_{j}>0?

    • \bar{x}_{i}=0 i \bar{x}_{j}>0?

    • \bar{x}_{i}=0 i \bar{x}_{j}=0?

Ćwiczenie 7.21

Rozwiąż problem optymalizacyjny

\begin{cases}\sqrt{x}+y\to\max,&\\
px+y\le I,&\\
x,y\ge 0,&\end{cases}

gdzie p,I>0 są parametrami.

Ćwiczenie 7.22

Niech A będzie macierzą symetryczną n\times n dodatnio określoną, zaś b\in(0,\infty). Rozwiąż problem optymalizacyjny:

\begin{cases}-\log\det X\to\min,&\\
tr(AX)\le b,&\end{cases}

w zbiorze macierzy X\in\mathbb{R}^{{n\times n}} symetrycznych i dodatnio określonych.

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.