Zagadnienia

7.1 Quasi-wypukłość
7.2 Maksymalizacja funkcji quasi-wypukłej
7.3 Warunki dostateczne
7.4 Zadania

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

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}).$
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}$ są 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ł.

Udowodnij, że $\forall\ \lambda\in A\quad g^{{\prime}}(\lambda)=0$ .
Wykaż, że $\hat{A}$ ma niepuste wnętrze.
Wykaż, że funkcja $f$ jest stała na $\hat{A}$ oraz ściśle większa od $g(0)$ .
Wykaż, że istnieje przedział otwarty $I\subset[0,1]$ taki że $I\cap A=\hat{A}$ .
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$ .

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

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}}}$ ?
Załóżmy, że warunki Kuhn'a-Tucker'a są spełnione w ${\bar{\mathbf{x}}}$ . Czy ${\bar{\mathbf{x}}}$ jest rozwiązaniem problemu optymalizacyjnego?
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$ ?