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 – 3. Funkcje wypukłe – MIM UW

Zagadnienia

3. Funkcje wypukłe

3.1. Zbiory wypukłe i twierdzenia o oddzielaniu

Przypomnijmy, za def. 2.2, definicję zbioru wypukłego: zbiór W\subset\mathbb{R}^{n} jest wypukły, jeśli

\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\in W

dla każdych \mathbf{x},\mathbf{y}\in W i każdego \lambda\in[0,1]. Równoważnie można wypukłość zdefiniować za pomocą m-tek punktów:

Lemat 3.1

Zbiór W\subset\mathbb{R}^{n} jest wypukły wtw, gdy dla dowolnego m\ge 2, punktów \mathbf{x}_{1},\ldots,\mathbf{x}_{m}\in W oraz liczb a_{1},\ldots,a_{m}\ge 0, takich że a_{1}+\ldots+a_{m}=1 mamy

a_{1}\mathbf{x}_{1}+a_{2}\mathbf{x}_{2}+\ldots+a_{m}\mathbf{x}_{m}\in W.

Dowód tego lematu pozostawiamy jako ćwiczenie (patrz ćw. 3.3). Udowodnimy natomiast geometryczną własność zbiorów wypukłych, która przyda nam się wielokrotnie.

Lemat 3.2

Niech W\subset\mathbb{R}^{n} będzie zbiorem wypukłym o niepustym wnętrzu. Wówczas:

  • I) Dla dowolnego \mathbf{x}\in W oraz \mathbf{x}_{0}\in\mathop{\rm int}W odcinek łączący \mathbf{x}_{0} z \mathbf{x}, z pominięciem punktu \mathbf{x}, należy do wnętrza W:

    \lambda\mathbf{x}_{0}+(1-\lambda)\mathbf{x}\in\mathop{\rm int}W,\qquad\forall\  0\le\lambda<1.
  • II) W\subset\mathop{\rm cl}(\mathop{\rm int}W).

Dowód

Weźmy punkty \mathbf{x}_{0} i \mathbf{x} jak w założeniach lematu. Z otwartości \mathop{\rm int}W wynika, że istnieje kula B(\mathbf{x}_{0},\varepsilon)\subset\mathop{\rm int}W. Połączmy punkty tej kuli z punktem \mathbf{x}. Dostaniemy ,,stożek” o wierzchołku \mathbf{x} i podstawie B(\mathbf{x}_{0},\varepsilon) (patrz rys. 3.1). Stożek ten leży w całości w W. Jego wnętrze zawiera odcinek od \mathbf{x}_{0} do \mathbf{x} bez końca \mathbf{x}. Kończy to zatem dowód (I). Dowód (II) wynika natychmiast z (I).

Rys. 3.1. Stożek o wierzchołku \mathbf{x} i podstawie B({\bar{\mathbf{x}}},\varepsilon).

Przypomnijmy bez dowodu twierdzenia o oddzielaniu zbiorów wypukłych w przestrzeniach \mathbb{R}^{n} (dowody tych twierdzeń można znaleźć np. w rozdziale 2.4 monografii Bazaraa, Sherali, Shetty [3] lub w rozdziale 11 monografii Rockafellar'a [11]).

Twierdzenie 3.1 (Słabe twierdzenie o oddzielaniu)

Niech U,V\subset\mathbb{R}^{n} będą niespustymi zbiorami wypukłymi, takimi że U\cap V=\emptyset. Wówczas istnieje hiperpłaszczyzna rozdzielająca U od V, tzn. istnieje niezerowy wektor \mathbf{a}\in\mathbb{R}^{n} spełniający

\mathbf{a}^{T}\mathbf{x}\le\mathbf{a}^{T}\mathbf{y},\qquad\mathbf{x}\in U,\ \mathbf{y}\in V.

Korzystając z ciągłości odwzorowania liniowego \mathbf{x}\mapsto\mathbf{a}^{T}\mathbf{x} dostajemy bardzo przydatny wniosek, który również będziemy nazywać słabym twierdzeniem o oddzielaniu.

Wniosek 3.1

Niech U,V\subset\mathbb{R}^{n} będą niepustymi zbiorami wypukłymi, takimi że \mathop{\rm int}U\ne\emptyset i (\mathop{\rm int}U)\cap V=\emptyset. Wówczas istnieje hiperpłaszczyzna rozdzielająca U od V, tzn. istnieje niezerowy wektor \mathbf{a}\in\mathbb{R}^{n} spełniający

\mathbf{a}^{T}\mathbf{x}\le\mathbf{a}^{T}\mathbf{y},\qquad\mathbf{x}\in U,\ \mathbf{y}\in V.
Twierdzenie 3.2 (Mocne twierdzenie o oddzielaniu)

Niech U,V\subset\mathbb{R}^{n} będą niepustymi zbiorami wypukłymi domkniętymi, U zwarty i U\cap V=\emptyset. Wówczas istnieje hiperpłaszczyzna ściśle rozdzielająca U od V, tzn. istnieje niezerowy wektor \mathbf{a}\in\mathbb{R}^{n} spełniający

\sup _{{\mathbf{x}\in U}}\mathbf{a}^{T}\mathbf{x}<\inf _{{\mathbf{y}\in V}}\mathbf{a}^{T}\mathbf{y}.
Uwaga 3.1

Powyższe twierdzenia mają intuicyjną geometryczną interpretację. Dwa rozłączne zbiory wypukłe mogą być rozdzielone hiperpłaszczyzną w ten sposób, iż jeden z nich leży w domkniętej półprzestrzeni po jednej stronie hiperpłaszczyzny, podczas gdy drugi leży po przeciwnej stronie tejże hiperpłaszczyzny. W słabym twierdzeniu nie możemy zagwarantować, iż któryś ze zbiorów leży we wnętrzu półprzestrzeni, tzn. ma puste przecięcie z hiperpłaszczyzną. Silna wersja właśnie to gwarantuje.

Hiperpłaszczyzna, o której mowa w twierdzeniach zadana jest wzorem:

\{\mathbf{x}\in\mathbb{R}^{n}:\mathbf{a}^{T}\mathbf{x}=\alpha\},

gdzie \alpha=\sup _{{\mathbf{x}\in U}}\mathbf{a}^{T}\mathbf{x}. Nie musi to być jedyna hiperpłaszczyzna spełniająca warunki słabego/mocnego rozdzielania.

Twierdzenia o oddzielaniu będziemy dowodzić w przeciwnej kolejności niż są podane. Okazuje się bowiem, że łatwiej udowodnić twierdzenie mocne. Później w dowodzie twierdzenia słabego skorzystamy z mocnego oddzielania zbiorów wypukłych.

Dowód twierdzenia 3.2

Określmy funkcję d:U\times V\to\mathbb{R} wzorem d(\mathbf{x},\mathbf{y})=\|\mathbf{x}-\mathbf{y}\|. Z ograniczoności zbioru U wynika, że d jest funkcją koercywną; zbieżność do nieskończoności może się tylko odbywać po argumencie ze zbioru V. Na mocy tw. 1.2 funkcja d jako ciągła i koercywna określona na zbiorze domkniętym U\times V osiąga swoje minimum w pewnym punkcie (\mathbf{x}_{0},\mathbf{y}_{0})\in U\times V. Z faktu, że U\cap V=\emptyset wynika, że \mathbf{x}_{0}\ne\mathbf{y}_{0}. Połóżmy \mathbf{a}=\mathbf{y}_{0}-\mathbf{x}_{0}. Pokażemy, że jest to szukany wektor z tezy twierdzenia.

Udowodnimy, że \mathbf{a}^{T}\mathbf{y}\ge\mathbf{a}^{T}\mathbf{y}_{0}. Niech \mathbf{y}\in V, \mathbf{y}\ne\mathbf{y}_{0}. Zdefiniujmy funkcję

g(t)=\Big(d\big(\mathbf{x}_{0},\mathbf{y}_{0}+t(\mathbf{y}-\mathbf{y}_{0})\big)\Big)^{2},\qquad t\in\mathbb{R}.

Rozwijając dostajemy

g(t)=\|\mathbf{y}_{0}-\mathbf{x}_{0}\|^{2}+2t(\mathbf{y}_{0}-\mathbf{x}_{0})^{T}(\mathbf{y}-\mathbf{y}_{0})+t^{2}(\mathbf{y}-\mathbf{y}_{0})^{T}(\mathbf{y}-\mathbf{y}_{0}).

Funkcja ta jest różniczkowalna dla t\in\mathbb{R} i g(0)\le g(t) dla t\in[0,1] (na mocy wypukłości V i definicji \mathbf{y}_{0}). Zatem g^{{\prime}}(0)\ge 0, czyli

(\mathbf{y}_{0}-\mathbf{x}_{0})^{T}(\mathbf{y}-\mathbf{y}_{0})\ge 0.

Nierówność ta jest równoważna \mathbf{a}^{T}\mathbf{y}\ge\mathbf{a}^{T}\mathbf{y}_{0}.

Podobnie pokazujemy, że \mathbf{a}^{T}\mathbf{x}\le\mathbf{a}^{T}\mathbf{x}_{0} dla \mathbf{x}\in U. Do zakończenia dowodu wystarczy sprawdzić, że \mathbf{a}^{T}\mathbf{y}_{0}>\mathbf{a}^{T}\mathbf{x}_{0}. Ta nierówność jest równoważna \|\mathbf{a}\|^{2}>0, co zachodzi, gdyż \mathbf{x}_{0}\ne\mathbf{y}_{0}.

Dowód twierdzenia 3.1

Rozważmy zbiór C=V-U=\{\mathbf{y}-\mathbf{x}:\ \mathbf{x}\in U,\ \mathbf{y}\in V\}. Zbiór ten jest wypukły i \mathbf{0}\notin C. Równoważne tezie twierdzenia jest znalezienie wektora niezerowego \mathbf{a}\in\mathbb{R}^{n} oddzielającego C od \{\mathbf{0}\}, tzn. takiego że \mathbf{a}^{T}\mathbf{x}\ge 0 dla \mathbf{x}\in C.

Zdefiniujmy zbiory

A_{\mathbf{x}}=\{\mathbf{a}\in\mathbb{R}^{n}:\ \|\mathbf{a}\|=1,\ \mathbf{a}^{T}\mathbf{x}\ge 0\}.

Wystarczy pokazać, że \bigcap _{{\mathbf{x}\in C}}A_{\mathbf{x}}\ne\emptyset. Będziemy rozumować przez sprzeczność. Załóżmy więc, że \bigcap _{{\mathbf{x}\in C}}A_{\mathbf{x}}=\emptyset. Niech B_{\mathbf{x}}=S\setminus A_{\mathbf{x}}, gdzie S jest sferą jednostkową S=\{\mathbf{a}\in\mathbb{R}^{n}:\ \|\mathbf{a}\|=1\}. Zbiory B_{\mathbf{x}}, \mathbf{x}\in C, są otwartymi podzbiorami zbioru zwartego S. Z założenia, że przecięcie ich dopełnień w S jest puste, wynika, że rodzina \{ B_{\mathbf{x}}\} _{{\mathbf{x}\in C}} jest pokryciem otwartym S. Na mocy zwartości S istnieje podpokrycie skończone B_{{\mathbf{x}_{1}}},\ldots,B_{{\mathbf{x}_{k}}}, czyli

A_{{\mathbf{x}_{1}}}\cap\cdots\cap A_{{\mathbf{x}_{k}}}=\emptyset.

Połóżmy

\hat{C}=\mathop{\rm conv}\{\mathbf{x}_{1},\ldots,\mathbf{x}_{k}\}=\{\sum _{{i=1}}^{k}\lambda _{i}\mathbf{x}_{i}:\ \lambda _{1},\ldots,\lambda _{k}\ge 0,\ \sum _{{i=1}}^{k}\lambda _{i}=1\}.

Zbiór \hat{C} jest wypukły i domknięty oraz \hat{C}\subset C. Stąd \mathbf{0}\notin\hat{C} i na mocy mocnego twierdzenia o oddzielaniu zastosowanego do \hat{C} i \{\mathbf{0}\} istnieje wektor \mathbf{a}\in\mathbb{R}^{n}\setminus\{\mathbf{0}\}, taki że

\mathbf{a}^{T}\mathbf{x}>0,\qquad\mathbf{x}\in\hat{C}.

W szczególności, \mathbf{a}^{T}\mathbf{x}_{1}>0,\ldots,\mathbf{a}^{T}\mathbf{x}_{k}>0, czyli \frac{\mathbf{a}}{\|\mathbf{a}\|}\in A_{{\mathbf{x}_{i}}}, i=1,\ldots,k, co przeczy założeniu, że przecięcie \bigcap _{{i=1}}^{k}A_{{\mathbf{x}_{i}}}=\emptyset.

3.2. Definicja funkcji wypukłej

Definicja 3.1

Funkcję f:W\to\mathbb{R}, gdzie W\subset\mathbb{R}^{n} wypukły, nazwiemy:

  • wypukłą, jeśli dla każdego \mathbf{x},\mathbf{y}\in W i \lambda\in(0,1) zachodzi

    f\big(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\big)\le\lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y}).
  • ściśle wypukłą, jeśli dla każdego \mathbf{x},\mathbf{y}\in W, \mathbf{x}\ne\mathbf{y} i \lambda\in(0,1) zachodzi

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

Funkcja f jest (ściśle) wklęsła, jeśli (-f) jest (ściśle) wypukła.

Okazuje się, że wystarczy rozważać \lambda=1/2 w definicji wypukłości. Zacytujemy najpierw silny wynik noszący nazwisko Sierpińskiego, a później łatwiejszy, który dowiedziemy:

Twierdzenie 3.3

Jeśli funkcja f:W\to\mathbb{R}, gdzie W\subset\mathbb{R}^{n} wypukły, jest mierzalna w sensie Lebesgue'a oraz spełnia

f\Big(\frac{\mathbf{x}+\mathbf{y}}{2}\Big)\le\frac{f(\mathbf{x})+f(\mathbf{y})}{2},

to jest wypukła.

Dowód

Patrz dowód tw. Sierpińskiego w [7, str. 12].

My udowodnimy słabszy wynik; założymy mianowicie ciągłość f.

Twierdzenie 3.4

Jeśli funkcja f:W\to\mathbb{R}, gdzie W\subset\mathbb{R}^{n} wypukły, jest ciągła oraz spełnia

f\Big(\frac{\mathbf{x}+\mathbf{y}}{2}\Big)\le\frac{f(\mathbf{x})+f(\mathbf{y})}{2},

to jest wypukła.

Dowód

Pokażemy najpierw, przez indukcję po k, że nierówność wypukłości zachodzi dla \lambda postaci p/2^{k}, p=0,1,\ldots,2^{k}. Własność ta jest spełniona dla k=1 z założenia twierdzenia. Przeprowadźmy teraz krok indukcyjny. Załóżmy, że nierówność jest prawdziwa dla k. Weźmy p,q>0 całkowite, o sumie p+q=2^{{k+1}}. Załóżmy p\le q. Wówczas p\le 2^{k}\le q i możemy napisać:

\mathbf{z}=\frac{p}{2^{{k+1}}}\mathbf{x}+\frac{q}{2^{{k+1}}}\mathbf{y}=\frac{1}{2}\bigg(\frac{p}{2^{k}}\mathbf{x}+\frac{q-2^{k}}{2^{k}}\mathbf{y}+\mathbf{y}\bigg).

Mamy zatem

f(\mathbf{z})\le\frac{1}{2}f\Big(\frac{p}{2^{k}}\mathbf{x}+\frac{q-2^{k}}{2^{k}}\mathbf{y}\Big)+\frac{1}{2}f(\mathbf{y})\le\frac{1}{2}\frac{p}{2^{k}}f(\mathbf{x})+\frac{1}{2}\frac{q-2^{k}}{2^{k}}f(\mathbf{y})+\frac{1}{2}f(\mathbf{y})=\frac{p}{2^{{k+1}}}f(\mathbf{x})+\frac{q}{2^{{k+1}}}f(\mathbf{y}).

Pierwsza nierówność wynika z założenia twierdzenia, zaś druga – z założenia indukcyjnego. Dowód w przypadku p\ge q jest symetryczny, ze zmienioną rolą \mathbf{x} i \mathbf{y}.

Zbiór punktów postaci p/2^{k}, k=1,2,\ldots, jest gęsty w odcinku (0,1). Z ciągłości funkcji f otrzymujemy nierówność wypukłości dla dowolnego \lambda\in(0,1).

Przykład 3.1
  • Funkcja afiniczna f(\mathbf{x})=\mathbf{a}^{T}\mathbf{x}+b jest wypukła i wklęsła.

  • Norma w \mathbb{R}^{n} jest funkcją wypukłą. Wystarczy skorzystać z nierówności trójkąta.

  • Odległość punktu od zbioru definiujmy następująco d(\mathbf{x},W)=\inf _{{\mathbf{y}\in W}}\|\mathbf{x}-\mathbf{y}\|. Odległość punktu od zbioru wypukłego jest funkcją wypukłą: f(\mathbf{x})=d(\mathbf{x},W) dla pewnego zbioru wypukłego W\subset\mathbb{R}^{n}.

3.3. Własności funkcji wypukłych

W tym rozdziale zakładamy, iż funkcja f:W\to R jest określona na niepustym wypukłym podzbiorze W\subset\mathbb{R}^{n}.

Definicja 3.2

Epigrafem funkcji f:W\to\mathbb{R} nazywamy zbiór

\mathop{\rm epi}(f)=\big\{(\mathbf{x},z)\in W\times\mathbb{R}:z\ge f(\mathbf{x})\big\}.
Definicja 3.3

Zbiorem poziomicowym funkcji f:W\to\mathbb{R} nazywamy

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

Funkcja f jest wypukła wtedy i tylko wtedy, gdy jej epigraf \mathop{\rm epi}(f) jest wypukłym podzbiorem \mathbb{R}^{{n+1}}.

Twierdzenie 3.6

Jeśli funkcja f jest wypukła, to zbiór poziomicowy W_{\alpha}(f) jest wypukły dla dowolnego \alpha.

Dowód powyższych twierdzeń pozostawiamy czytelnikowi.

Uwaga 3.2

Twierdzenie odwrotne do tw. 3.6 nie jest prawdziwe. Połóżmy W=\mathbb{R}^{n} i weźmy dowolny niepusty wypukły zbiór A\subset\mathbb{R}^{n}. Rozważmy funkcję

f(\mathbf{x})=\begin{cases}0,&\mathbf{x}\in A,\\
1,&\mathbf{x}\notin A.\end{cases}

Każdy zbiór poziomicowy tej funkcji jest wypukły, zaś funkcja nie jest wypukła.

Okazuje się, że wypukłość gwarantuje ciągłość we wnętrzu \mathop{\rm int}W. Rezultat ten nie może być rozszerzony na brzeg W.

Twierdzenie 3.7

Jeśli funkcja f jest wypukła, to jest również ciągła na \mathop{\rm int}W.

Dowód powyższego twierdzenia wykracza poza ramy tego wykładu. Zainteresowany czytelnik może go znaleźć w monografii [10] w rozdziale IV.41.

Twierdzenie 3.8 (Twierdzenie o hiperpłaszczyźnie podpierającej)

Jeśli f jest wypukła, to w każdym punkcie \bar{\mathbf{x}}\in\mathop{\rm int}W istnieje hiperpłaszczyzna podpierająca, tzn. istnieje \xi\in\mathbb{R}^{n} takie że

f(\mathbf{x})\ge f(\bar{\mathbf{x}})+\xi^{T}(\mathbf{x}-\bar{\mathbf{x}}),\qquad\forall\,\mathbf{x}\in W.

Jeśli f jest ściśle wypukła, to

f(\mathbf{x})>f(\bar{\mathbf{x}})+\xi^{T}(\mathbf{x}-\bar{\mathbf{x}}),\qquad\forall\,\mathbf{x}\in W\setminus\{{\bar{\mathbf{x}}}\}.

Jeśli f jest różniczkowalna w {\bar{\mathbf{x}}}, to w obu powyższych nierównościach możemy przyjąć \xi=Df({\bar{\mathbf{x}}})^{T}.

Dowód tw. 3.8

Na mocy twierdzenia 3.5, epigraf \mathop{\rm epi}(f) jest zbiorem wypukłym. Zastosujemy słabe twierdzenie o oddzielaniu do zbiorów U=\mathop{\rm epi}(f) i V=\{({\bar{\mathbf{x}}},f({\bar{\mathbf{x}}}))\}. Istnieje niezerowy wektor \mathbf{a}=(\xi,\alpha)\in\mathbb{R}^{n}\times\mathbb{R}, takie że

\xi^{T}\mathbf{x}+\alpha y\le\xi^{T}{\bar{\mathbf{x}}}+\alpha f({\bar{\mathbf{x}}}) (3.1)

dla (\mathbf{x},y)\in\mathop{\rm epi}(f). Nierówność ta musi być prawdziwa dla wszystkich y\ge f(\mathbf{x}). Zatem \alpha\le 0. Okazuje się, że \alpha\ne 0. Dowiedziemy tego przez sprzeczność: załóżmy \alpha=0. Wówczas dla dowolnego \mathbf{x}\in W mamy \xi^{T}(\mathbf{x}-{\bar{\mathbf{x}}})\le 0. Korzystając z tego, że {\bar{\mathbf{x}}} jest we wnętrzu W, wiemy, że {\bar{\mathbf{x}}}+\varepsilon\xi\in W dla dostatecznie małego \varepsilon>0. Połóżmy \mathbf{x}={\bar{\mathbf{x}}}+\varepsilon\xi. Wtedy 0\ge\xi^{T}(\mathbf{x}-{\bar{\mathbf{x}}})=\varepsilon\xi^{T}\xi=\varepsilon\|\xi\|^{2}, a zatem \xi=\mathbf{0}. Przeczy to niezerowości wektora (\xi,\alpha). Wnioskujemy więc, że \alpha<0.

Możemy założyć, że \alpha=-1 w nierówności (3.1) (wystarczy podzielić obie strony przez |\alpha|). Dla dowolnego \mathbf{x}\in W dostajemy zatem

\xi^{T}\mathbf{x}-f(\mathbf{x})\le\xi^{T}{\bar{\mathbf{x}}}-f({\bar{\mathbf{x}}}),

co przepisujemy następująco

f(\mathbf{x})\ge f({\bar{\mathbf{x}}})+\xi^{T}(\mathbf{x}-{\bar{\mathbf{x}}}).

Kończy to dowód pierwszej części twierdzenia.

Załóżmy teraz, że f jest różniczkowalna w {\bar{\mathbf{x}}}. Dla dowolnego \mathbf{x}\in W, \mathbf{x}\ne{\bar{\mathbf{x}}} i \lambda\in(0,1), z wypukłości mamy

\displaystyle f(\mathbf{x})-f({\bar{\mathbf{x}}}) \displaystyle=\frac{(1-\lambda)f({\bar{\mathbf{x}}})+\lambda f(\mathbf{x})-f({\bar{\mathbf{x}}})}{\lambda}
\displaystyle\ge\frac{f\big((1-\lambda){\bar{\mathbf{x}}}+\lambda\mathbf{x}\big)-f({\bar{\mathbf{x}}})}{\lambda} (3.2)
\displaystyle=\frac{f\big({\bar{\mathbf{x}}}+\lambda(\mathbf{x}-{\bar{\mathbf{x}}})\big)-f({\bar{\mathbf{x}}})}{\lambda}.

Policzmy granicę, gdy \lambda dąży do zera:

f(\mathbf{x})-f({\bar{\mathbf{x}}})\ge\lim _{{\lambda\downarrow 0}}\frac{f\big({\bar{\mathbf{x}}}+\lambda(\mathbf{x}-{\bar{\mathbf{x}}})\big)-f({\bar{\mathbf{x}}})}{\lambda}=Df({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}}),

gdzie istnieje granicy i ostatnia równość wynika z różniczkowalności f w punkcie {\bar{\mathbf{x}}}.

Przypuśćmy, że f jest ściśle wypukła. Ustalmy {\bar{\mathbf{x}}}\in\mathop{\rm int}W. Na mocy pierwszej części twierdzenia f(\mathbf{x})\ge f({\bar{\mathbf{x}}})+\xi^{T}(\mathbf{x}-{\bar{\mathbf{x}}}) dla dowolnego \mathbf{x}\in W. Przypuśćmy, że dla pewnego \mathbf{x}\in W, \mathbf{x}\ne{\bar{\mathbf{x}}}, ta nierówność nie jest ścisła, tj. f(\mathbf{x})=f({\bar{\mathbf{x}}})+\xi^{T}(\mathbf{x}-{\bar{\mathbf{x}}}). Ze ścisłej wypukłości dostajemy

f\Big(\frac{{\bar{\mathbf{x}}}+\mathbf{x}}{2}\Big)<\frac{1}{2}f(\mathbf{x})+\frac{1}{2}f({\bar{\mathbf{x}}})=f({\bar{\mathbf{x}}})+\frac{1}{2}\xi^{T}(\mathbf{x}-{\bar{\mathbf{x}}}). (3.3)

Z drugiej strony, z istnienia płaszczyzny podpierającej w {\bar{\mathbf{x}}} mamy

f\Big(\frac{{\bar{\mathbf{x}}}+\mathbf{x}}{2}\Big)\ge f({\bar{\mathbf{x}}})+\xi^{T}\Big(\frac{\mathbf{x}+{\bar{\mathbf{x}}}}{2}-{\bar{\mathbf{x}}}\Big)=f({\bar{\mathbf{x}}})+\xi^{T}\frac{\mathbf{x}-{\bar{\mathbf{x}}}}{2}.

Dostajemy sprzeczność z nierównością (3.3). Pokazuje to, że dla funkcji ściśle wypukłej f musi być spełniona ścisła nierówność f(\mathbf{x})<f({\bar{\mathbf{x}}})+\xi^{T}(\mathbf{x}-{\bar{\mathbf{x}}}) jeśli tylko \mathbf{x}\ne{\bar{\mathbf{x}}}.

Prawdziwe jest twierdzenie odwrotne do twierdzenia 3.8 (patrz tw. 3.9).

Wniosek 3.2

Jeśli f wypukła i różniczkowalna w {\bar{\mathbf{x}}}\in\mathop{\rm int}W, to w {\bar{\mathbf{x}}} jest minimum globalne wtw, gdy Df({\bar{\mathbf{x}}})=0.

Dowód

Implikacja w prawą stronę wynika z tw. 1.4. Aby dowieść implikacji przeciwnej, załóżmy Df({\bar{\mathbf{x}}})=0 dla pewnego {\bar{\mathbf{x}}}=0. Na mocy tw. 3.8 dla dowolnego \mathbf{x}\in W mamy

f(\mathbf{x})\ge f(\bar{\mathbf{x}})+Df({\bar{\mathbf{x}}})(\mathbf{x}-\bar{\mathbf{x}})=f({\bar{\mathbf{x}}}),

co dowodzi, że w punkcie {\bar{\mathbf{x}}} jest minimum globalne.

Poniżej wymieniamy pozostałe własności funkcji wypukłych. Ich dowody pozostawione są jako ćwiczenia.

  • Niech W\subset\mathbb{R}^{n}, wypukły, zaś I dowolny zbiór. Jeśli funkcje f_{i}:W\to\mathbb{R}, i\in I, są wypukłe, to f(\mathbf{x})=\sup _{{i\in I}}f_{i}(\mathbf{x}) jest wypukła ze zbiorem wartości \mathbb{R}\cup\{\infty\}.

  • Niech W\subset\mathbb{R}^{n}, wypukły. Jeśli funkcje f_{i}:W\to\mathbb{R}, i=1,2,\ldots,m, są wypukłe i \alpha _{i}>0 dla i=1,2,\ldots,m, to funkcja f=\sum _{{i=1}}^{m}\alpha _{i}f_{i} jest wypukła. Jeśli jedna z funkcji f_{i} jest ściśle wypukła, to f jest również ściśle wypukła.

  • Niech W\subset\mathbb{R}^{n}, A\subset\mathbb{R}^{m} wypukłe zbiory. Jeśli funkcja h:W\times A\to\mathbb{R} jest wypukła i ograniczona z dołu, to

    f(\mathbf{x})=\inf _{{\mathbf{a}\in A}}h(\mathbf{x},\mathbf{a}),\qquad\mathbf{x}\in W,

    jest wypukła.

  • Niech f:\mathbb{R}^{n}\to\mathbb{R} wypukła. Jeśli h:\mathbb{R}^{m}\to\mathbb{R}^{n} afiniczna, to złożenie f\circ h jest funkcją wypukłą.

  • Niech W\subset\mathbb{R}^{n} wypukły. Jeśli f:W\to\mathbb{R} jest funkcją wypukłą i g:\mathbb{R}\to\mathbb{R} jest wypukła i niemalejąca, to g\circ f jest funkcją wypukłą. Jeśli dodatkowo g jest rosnąca, zaś f ściśle wypukła, to g\circ f jest ściśle wypukła.

  • Niech W\subset\mathbb{R}^{n} wypukły. Jeśli f:W\to\mathbb{R} jest funkcją (ściśle) wklęsłą i f>0, to funkcja 1/f jest (ściśle) wypukła.

3.4. Charakteryzacje funkcji wypukłej

Twierdzenie 3.9

Niech W\subset\mathbb{R}^{n} wypukły o niepustym wnętrzu. Jeśli w każdym punkcie {\bar{\mathbf{x}}}\in\mathop{\rm int}W istnieje wektor \xi\in\mathbb{R}^{n}, taki że

f(\mathbf{x})\ge f(\bar{\mathbf{x}})+\xi^{T}(\mathbf{x}-\bar{\mathbf{x}}),\qquad\forall\,\mathbf{x}\in W,

to funkcja f jest wypukła. Jeśli nierówność jest ostra dla \mathbf{x}\ne{\bar{\mathbf{x}}}, to f jest ściśle wypukła.

Dowód

Weźmy \mathbf{x}\in\mathop{\rm int}W, \mathbf{y}\in W i \lambda\in(0,1). Oznaczmy \mathbf{x}_{\lambda}=\lambda\mathbf{x}+(1-\lambda)\mathbf{y}. Chcemy wykazać, że f(\mathbf{x}_{\lambda})\le\lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y}). Na mocy Lematu 3.2 punkt \mathbf{x}_{\lambda} należy do wnętrza W. Stosując założenie do tego punktu dostajemy \xi\in\mathbb{R}^{n}, takie że

\begin{aligned}\displaystyle f(\mathbf{x})&\displaystyle\ge f(\mathbf{x}_{\lambda})+\xi^{T}(\mathbf{x}-\mathbf{x}_{\lambda}),\\
\displaystyle f(\mathbf{y})&\displaystyle\ge f(\mathbf{x}_{\lambda})+\xi^{T}(\mathbf{y}-\mathbf{x}_{\lambda}).\end{aligned} (3.4)

Stąd

\lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y})\ge f(\mathbf{x}_{\lambda})+\xi^{T}\big[\lambda(\mathbf{x}-\mathbf{x}_{\lambda})+(1-\lambda)(\mathbf{y}-\mathbf{x}_{\lambda})\big]=f(\mathbf{x}_{\lambda}),

gdyż wielkości w nawiasie kwadratowym zerują się. Kończy to dowód twierdzenia. Jeśli nierówność w założeniu jest ostra i \mathbf{x}\ne\mathbf{y}, to nierówności (3.4) są ostre i dostajemy warunek ścisłej wypukłości.

Twierdzenie 3.10

Niech W\subset\mathbb{R}^{n} niepusty, otwarty i wypukły, zaś f:W\to\mathbb{R} dwukrotnie różniczkowalna. Wówczas:

  • I) f jest wypukła wtw, gdy hesjan D^{2}f(\mathbf{x}) jest nieujemnie określony dla każdego \mathbf{x}\in W.

  • II) Jeśli hesjan D^{2}f(\mathbf{x}) jest dodatnio określony dla każdego \mathbf{x}\in W, to f jest ściśle wypukła.

Analogiczna teza zachodzi w przypadku wklęsłości.

Dowód

Załóżmy najpierw, że hesjan jest nieujemnie określony dla każdego \mathbf{x}\in W. Wówczas, na mocy wniosku 2.1, dla dowolnych {\bar{\mathbf{x}}},\mathbf{x}\in W mamy

f(\mathbf{x})=f({\bar{\mathbf{x}}})+Df({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})+\frac{1}{2}(\mathbf{x}-{\bar{\mathbf{x}}})^{T}D^{2}f(\tilde{\mathbf{x}})(\mathbf{x}-{\bar{\mathbf{x}}}),

gdzie \tilde{\mathbf{x}} jest punktem leżącym na odcinku łączącym {\bar{\mathbf{x}}} z \mathbf{x}. Założenie o nieujemnej określoności hesjanu pociąga nieujemność ostatniego składnika powyższej sumy. Stąd

f(\mathbf{x})\ge f({\bar{\mathbf{x}}})+Df({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}}). (3.5)

Ponieważ powyższa nierówność zachodzi dla dowolnych {\bar{\mathbf{x}}},\mathbf{x}\in W, to f jest wypukła na mocy twierdzenia 3.9.

Jeśli założymy, że hesjan jest dodatnio określony dla każdego punktu W, to nierówność (3.5) jest ostra i twierdzenie 3.9 implikuje ścisłą wypukłość f.

Przejdźmy teraz do dowodu implikacji przeciwnej. Załóżmy, że funkcja f jest wypukła. Ustalmy {\bar{\mathbf{x}}}\in W i \mathbf{h}\in\mathbb{R}^{n}, \mathbf{h}\ne 0. Z otwartości W wynika, że istnieje \delta>0, dla której {\bar{\mathbf{x}}}+t\mathbf{h}\in W, t\in(-\delta,\delta). Zdefiniujmy funkcję g(t)=f\big({\bar{\mathbf{x}}}+t\mathbf{h}\big), t\in(-\delta,\delta). Jest to funkcja jednej zmiennej, dwukrotnie różniczkowalna oraz wypukła. Stosując twierdzenie 3.8 dostajemy

g(t)\ge g(0)+g^{{\prime}}(0)t,\qquad t\in(-\delta,\delta).

Na mocy twierdzenie Taylora z resztą w postaci Peano, tw. 1.9, mamy

g(t)=g(0)+g^{{\prime}}(0)t+\frac{1}{2}g^{{\prime\prime}}(0)t^{2}+o(t^{2}),\qquad t\in(-\delta,\delta).

Powyższa nierówność i wzór Taylora dają następujące oszacowanie na drugą pochodną

\frac{1}{2}g^{{\prime\prime}}(0)t^{2}+o(t^{2})\ge 0.

Dzielimy obie strony przez t^{2}:

\frac{1}{2}g^{{\prime\prime}}(0)+\frac{o(t^{2})}{t^{2}}\ge 0.

W granicy przy t dążącym do zera, drugi składnik zanika i pozostaje g^{{\prime\prime}}(0)\ge 0. Co ta nierówność znaczy w terminach funkcji f? Liczymy:

g^{{\prime}}(t)=Df({\bar{\mathbf{x}}}+t\mathbf{h})\mathbf{h},\qquad g^{{\prime\prime}}(t)=\mathbf{h}^{T}D^{2}f({\bar{\mathbf{x}}}+t\mathbf{h})\mathbf{h}.

Stąd g^{{\prime\prime}}(0)=\mathbf{h}^{T}D^{2}f({\bar{\mathbf{x}}})\mathbf{h}.

Powyższe rozumowanie możemy przeprowadzić dla dowolnego \mathbf{h}\in\mathbb{R}^{n}. Wykazaliśmy więc nieujemną określoność D^{2}f({\bar{\mathbf{x}}}).

3.5. Subróżniczka

Zajmiemy się teraz uogólnieniem pojęcia pochodnej na nieróżniczkowalne funkcje wypukłe. Niech W\subseteq\mathbb{R}^{n} będzie zbiorem wypukłym, zaś f:W\to\mathbb{R} funkcją wypukłą.

Definicja 3.4

Wektor \xi\in\mathbb{R}^{n} nazywamy subgradientem funkcji f w punkcie \mathbf{x}_{0}\in W, jeśli

f(\mathbf{x})\ge f(\mathbf{x}_{0})+\xi^{T}(\mathbf{x}-\mathbf{x}_{0}),\qquad\mathbf{x}\in W.

Zbiór wszystkich subgradientów f w punkcie \mathbf{x}_{0} nazywamy subróżniczką i oznaczamy \partial f(\mathbf{x}_{0}).

Wniosek 3.3

Jeśli W\in\mathbb{R}^{n} jest zbiorem wypukłym o niepustym wnętrzu, to f:W\to\mathbb{R} jest wypukła wtw, gdy w każdym punkcie zbioru \mathop{\rm int}W istnieje subgradient:

\partial f(\mathbf{x})\ne\emptyset\qquad\forall\ \mathbf{x}\in\mathop{\rm int}W.
Dowód

Implikacja w prawą stronę wynika z twierdzenia 3.8, zaś implikacja w stronę lewą – z tw. 3.9.

Lemat 3.3

Niech W\subset\mathbb{R}^{n} będzie zbiorem wypukłym, zaś f:W\to\mathbb{R} funkcją wypukłą. Wówczas subróżniczka \partial f(\mathbf{x}) jest zbiorem wypukłym i domkniętym. Jeśli \mathbf{x} jest wewnętrzym punktem W, \mathbf{x}\in\mathop{\rm int}W, to zbiór \partial f(\mathbf{x}) jest ograniczony.

Dowód

Dowód wypukłości i domkniętości pozostawiamy jako ćwiczenie (patrz ćw. 3.24). Ustalmy {\bar{\mathbf{x}}}\in\mathop{\rm int}W. Wówczas istnieje \varepsilon>0, taki że kula domknięta B({\bar{\mathbf{x}}},\varepsilon) jest zawarta w \mathop{\rm int}W. Dla dowolnego \xi\in\partial f({\bar{\mathbf{x}}})

f(\mathbf{x})\ge f({\bar{\mathbf{x}}})+\xi^{T}(\mathbf{x}-{\bar{\mathbf{x}}}),\qquad\mathbf{x}\in W.

A zatem

\sup _{{\mathbf{x}\in B({\bar{\mathbf{x}}},\varepsilon)}}f(\mathbf{x})\ge f({\bar{\mathbf{x}}})+\sup _{{\mathbf{x}\in B({\bar{\mathbf{x}}},\varepsilon)}}\xi^{T}(\mathbf{x}-{\bar{\mathbf{x}}}).

Lewa strona jest niezależna od \xi oraz, z ciągłości f na \mathop{\rm int}W, skończona. Supremum po prawej stronie jest przyjmowane dla \mathbf{x}={\bar{\mathbf{x}}}+\varepsilon\xi/\|\xi\| i wynosi \varepsilon\|\xi\|. Dostajemy zatem

\varepsilon\|\xi\|\le\sup _{{\mathbf{x}\in B({\bar{\mathbf{x}}},\varepsilon)}}f(\mathbf{x})-f({\bar{\mathbf{x}}}),

co dowodzi ograniczoności zbioru \partial f({\bar{\mathbf{x}}}).

Pokażemy teraz związek subróżniczki z pochodnymi kierunkowymi funkcji. Związek ten przyda nam się w dalszych dowodach.

Definicja 3.5

Pochodną kierunkową funkcji f w punkcie {\bar{\mathbf{x}}} w kierunku \mathbf{d} nazywamy granicę

f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})=\lim _{{\lambda\downarrow 0}}\frac{f({\bar{\mathbf{x}}}+\lambda\mathbf{d})-f({\bar{\mathbf{x}}})}{\lambda}.

Z własności pochodnych jednostronnych dla skalarnych funkcji wypukłych wynikają następujące własności pochodnych kierunkowych:

Lemat 3.4

Niech W\subset\mathbb{R}^{n} będzie zbiorem wypukłym otwartym, zaś f:W\to\mathbb{R} funkcją wypukłą. Wówczas dla każdego \mathbf{d}\in\mathbb{R}^{n} i \mathbf{x}\in W

  • I) istnieje pochodna kierunkowa f^{{\prime}}(\mathbf{x};\mathbf{d}).

  • II) f^{{\prime}}(\mathbf{x};\mathbf{d})=\inf _{{\lambda>0}}\frac{f({\bar{\mathbf{x}}}+\lambda\mathbf{d})-f({\bar{\mathbf{x}}})}{\lambda}.

  • III) f^{{\prime}}(\mathbf{x};\mathbf{d})\ge-f^{{\prime}}(\mathbf{x};-\mathbf{d}).

Dowód

Zdefiniujmy funkcję skalarną g(t)=f(\mathbf{x}+t\mathbf{d}) dla t, takich że \mathbf{x}+t\mathbf{d}\in W. Z otwartości W wynika, że g jest określona na pewnym otoczeniu zera (-\delta,\delta). Jest ona także wypukła. Wówczas iloraz różnicowy jest monotoniczny, tzn. dla -\delta<t_{1}<t_{2}<\delta mamy

\frac{g(t_{1})-g(0)}{t_{1}}\le\frac{g(t_{2})-g(0)}{t_{2}}. (3.6)

Z monotoniczności ilorazu różnicowego wynika, że istnieją pochodne lewostronna g^{{\prime}}(0-) i prawostronna g^{{\prime}}(0+), g^{{\prime}}(0-)\le g^{{\prime}}(0+) oraz

g^{{\prime}}(0+)=\inf _{{t>0}}\frac{g(t)-g(0)}{t}.

Wystarczy teraz zauważyć, że f^{{\prime}}(\mathbf{x};\mathbf{d})=g^{{\prime}}(0+), zaś f^{{\prime}}(\mathbf{x};-\mathbf{d})=-g^{{\prime}}(0-).

Pozostał nam jeszcze dowód monotoniczności ilorazu różnicowego. Weźmy najpierw 0<t_{1}<t_{2}<\delta i zauważmy, że nierówność (3.6) jest równoważna

g(t_{1})\le\lambda g(t_{2})+(1-\lambda)g(0),

gdzie \lambda=t_{1}/t_{2}\in(0,1) oraz \lambda t_{2}+(1-\lambda)0=t_{1}. Prawdziwość ostatniej nierówności wynika z wypukłości funkcji g. Przypadek -\delta<t_{1}<t_{2}<0 dowodzimy analogicznie. Dla -\delta<t_{1}<0<t_{2}<\delta nierówność (3.6) jest równoważna

g(0)\le\frac{1}{1+\lambda}g(t_{1})+\frac{\lambda}{1+\lambda}g(t_{2}),\qquad\lambda=-\frac{t_{1}}{t_{2}},

która wynika z wypukłości g, gdyż 1/(1+\lambda)\in(0,1) oraz

\frac{1}{1+\lambda}t_{1}+\frac{\lambda}{1+\lambda}t_{2}=0.

Pochodne kierunkowe pozwalają na nową charakteryzację subróżniczki.

Lemat 3.5

Niech W\subset\mathbb{R}^{n} będzie zbiorem wypukłym otwartym, zaś f:W\to\mathbb{R} funkcją wypukłą. Prawdziwa jest następująca równoważność: \xi\in\partial f({\bar{\mathbf{x}}}) wtw, gdy

f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})\ge\xi^{T}\mathbf{d},\qquad\forall\ \mathbf{d}\in\mathbb{R}^{n}.
Dowód

Ustalmy {\bar{\mathbf{x}}}\in W i \xi\in\partial f({\bar{\mathbf{x}}}). Wówczas dla \lambda>0 i \mathbf{d}\in\mathbb{R}^{n} (oczywiście takich, że {\bar{\mathbf{x}}}+\lambda\mathbf{d}\in W) mamy

f({\bar{\mathbf{x}}}+\lambda\mathbf{d})\ge f({\bar{\mathbf{x}}})+\lambda\xi^{T}\mathbf{d}.

Zatem

\frac{f({\bar{\mathbf{x}}}+\lambda\mathbf{d})-f({\bar{\mathbf{x}}})}{\lambda}\ge\xi^{T}\mathbf{d},

co implikuje f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})\ge\xi^{T}\mathbf{d}.

Weźmy teraz wektor \xi\in\mathbb{R}^{n} spełniający warunek f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})\ge\xi^{T}\mathbf{d} dla każdego \mathbf{d}\in\mathbb{R}^{n}. Na mocy lematu 3.4(II) dla \lambda>0 mamy

f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})\le\frac{f({\bar{\mathbf{x}}}+\lambda\mathbf{d})-f({\bar{\mathbf{x}}})}{\lambda}.

A zatem

f({\bar{\mathbf{x}}}+\lambda\mathbf{d})\ge f({\bar{\mathbf{x}}})+\xi^{T}(\lambda\mathbf{d}).

Z dowolności \lambda i \mathbf{d} wynika, iż \xi jest subgradientem.

Poniższe twierdzenie precyzuje związek pomiędzy subróżniczką i pochodną kierunkową funkcji. Zwróć uwagę na wykorzystanie twierdzenia o oddzielaniu w dowodzie. Metoda polegająca na sprytnym dobraniu rozłącznych zbiorów wypukłych, które można rozdzielić hiperpowierzchnią, będzie wielokrotnie wykorzystywana w dowodzeniu twierdzeń dotyczących funkcji wypukłych.

Twierdzenie 3.11

Niech f:W\to\mathbb{R} będzie funkcją wypukłą zadaną na wypukłym otwartym zbiorze W\subset\mathbb{R}^{n}. Dla dowolnego {\bar{\mathbf{x}}}\in W i \mathbf{d}\in\mathbb{R}^{n} zachodzi

f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})=\max _{{\xi\in\partial f({\bar{\mathbf{x}}})}}\xi^{T}\mathbf{d}.

Ponadto, funkcja f jest różniczkowalna w {\bar{\mathbf{x}}} wtw, gdy subróżniczka \partial f({\bar{\mathbf{x}}}) składa się z jednego subgradientu. Tym subgradientem jest wówczas Df({\bar{\mathbf{x}}})^{T}.

Dowód

Z lematu 3.5 wynika, że f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})\ge\xi^{T}\mathbf{d} dla \xi\in\partial f({\bar{\mathbf{x}}}). Stąd

f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})\ge\max _{{\xi\in\partial f({\bar{\mathbf{x}}})}}\xi^{T}\mathbf{d}.

Udowodnienie przeciwnej nierówności wymaga skorzystania z twierdzenia o oddzielaniu. Zdefiniujmy dwa zbiory:

\displaystyle C_{1} \displaystyle=\{(\mathbf{x},z)\in W\times\mathbb{R}:\  z>f(\mathbf{x})\},
\displaystyle C_{2} \displaystyle=\{(\mathbf{x},z)\in W\times\mathbb{R}:\ \mathbf{x}={\bar{\mathbf{x}}}+\lambda\mathbf{d},\  z=f({\bar{\mathbf{x}}})+\lambda f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d}),\quad\lambda\ge 0\}.

Zauważmy, że C_{1} różni się od epigrafu f tylko brzegiem \{(\mathbf{x},z)\in W\times\mathbb{R}:\  z=f(\mathbf{x})\}. Możemy zatem zastosować podobne rozumowanie jak w dowodzie tw. 3.5, aby wykazać, że C_{1} jest zbiorem wypukłym. Zbiór C_{2} jest odcinkiem o początku w punkcie ({\bar{\mathbf{x}}},f({\bar{\mathbf{x}}})) i o kierunku \big(\mathbf{d},f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})\big), więc jest wypukły. Można zauważyć, że jest on wykresem liniowego przybliżenia funkcji f wokół punktu {\bar{\mathbf{x}}} wzdłuż odcinka \{{\bar{\mathbf{x}}}+\lambda\mathbf{d}:\lambda\ge 0\}\cap W.

Na mocy lematu 3.4(II) mamy f^{{\prime}}(\mathbf{x};\mathbf{d})\le\frac{f({\bar{\mathbf{x}}}+\lambda\mathbf{d})-f({\bar{\mathbf{x}}})}{\lambda}, czyli

f({\bar{\mathbf{x}}}+\lambda\mathbf{d})\ge f({\bar{\mathbf{x}}})+\lambda f^{{\prime}}(\mathbf{x};\mathbf{d}).

Wniskujemy stąd, że zbiory C_{1} i C_{2} są rozłączne. Stosujemy słabe twierdzenie o oddzialniu, tw. 3.1: istnieje niezerowy wektor (\mu,\gamma)\in\mathbb{R}^{n}\times\mathbb{R}, taki że

\mu^{T}\mathbf{x}+\gamma z\ge\mu^{T}({\bar{\mathbf{x}}}+\lambda\mathbf{d})+\gamma\big(f({\bar{\mathbf{x}}})+\lambda f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})\big),\qquad(\mathbf{x},z)\in C_{1},\ \lambda\in[0,L), (3.7)

gdzie L=\sup\{\lambda\ge 0:\ {\bar{\mathbf{x}}}+\lambda\mathbf{d}\in W\}. Zauważmy, że \gamma nie może być ujemna, gdyż wtedy lewa strona mogłaby być dowolnie mała (z może być dowolnie duże). Nie może także być \gamma=0, gdyż wówczas dla każdego \mathbf{x}\in W musiałoby zachodzić \mu^{T}(\mathbf{x}-{\bar{\mathbf{x}}})\ge\lambda\mu^{T}\mathbf{d}. Jest to możliwe tylko, gdy \mu=\mathbf{0} (korzystamy tutaj z faktu, że W jest otwarty). A to przeczy niezerowości wektora (\mu,\gamma). Dowiedliśmy zatem, że \gamma>0. Dzieląc obie strony nierówności (3.7) przez \gamma możemy założyć, że \gamma=1, czyli

\mu^{T}\mathbf{x}+z\ge\mu^{T}({\bar{\mathbf{x}}}+\lambda\mathbf{d})+f({\bar{\mathbf{x}}})+\lambda f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d}),\qquad(\mathbf{x},z)\in C_{1},\ \lambda\in[0,L).

Zbiegając z z do f(\mathbf{x}) otrzymujemy

\mu^{T}\mathbf{x}+f(\mathbf{x})\ge\mu^{T}({\bar{\mathbf{x}}}+\lambda\mathbf{d})+f({\bar{\mathbf{x}}})+\lambda f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d}),\qquad\mathbf{x}\in W,\ \lambda\in[0,L). (3.8)

Kładąc \lambda=0 dostajemy

\mu^{T}(\mathbf{x}-{\bar{\mathbf{x}}})+f(\mathbf{x})\ge f({\bar{\mathbf{x}}}),

co po przekształeceniu daje

f(\mathbf{x})\ge f({\bar{\mathbf{x}}})-\mu^{T}(\mathbf{x}-{\bar{\mathbf{x}}}).

A zatem -\mu\in\partial f({\bar{\mathbf{x}}}). Biorąc w nierówności (3.8) \lambda>0 i \mathbf{x}={\bar{\mathbf{x}}} dostajemy

-\mu^{T}(\lambda\mathbf{d})\ge\lambda f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d}),

czyli

\sup _{{\xi\in\partial f({\bar{\mathbf{x}}})}}\xi^{T}\mathbf{d}\ge f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d}).

To kończy dowód pierwszej części twierdzenia.

Dowód drugiej części twierdzenia opiera się na dwóch prostych równoważnościach:

  1. Funkcja f jest różniczkowalna w punkcie {\bar{\mathbf{x}}} wtw, gdy istnieje wektor \alpha\in\mathbb{R}^{n}, taki że f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})=\alpha^{T}\mathbf{d} dla każdego \mathbf{d}\in\mathbb{R}^{n}.

  2. Odwzorowanie \mathbb{R}^{n}\ni\mathbf{d}\mapsto\sup _{{\xi\in\partial f({\bar{\mathbf{x}}})}}\xi^{T}\mathbf{d} jest liniowe wtw, gdy subróżniczka \partial f({\bar{\mathbf{x}}}) jest jednoelementowa.

Równoważność pierwsza wynika wprost z definicji pochodnej (patrz roz. 2). Jeśli f jest różniczowalna w {\bar{\mathbf{x}}}, jedynym wektorem spełniającym f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})=\alpha^{T}\mathbf{d} jest \alpha=Df({\bar{\mathbf{x}}})^{T}.

Przypuśćmy więc, że funkcja f jest różniczkowalna w {\bar{\mathbf{x}}}. Wówczas f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})=Df({\bar{\mathbf{x}}})\mathbf{d}, czyli pochodna kierunkowa jest funkcją liniową \mathbf{d}. Na mocy drugiej równoważności subróżniczka jest jednoelementowa. Łatwo już zauważyć, że \partial f({\bar{\mathbf{x}}})=\{ Df({\bar{\mathbf{x}}})^{T}\}. Do dowodu w przeciwną stronę załóżmy, że subróżniczka \partial f({\bar{\mathbf{x}}}) składa się z jednego wektora \alpha\in\mathbb{R}^{n}. Wówczas f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})=\alpha^{T}\mathbf{d}. Na mocy pierwszej równoważności funkcja f jest różniczkowalna w {\bar{\mathbf{x}}}.

Twierdzenie 3.11 wykorzystamy kilkukrotnie w dowodzie poniższego twierdzenia, które będzie użyteczne w znajdowaniu subróżniczek.

Twierdzenie 3.12

Niech W\subset\mathbb{R}^{n} będzie zbiorem wypukłym otwartym, zaś f_{1},f_{2}:W\to\mathbb{R} funkcjami wypukłymi.

  • I) Niech f=f_{1}+f_{2}. Wówczas \partial f_{1}(\mathbf{x})+\partial f_{2}(\mathbf{x})=\partial f(\mathbf{x}), gdzie

    \partial f_{1}(\mathbf{x})+\partial f_{2}(\mathbf{x})=\big\{\xi _{1}+\xi _{2}:\ \xi _{1}\in\partial f_{1}(\mathbf{x}),\ \xi _{2}\in\partial f_{2}(\mathbf{x})\big\}.
  • II) Niech f=\max(f_{1},f_{2}). Wówczas

    \partial f(\mathbf{x})=\begin{cases}\partial f_{1}(\mathbf{x}),&f_{1}(\mathbf{x})>f_{2}(\mathbf{x}),\\
\mathop{\rm conv}\big(\partial f_{1}(\mathbf{x})\cup\partial f_{2}(\mathbf{x})\big),&f_{1}(\mathbf{x})=f_{2}(\mathbf{x}),\\
\partial f_{2}(\mathbf{x}),&f_{1}(\mathbf{x})<f_{2}(\mathbf{x}),\end{cases}

    gdzie \mathop{\rm conv}(\partial f_{1}(\mathbf{x})\cup f_{2}(\mathbf{x})) jest zbiorem kombinacji wypukłych elementów zbiorów \partial f_{1}(\mathbf{x}) i \partial f_{2}(\mathbf{x}).

Dowód

Zaczniemy od dowodu (I). Ustalmy {\bar{\mathbf{x}}}\in W. Niech \xi _{1}\in\partial f_{1}({\bar{\mathbf{x}}}) i \xi _{2}\in\partial f_{2}({\bar{\mathbf{x}}}). Wówczas dla \mathbf{x}\in W zachodzi

\displaystyle f_{1}(\mathbf{x}) \displaystyle\ge f_{1}({\bar{\mathbf{x}}})+\xi _{1}^{T}(\mathbf{x}-{\bar{\mathbf{x}}}),
\displaystyle f_{2}(\mathbf{x}) \displaystyle\ge f_{2}({\bar{\mathbf{x}}})+\xi _{2}^{T}(\mathbf{x}-{\bar{\mathbf{x}}}).

Dodając te nierówności stronami otrzymujemy

f(\mathbf{x})\ge f({\bar{\mathbf{x}}})+(\xi _{1}+\xi _{2})^{T}(\mathbf{x}-{\bar{\mathbf{x}}}),

czyli \xi _{1}+\xi _{2}\in\partial f({\bar{\mathbf{x}}}). Dowiedliśmy zawierania \partial f_{1}({\bar{\mathbf{x}}})+\partial f_{2}({\bar{\mathbf{x}}})\subset\partial f({\bar{\mathbf{x}}}). Przypuśćmy, że inkluzja ta jest ostra, tzn. istnieje \xi\in\partial f({\bar{\mathbf{x}}}), taki że \xi\notin\partial f_{1}({\bar{\mathbf{x}}})+\partial f_{2}({\bar{\mathbf{x}}}). Na mocy lematu 3.3 subróżniczki \partial f_{1}({\bar{\mathbf{x}}}) i \partial f_{2}({\bar{\mathbf{x}}}) są zwartymi zbiorami wypukłymi. A zatem ich suma algebraiczna jest również zbiorem zwartym i wypukłym (patrz ćw. 3.25). Stosujemy silne twierdzenie o oddzielaniu do zbiorów \{\xi\} oraz \partial f_{1}({\bar{\mathbf{x}}})+\partial f_{2}({\bar{\mathbf{x}}}). Dostajemy \mu\in\mathbb{R}^{n} i stałą b\in R, takie że

\mu^{T}\xi _{1}+\mu^{T}\xi _{2}<b<\mu^{T}\xi,\qquad\forall\ \xi _{1}\in\partial f_{1}({\bar{\mathbf{x}}}),\ \xi _{2}\in\partial f_{2}({\bar{\mathbf{x}}}).

Bierzemy maksimum po \xi _{1},\xi _{2} po lewej stronie i stosujemy twierdzenie 3.11:

f_{1}^{{\prime}}({\bar{\mathbf{x}}};\mu)+f_{2}^{{\prime}}({\bar{\mathbf{x}}};\mu)<\xi^{T}\mu\le f^{{\prime}}({\bar{\mathbf{x}}};\mu).

Z drugiej strony, z własności pochodnych kierunkowych mamy

f_{1}^{{\prime}}({\bar{\mathbf{x}}};\mu)+f_{2}^{{\prime}}({\bar{\mathbf{x}}};\mu)=f^{{\prime}}({\bar{\mathbf{x}}};\mu).

Doprowadziliśmy do sprzeczności: \xi o żądanych własnościach nie może istnieć. Kończy to dowód (I).

Dowód (II). Postać subróżniczki \partial f na zbiorach \{\mathbf{x}\in W:\  f_{1}(\mathbf{x})>f_{2}(\mathbf{x})\} i \{\mathbf{x}\in W:\  f_{1}(\mathbf{x})<f_{2}(\mathbf{x})\} jest oczywista. Jedynie przypadek \{\mathbf{x}\in W:\  f_{1}(\mathbf{x})=f_{2}(\mathbf{x})\} wymaga dokładnego dowodu. Ustalmy {\bar{\mathbf{x}}}\in W, dla którego f_{1}({\bar{\mathbf{x}}})=f_{2}({\bar{\mathbf{x}}}). Oznaczmy A=\mathop{\rm conv}\big(\partial f_{1}({\bar{\mathbf{x}}})\cup\partial f_{2}({\bar{\mathbf{x}}})\big). Dla i=1,2 oraz \mathbf{x}\in W mamy

f(\mathbf{x})-f({\bar{\mathbf{x}}})\ge f_{i}(\mathbf{x})-f({\bar{\mathbf{x}}})=f_{i}(\mathbf{x})-f_{i}({\bar{\mathbf{x}}})\ge\xi _{i}^{T}(\mathbf{x}-{\bar{\mathbf{x}}}),\qquad\forall\ \xi _{i}\in\partial f_{i}({\bar{\mathbf{x}}}).

Stąd dostajemy \partial f_{1}({\bar{\mathbf{x}}})\cup\partial f_{1}({\bar{\mathbf{x}}})\subset\partial f({\bar{\mathbf{x}}}). Z wypukłości subróżniczki (patrz lemat 3.3) wynika, że A\subset\partial f({\bar{\mathbf{x}}}). Załóżmy teraz, że istnieje \xi\in\partial f({\bar{\mathbf{x}}})\setminus A. Zbiór A jest wypukły i zwarty. Stosujemy silne twierdzenie o oddzielaniu do zbiorów A i \{\xi\}. Dostajemy \mu\in\mathbb{R}^{n} i stałą b\in R, takie że

\mu^{T}\tilde{\xi}<b<\mu^{T}\xi,\qquad\forall\ \tilde{\xi}\in A.

W szczególności \mu^{T}\xi _{i}<b dla \xi _{i}\in\partial f_{i}({\bar{\mathbf{x}}}), i=1,2, czyli, na mocy tw. 3.11,

\max\big(f_{1}^{{\prime}}({\bar{\mathbf{x}}};\mu),f_{2}^{{\prime}}({\bar{\mathbf{x}}};\mu)\big)\le b.

Podobnie, b<\xi^{T}\mu\le f^{{\prime}}({\bar{\mathbf{x}}};\mu). Podsumowując:

\max\big(f_{1}^{{\prime}}({\bar{\mathbf{x}}};\mu),f_{2}^{{\prime}}({\bar{\mathbf{x}}};\mu)\big)<f^{{\prime}}({\bar{\mathbf{x}}};\mu). (3.9)

Z drugiej strony, definicja pochodnej kierunkowej daje nam następującą równość (przypomnijmy, że f({\bar{\mathbf{x}}})=f_{1}({\bar{\mathbf{x}}})=f_{2}({\bar{\mathbf{x}}})):

\frac{f({\bar{\mathbf{x}}}+\lambda\mathbf{d})-f({\bar{\mathbf{x}}})}{\lambda}=\max\bigg(\frac{f_{1}({\bar{\mathbf{x}}}+\lambda\mathbf{d})-f({\bar{\mathbf{x}}})}{\lambda},\frac{f_{2}({\bar{\mathbf{x}}}+\lambda\mathbf{d})-f({\bar{\mathbf{x}}})}{\lambda}\bigg),\qquad\lambda>0.

Przechodząc z \lambda do zera dostajemy

f^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})=\max\big(f_{1}^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d}),f_{2}^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})\big).

Biorąc \mathbf{d}=\mu dostajemy sprzeczność z (3.9), a więc nie może istnieć \xi\in\partial f({\bar{\mathbf{x}}})\setminus A.

Twierdzenie 3.13

Niech W\subset\mathbb{R}^{n} będzie zbiorem wypukłym otwartym, f:W\to\mathbb{R} funkcją wypukłą, zaś A będzie macierzą n\times m. Zdefiniujmy \tilde{W}=\{\mathbf{x}\in\mathbb{R}^{m}:A\mathbf{x}\in W\}. Wówczas \tilde{W} jest zbiorem wypukłym otwartym oraz funkcja F:\tilde{W}\to\mathbb{R} zadana wzorem F(\mathbf{x})=f(A\mathbf{x}) ma w punkcie \mathbf{x}\in\tilde{W} subróżniczkę zadaną wzorem

\partial F(\mathbf{x})=A^{T}\partial f(A\mathbf{x}).
Dowód

Dowód będzie przebiegał podobnie jak dowód poprzedniego twierdzenia. Ustalmy {\bar{\mathbf{x}}}\in\tilde{W}. Weźmy \xi\in\partial f(A{\bar{\mathbf{x}}}). Wówczas

f(A\mathbf{x})\ge f(A{\bar{\mathbf{x}}})+\xi^{T}(A\mathbf{x}-A{\bar{\mathbf{x}}})=f(A{\bar{\mathbf{x}}})+(A^{T}\xi)^{T}(\mathbf{x}-{\bar{\mathbf{x}}}),

czyli A^{T}\xi\in\partial F({\bar{\mathbf{x}}}). Stąd mamy zawieranie A^{T}\partial f(A{\bar{\mathbf{x}}})\subset\partial F({\bar{\mathbf{x}}}). Równości tych dwóch zbiorów dowiedziemy przez sprzeczność. Załóżmy, że istnieje \xi\in\partial F({\bar{\mathbf{x}}})\setminus A^{T}\partial f(A{\bar{\mathbf{x}}}). Zbiór A^{T}\partial f(A{\bar{\mathbf{x}}}) jest wypukły i domknięty, jako liniowy obraz zbioru wypukłego i domkniętego. Zastosujemy silne twierdzenie o oddzielaniu, aby oddzielić go od zbioru jednoelementowego \{\xi\}. Dostajemy \mu\in\mathbb{R}^{m} oraz b\in\mathbb{R}, takie że

\mu^{T}A^{T}\tilde{\xi}<b<\mu^{T}\xi,\qquad\forall\ \tilde{\xi}\in\partial f(A{\bar{\mathbf{x}}}).

Biorąc supremum po \tilde{\xi}\in\partial f(A{\bar{\mathbf{x}}}) po lewej stronie i stosując tw. 3.11 otrzymujemy f^{{\prime}}(A{\bar{\mathbf{x}}};A\mu)\le b. Prawą stronę możemy również oszacować przez pochodną kierunkową: \mu^{T}\xi\le F^{{\prime}}({\bar{\mathbf{x}}};\mu). Podsumowując:

f^{{\prime}}(A{\bar{\mathbf{x}}};A\mu)<F^{{\prime}}({\bar{\mathbf{x}}};\mu).

Jednak z własności pochodnych kierunkowych natychmiast wnioskujemy, że F^{{\prime}}({\bar{\mathbf{x}}};\mathbf{d})=f^{{\prime}}(A{\bar{\mathbf{x}}};A\mathbf{d}) dla dowolnego \mathbf{d}\in\mathbb{R}^{m}. Mamy zatem sprzeczność. Dowodzi to, iż zbiór \partial F({\bar{\mathbf{x}}})\setminus A^{T}\partial f(A{\bar{\mathbf{x}}}) jest pusty.

3.6. Zadania

Ćwiczenie 3.1

Niech U,V\subset\mathbb{R}^{n} będą zbiorami wypukłymi. Wykaż, że

  1. U\cap V jest zbiorem wypukłym.

  2. U\cup V może nie być zbiorem wypukłym.

Ćwiczenie 3.2

Czy zbiór \{(x_{1},x_{2},x_{3})\in\mathbb{R}^{3}:\  x_{1}^{6}+x_{1}^{2}+x_{2}x_{3}+x_{3}^{2}\le 1\} jest zbiorem wypukłym?

Ćwiczenie 3.3

Udowodnij lemat 3.1.

Ćwiczenie 3.4

Niech

W_{1}=\{(x_{1},x_{2}):\  x_{2}\ge e^{{-x_{1}}}\},\qquad W_{2}=\{(x_{1},x_{2}):\  x_{2}\le-e^{{-x_{1}}}\}.

Wykaż, że zbiory W_{1},W_{2} są wypukłe i rozłączne. Znajdź prostą (hiperpłaszczyznę) je dzielącą. Czy istnieje hiperpłaszczyzna dzieląca ściśle te zbiory (w sensie mocnego twierdzenia o oddzielaniu)?

Ćwiczenie 3.5

Niech W_{1},W_{2}\subset\mathbb{R}^{n} będą zbiorami wypukłymi. Udowodnij, że \inf\{\|\mathbf{x}-\mathbf{y}\|:\ \mathbf{x}\in W_{1},\quad\mathbf{y}\in W_{2}\}>0 wtw, gdy istnieje hiperpłaszczyzna ściśle (w sensie mocnego tw. o oddzielaniu) oddzielająca te zbiory.

Ćwiczenie 3.6

Niech \mathbb{X}\subset\mathbb{R}^{n} będzie dowolnym zbiorem. Zdefiniujmy zbiór \tilde{\mathbb{X}} jako zbiór takich punktów \mathbf{x}\in\mathbb{R}^{n}, dla których istnieje liczba naturalna m\in\mathbb{N}, zależna od punktu, wektor [\lambda _{1},\ldots,\lambda _{m}]\in[0,1]^{m} o tej własności, że \sum _{{i=1}}^{m}\lambda _{i}=1, oraz \mathbf{x}_{1},\ldots,\mathbf{x}_{m}\in\mathbb{X} i

\mathbf{x}=\sum _{{i=1}}^{m}\lambda _{i}\mathbf{x}_{i}.

Udowodnij, że

  1. \tilde{\mathbb{X}} jest zbiorem wypukłym.

  2. \tilde{\mathbb{X}} jest najmniejszym zbiorem wypukłym zawierającym \mathbb{X}.

  3. W definicji zbioru \tilde{\mathbb{X}} można założyć, że m\le n+1, gdzie n jest wymiarem przestrzeni (Tw. Caratheodory'ego).

Zbiór \tilde{X} nazywa się otoczką wypukłą zbioru \mathbb{X} i oznaczane jest \text{conv}(\mathbb{X}).

Ćwiczenie 3.7

Udowodnij twierdzenie 3.5.

Ćwiczenie 3.8

Udowodnij twierdzenie 3.6.

Ćwiczenie 3.9

Znajdź przykład zbioru W\subseteq\mathbb{R}^{n} i funkcji wypukłej f:W\to\mathbb{R}, która nie jest ciągła na całym zbiorze W.

Wskazówka: 

Twierdzenie 3.7 pomoże w wyborze zbioru W.

Ćwiczenie 3.10

Niech W\subseteq\mathbb{R}^{n} będzie zbiorem wypukłym i otwartym, zaś f:W\to\mathbb{R} funkcją różniczkowalną. Udowodnij następującą równoważność: f jest wypukła wtw, gdy

\big(Df(\mathbf{y})-Df(\mathbf{x})\big)(\mathbf{y}-\mathbf{x})\ge 0,\qquad\forall\,\mathbf{x},\mathbf{y}\in W.
Ćwiczenie 3.11

Udowodnij: Niech W\subset\mathbb{R}^{n}, wypukły, zaś I dowolny zbiór. Jeśli funkcje f_{i}:W\to\mathbb{R}, i\in I, są wypukłe, to f(\mathbf{x})=\sup _{{i\in I}}f_{i}(\mathbf{x}) jest wypukła ze zbiorem wartości \mathbb{R}\cup\{\infty\}.

Ćwiczenie 3.12

Udowodnij: Niech W\subset\mathbb{R}^{n}, wypukły. Jeśli funkcje f_{i}:W\to\mathbb{R}, i=1,2,\ldots,m, są wypukłe i \alpha _{i}>0 dla i=1,2,\ldots,m, to funkcja f=\sum _{{i=1}}^{m}\alpha _{i}f_{i} jest wypukła. Jeśli jedna z funkcji f_{i} jest ściśle wypukła, to f jest również ściśle wypukła.

Ćwiczenie 3.13

Udowodnij: Niech W\subset\mathbb{R}^{n}, wypukły, zaś A\subset\mathbb{R}^{m} wypukły, zwarty. Jeśli funkcja h:W\times A\to\mathbb{R} jest wypukła i ciągła, to

f(\mathbf{x})=\inf _{{\mathbf{a}\in A}}h(\mathbf{x},\mathbf{a}),\qquad\mathbf{x}\in W,

jest wypukła.

Wskazówka: 

Korzystając ze zwartości A i ciągłości h, dla każdego \mathbf{x} istnieje \mathbf{a}(\mathbf{x})\in A realizujący infimum. Dowodzimy teraz z definicji funkcji wypukłej.

Ćwiczenie 3.14

Udowodnij uogólnienie twierdzenia z ćwiczenia 3.13: opuścimy zwartość A i ciągłość h. Niech W\subset\mathbb{R}^{n}, A\subset\mathbb{R}^{m} wypukłe zbiory. Jeśli funkcja h:W\times A\to\mathbb{R} jest wypukła i ograniczona z dołu, to

f(\mathbf{x})=\inf _{{\mathbf{a}\in A}}h(\mathbf{x},\mathbf{a}),\qquad\mathbf{x}\in W,

jest wypukła.

Ćwiczenie 3.15

Skonstruuj przykład, który pokaże, że założenie o ograniczoności z dołu nie może być pominięte w twierdzeniu z ćw. 3.14.

Ćwiczenie 3.16

Udowodnij, że funkcja odległości od zbioru wypukłego jest funkcją wypukłą. Podaj przykład wskazujący na konieczność wypukłości zbioru.

Ćwiczenie 3.17

Udowodnij: Niech f:\mathbb{R}^{n}\to\mathbb{R} wypukła. Jeśli h:\mathbb{R}^{m}\to\mathbb{R}^{n} afiniczna, to złożenie f\circ h jest funkcją wypukłą.

Ćwiczenie 3.18

Udowodnij: Niech W\subset\mathbb{R}^{n}, wypukły. Jeśli f:W\to\mathbb{R} jest funkcją wypukłą i g:\mathbb{R}\to\mathbb{R} jest wypukła i niemalejąca, to g\circ f jest funkcją wypukłą. Kiedy g\circ f jest ściśle wypukła?

Stwórz analog powyższego twierdzenia dla funkcji wklęsłych.

Ćwiczenie 3.19

Udowodnij: Niech W\subset\mathbb{R}^{n} wypukły. Jeśli f:W\to\mathbb{R} jest funkcją (ściśle) wklęsłą i f>0, to funkcja 1/f jest (ściśle) wypukła.

Ćwiczenie 3.20

Czy jeśli f:\mathbb{R}^{n}\to\mathbb{R} i g:\mathbb{R}\to\mathbb{R} wypukłe, to g\circ f:\mathbb{R}^{n}\to\mathbb{R} jest wypukła?

Ćwiczenie 3.21

Udowodnij, że funkcja f(x_{1},x_{2})=e^{{x_{1}^{2}-x_{2}}} jest wypukła.

Ćwiczenie 3.22

Niech W\subset\mathbb{R}^{n} i funkcja f:W\to\mathbb{R} klasy C^{2}. Załóżmy ponadto, że D^{2}f(\mathbf{x})\ge 0 dla każdego \mathbf{x}\in W (tzn. Hesjan jest nieujemnie określony). Rozstrzygnij, który z następujących warunków jest wystarczający, by zdanie

Df({\bar{\mathbf{x}}})=\mathbf{0}\qquad\implies\qquad\text{w ${\bar{\mathbf{x}}}$ jest globalne minimum}

było prawdziwe:

  • W=\mathbb{R}^{n},

  • W jest wypukły i otwarty,

  • W jest wypukły,

  • W jest otwarty.

Ćwiczenie 3.23

Znajdź przykład zbioru \mathbb{X}\subset\mathbb{R}^{n} oraz funkcji f:\mathbb{X}\to\mathbb{R} klasy C^{2}, takiej że

  1. D^{2}f(\mathbf{x})\ge 0 (tzn. hesjan jest nieujemnie określony) dla każdego \mathbf{x}\in\mathbb{X},

  2. istnieje punkt {\bar{\mathbf{x}}}\in\mathbb{X}, w którym jest minimum lokalne funkcji f, ale nie jest ono globalne.

Ćwiczenie 3.24

Niech W\subset\mathbb{R}^{n} będzie zbiorem wypukłym, zaś f:W\to\mathbb{R} funkcją wypukłą. Udowodnij, że \partial f(\mathbf{x}) jest zbiorem wypukłym i domkniętym.

Ćwiczenie 3.25

Niech A,B\subset\mathbb{R}^{n} będą zbiorami wypukłymi zwartymi. Udowodnij, że suma algebraiczna tych zbiorów

A+B=\{\mathbf{a}+\mathbf{b}:\ \mathbf{a}\in A,\ \mathbf{b}\in B\}

jest zbiorem zwartym i wypukłym.

Ćwiczenie 3.26

Niech W\subset\mathbb{R}^{n} wypukły otwarty i f:W\to\mathbb{R} wypukła. Wykaż, że \xi\in\mathbb{R}^{n} jest subgradientem f w {\bar{\mathbf{x}}}\in W wtw, gdy odwzorowanie \mathbf{x}\mapsto\xi^{T}\mathbf{x}-f(\mathbf{x}) osiąga swoje maksimum w {\bar{\mathbf{x}}}.

Ćwiczenie 3.27

Znajdź subróżniczkę funkcji \mathbb{R}^{n}\ni\mathbf{x}\mapsto\|\mathbf{x}\|.

Ćwiczenie 3.28

Niech A będzie macierzą n\times n symetryczną i nieujemnie określoną. Udowodnij, że f(\mathbf{x})=\sqrt{\mathbf{x}^{T}A\mathbf{x}}, \mathbf{x}\in\mathbb{R}^{n}, jest funkcją wypukłą i znajdź jej subróżniczkę.

Ćwiczenie 3.29

Wykaż, że dla skalarnej funkcji wypukłej f:(a,b)\to\mathbb{R} mamy

\partial f(x)=[f^{{\prime}}(x-),f^{{\prime}}(x+)],

gdzie f^{{\prime}}(x\pm) oznaczają prawo- i lewo-stronne pochodne w punkcie x\in(a,b).

Ćwiczenie 3.30

Niech f:\mathbb{R}^{n}\to\mathbb{R} wypukła, \mathbf{x},\mathbf{y}\in\mathbb{R}^{n} ustalone wektory. Zdefiniujmy g(t)=f(t\mathbf{x}+(1-t)\mathbf{y}), t\in\mathbb{R}. Wykaż, że g jest wypukła oraz

\partial g(t)=(\mathbf{x}-\mathbf{y})^{T}\partial f\big(t\mathbf{x}+(1-t)\mathbf{y}\big).
Ćwiczenie 3.31

Wykaż, że funkcja f(x)=\max(-2x+5,3x^{2}-1) jest wypukła na \mathbb{R} i znajdź jej subróżniczkę.

Ćwiczenie 3.32

Niech f_{W}(\mathbf{x})=\inf _{{\mathbf{y}\in W}}\| x-y\|, \mathbf{x}\in\mathbb{R}^{n}, gdzie W\subset\mathbb{R}^{n} jest zbiorem wypukłym. Znajdź subróżniczkę w następujących przypadkach:

  • W=\{{\bar{\mathbf{x}}}\} dla pewnego {\bar{\mathbf{x}}}\in\mathbb{R}^{n},

  • W=\mathop{\rm conv}(\{(0,0),(1,0)\})\subset\mathbb{R}^{2}, tzn. W jest odcinkiem,

  • W=\mathop{\rm conv}(\{(0,0),(1,0),(0,1),(1,1)\})\subset\mathbb{R}^{2}, tzn. W jest kwadratem.

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.