Zagadnienia

4.1 Problem minimalizacyjny
4.2 Funkcje pseudowypukłe
4.3 Maksymalizacja funkcji wypukłej
4.4 Zadania

4. Ekstrema funkcji wypukłej z ograniczeniami

4.1. Problem minimalizacyjny

Niech $W$ będzie niepustym wypukłym podzbiorem $\mathbb{R}^{n}$ , zaś $f:W\to\mathbb{R}$ będzie funkcją wypukłą. Rozważmy problem minimalizacji funkcji $f$ na zbiorze $W$ :

$\begin{cases}f(\mathbf{x})\longrightarrow\min,&\\ \mathbf{x}\in W.\end{cases}$

(4.1)

Przypomnijmy, że punktami dopuszczalnymi nazywamy elementy zbioru $W$ . Rozwiązaniem globalnym nazywamy taki punkt ${\bar{\mathbf{x}}}\in W$ , że $f({\bar{\mathbf{x}}})\le f(\mathbf{x})$ dla każdego $\mathbf{x}\in W$ . Rozwiązaniem lokalnym jest taki punkt ${\bar{\mathbf{x}}}\in W$ , że istnieje $\varepsilon>0$ , dla którego $f({\bar{\mathbf{x}}})\le f(\mathbf{x})$ , jeśli $\mathbf{x}\in W\cap B({\bar{\mathbf{x}}},\varepsilon)$ . Rozwiązanie jest ścisłe, jeśli $f({\bar{\mathbf{x}}})<f(\mathbf{x})$ dla $\mathbf{x}\in W\cap B({\bar{\mathbf{x}}},\varepsilon)$ i $\mathbf{x}\ne{\bar{\mathbf{x}}}$ . Innymi słowy, ${\bar{\mathbf{x}}}$ jest rozwiązaniem lokalnym, jeśli ${\bar{\mathbf{x}}}$ jest minimum funkcji $f$ na pewnym otoczeniu ${\bar{\mathbf{x}}}$ .

Twierdzenie 4.1

Niech $W\subset R^{n}$ wypukły, $f:W\to\mathbb{R}$ wypukła. Jeśli ${\bar{\mathbf{x}}}\in W$ będzie rozwiązaniem lokalnym (4.1), to:

I) ${\bar{\mathbf{x}}}$ jest rozwiązaniem globalnym,
II) Zbiór rozwiązań globalnych jest wypukły.
III) Jeśli $f$ jest ściśle wypukła, to ${\bar{\mathbf{x}}}$ jest ścisłym rozwiązaniem lokalnym.
IV) Jeśli ${\bar{\mathbf{x}}}$ jest ścisłym rozwiązaniem lokalnym, to ${\bar{\mathbf{x}}}$ jest jedynym rozwiązaniem globalnym.

Zauważmy, że w powyższym twierdzeniu nie zakładamy różniczkowalności funkcji $f$ .

Dowód twierdzenia 4.1

(I): Dowód przez sprzeczność. Przypuśćmy, że istnieje $\mathbf{x}^{*}\in W$ takie że $f(\mathbf{x}^{*})<f({\bar{\mathbf{x}}})$ . Ponieważ ${\bar{\mathbf{x}}}$ jest rozwiązaniem lokalnym, to $f({\bar{\mathbf{x}}})\le f(\mathbf{x})$ dla $\mathbf{x}\in W\cap B({\bar{\mathbf{x}}},\varepsilon)$ i $\varepsilon>0$ . Z wypukłości zbioru $W$ wynika, iż odcinek łączący ${\bar{\mathbf{x}}}$ i $\mathbf{x}^{*}$ znajduje się w zbiorze $W$ . Ma on więc niepuste przecięcie z kulą $B({\bar{\mathbf{x}}},\varepsilon)$ : dla pewnego $\lambda\in(0,1)$ mamy $\lambda{\bar{\mathbf{x}}}+(1-\lambda)\mathbf{x}^{*}\in B({\bar{\mathbf{x}}},\varepsilon)$ . Z wypukłości $f$ dostajemy

$f\big(\lambda{\bar{\mathbf{x}}}+(1-\lambda)\mathbf{x}^{*}\big)\le\lambda f({\bar{\mathbf{x}}})+(1-\lambda)f(\mathbf{x}^{*})<f({\bar{\mathbf{x}}}),$

co przeczy lokalnej optymalności ${\bar{\mathbf{x}}}$ .

(II) Pozostawione jako ćwiczenie.

(III) Wynika wprost z definicji ścisłej wypukłości.

(IV) Pozostawione jako ćwiczenie.

∎

Dotychczas pokazaliśmy, że warunkiem koniecznym i dostatecznym minimum funkcji wypukłej na zbiorze wypukłym i otwartym jest zerowanie się pochodnej/gradientu. Uogólnimy teraz te wyniki na przypadek dowolnych zbiorów wypukłych.

Twierdzenie 4.2

Niech $W\subset R^{n}$ wypukły, $f:W\to\mathbb{R}$ wypukła. Jeśli $f$ jest różniczkowalna w punkcie ${\bar{\mathbf{x}}}\in W$ , to mamy następującą równoważność: ${\bar{\mathbf{x}}}$ jest rozwiązaniem (4.1) wtw, gdy $Df({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})\ge 0$ dla każdego $\mathbf{x}\in W$ .

Uwaga 4.1

W sformułowaniu powyższego twierdzenia, jak i w wielu miejscach w dalszej części tych notatek, zastosowany jest następujący skrót myślowy. Aby mówić o różniczkowalności funkcji $f$ w punkcie ${\bar{\mathbf{x}}}\in W$ , musi być ona określona w pewnym otoczeniu ${\bar{\mathbf{x}}}$ , czyli w kuli $B({\bar{\mathbf{x}}},\varepsilon)$ dla pewnego $\varepsilon>0$ . Jeśli ${\bar{\mathbf{x}}}$ jest na brzegu $W$ , to zakładać będziemy, że $f$ jest określona na $W\cup B({\bar{\mathbf{x}}},\varepsilon)$ mimo, że jest to pominięte, dla prostoty notacji, w założeniach twierdzenia.

Uwaga 4.2

Jeśli ${\bar{\mathbf{x}}}\in\mathop{\rm int}W$ , to warunek powyższy sprowadza się do warunku zerowania się pochodnej $Df({\bar{\mathbf{x}}})=0$ .

Dowód tw. 4.2

Załóżmy, że $Df({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})\ge 0$ dla każdego $\mathbf{x}\in W$ . Ustalmy $\mathbf{x}\in W$ . Na mocy twierdzenia 3.8

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

Z założenia, drugi składnik jest nieujemny, co pociąga $f(\mathbf{x})\ge f({\bar{\mathbf{x}}})$ . Z dowolności $\mathbf{x}\in W$ dostajemy tezę.

Załóżmy teraz, że ${\bar{\mathbf{x}}}$ jest rozwiązaniem (4.1). Ustalmy $\mathbf{x}\in W$ . Zauważmy, że wypukłość $W$ implikuje ${\bar{\mathbf{x}}}+\lambda(\mathbf{x}-{\bar{\mathbf{x}}})=(1-\lambda){\bar{\mathbf{x}}}+\lambda\mathbf{x}\in W$ dla $\lambda\in[0,1]$ . Z definicji pochodnej mamy

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

Ponieważ w punkcie ${\bar{\mathbf{x}}}$ jest minimum, to $f\big({\bar{\mathbf{x}}}+\lambda(\mathbf{x}-{\bar{\mathbf{x}}})\big)\ge f({\bar{\mathbf{x}}})$ . Stąd $Df({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})\ge 0$ .

∎

Z dowodu powyższego twierdzenia dostajemy użyteczny wniosek.

Wniosek 4.1

Jeśli ${\bar{\mathbf{x}}}\in W$ , gdzie $W\subset\mathbb{R}^{n}$ jest wypukły, jest rozwiązaniem lokalnym (4.1) dla funkcji $f:W\to\mathbb{R}$ (niekoniecznie wypukłej) różniczkowalnej w ${\bar{\mathbf{x}}}$ , to $Df({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})\ge 0$ dla każdego $\mathbf{x}\in W$ .

Przykład 4.1

Rozważmy problem minimalizacyjny:

$\begin{cases}\Big(x_{1}-\frac{3}{2}\Big)^{2}+(x_{2}-5)^{2}\longrightarrow\min,&\\ -x_{1}+x_{2}\le 2,&\\ 2x_{1}+3x_{2}\le 11,&\\ x_{1},x_{2}\ge 0,&\end{cases}$

Zbiór $W$ zadany jest przez ograniczenia liniowe (patrz rysunek 4.1):

$W=\{(x_{1},x_{2})\in\mathbb{R}^{2}:x_{1},x_{2}\ge 0,\ -x_{1}+x_{2}\le 2,\ 2x_{1}+3x_{2}\le 11\}.$

$Wykres zbioru $W=\{(x_{1},x_{2})\in\mathbb{R}^{n}:x_{1},x_{2}\ge 0,\ -x_{1}+x_{2}\le 2,\ 2x_{1}+3x_{2}\le 11\}$$

Rys. 4.1. Zbiór punktów dopuszczalnych.

Łatwo sprawdzić, że jest on wypukły. Funkcja $f(x_{1},x_{2})=(x_{1}-\frac{3}{2})^{2}+(x_{2}-5)^{2}$ jest ściśle wypukła: jej hesjan wynosi

$D^{2}f(x_{1},x_{2})=\begin{bmatrix}2&0\\ 0&2\end{bmatrix}.$

Na mocy tw. 4.1 minimum jest jednoznaczne. Policzmy gradient $f$ :

$Df(x_{1},x_{2})=(2x_{1}-3,2x_{2}-10).$

Gradient zeruje się w punkcie $(\frac{3}{2},5)$ , który jest poza zbiorem $W$ . Minimum należy zatem szukać na brzegu $W$ . Nie mamy jeszcze narzędzi ułatwiających znalezienie tego punktu. Zgadujemy… Sprawdźmy wierzchołek ${\bar{\mathbf{x}}}=(1,3)$ . Gradient w tym punkcie wynosi $(-1,-4)$ . Zauważmy, że wektory $\mathbf{x}-{\bar{\mathbf{x}}}$ są kombinacjami liniowymi dodatnimi wektorów $\mathbf{x}_{1}=(0,2)-(1,3)=(-1,-1)$ i $\mathbf{x}_{2}=(\frac{11}{2},0)-(1,3)=(\frac{9}{2},-3)$ , tzn. $\mathbf{x}-{\bar{\mathbf{x}}}=a_{1}\mathbf{x}_{1}+a_{2}\mathbf{x}_{2}$ dla pewnych $a_{1},a_{2}\ge 0$ . Wystarczy zatem sprawdzić, że $Df({\bar{\mathbf{x}}})(\mathbf{x}_{1})\ge 0$ i $Df({\bar{\mathbf{x}}})\mathbf{x}_{2}\ge 0$ :

		$\displaystyle Df({\bar{\mathbf{x}}})(\mathbf{x}_{1})=(-1,-4)\begin{pmatrix}-1\\ -1\end{pmatrix}=5,$
		$\displaystyle Df({\bar{\mathbf{x}}})(\mathbf{x}_{2})=(-1,-4)\begin{pmatrix}9/2\\ -3\end{pmatrix}=16\frac{1}{2}.$

Na mocy tw. 4.2 minimum jest rzeczywiście w punkcie $(1,3)$ .

Rozszerzymy teraz twierdzenie 4.2 na klasę funkcji wypukłych nieróżniczkowalnych – skorzystamy z wprowadzonego w poprzednim rozdziale pojęcia subróżniczki.

Twierdzenie 4.3

Niech $\tilde{W}\subset R^{n}$ wypukły otwarty, $f:\tilde{W}\to\mathbb{R}$ wypukła. Załóżmy, że zbiór punktów dopuszczalnych $W$ jest wypukłym podzbiorem $\tilde{W}$ . Mamy następującą równoważność: ${\bar{\mathbf{x}}}$ jest rozwiązaniem (4.1) wtw, gdy istnieje $\xi\in\partial f({\bar{\mathbf{x}}})$ , takie że $\xi^{T}(\mathbf{x}-{\bar{\mathbf{x}}})\ge 0$ dla każdego $\mathbf{x}\in W$ .

Wniosek 4.2

Niech $W\subset R^{n}$ wypukły otwarty, $f:\tilde{W}\to\mathbb{R}$ wypukła. Wówczas $f$ ma w ${\bar{\mathbf{x}}}\in W$ minimum globalne wtw, gdy $\mathbf{0}\in\partial f({\bar{\mathbf{x}}})$ .

Dowód twierdzenia 4.3

Zacznijmy od łatwiejszej implikacji. Załóżmy, że istnieje $\xi\in\partial f({\bar{\mathbf{x}}})$ , takie że $\xi^{T}(\mathbf{x}-{\bar{\mathbf{x}}})\ge 0$ dla każdego $\mathbf{x}\in W$ . Z faktu, że $\xi$ jest subgradientem wynika, że

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

Wystarczy teraz skorzystać z założenia, żeby zauważyć, że $f(\mathbf{x})\ge f({\bar{\mathbf{x}}})$ dla $\mathbf{x}\in W$ , czyli ${\bar{\mathbf{x}}}$ jest rozwiązaniem (4.1).

Załóżmy teraz, że ${\bar{\mathbf{x}}}\in W$ jest rozwiązaniem (4.1). Zdefiniujmy dwa zbiory

	$\displaystyle C_{1}$	$\displaystyle=\big\{(\mathbf{x},z)\in\mathbb{R}^{n}\times\mathbb{R}:\ \mathbf{x}\in\tilde{W},\ z>f(\mathbf{x})-f({\bar{\mathbf{x}}})\big\},$
	$\displaystyle C_{2}$	$\displaystyle=\big\{(\mathbf{x},z)\in\mathbb{R}^{n}\times\mathbb{R}:\ \mathbf{x}\in W,\ z\le 0\big\}.$

Oba zbiory są wypukłe, $C_{1}$ ma niepuste wnętrze (zbiór $C_{2}$ ma puste wnętrze, jeśli $W$ ma puste wnętrze). Z faktu, że punkt ${\bar{\mathbf{x}}}$ jest rozwiązaniem (4.1) wynika, że $C_{1}\cap C_{2}=\emptyset$ . Stosujemy słabe twierdzenie o oddzielaniu: istnieje niezerowy wektor $(\mu,\gamma)\in\mathbb{R}^{n}\times\mathbb{R}$ i stała $b\in\mathbb{R}$ , takie że

$\begin{aligned}\displaystyle&\displaystyle\mu^{T}\mathbf{x}+\gamma z\le b,\qquad\forall\ \mathbf{x}\in\tilde{W},\ z>f(\mathbf{x})-f({\bar{\mathbf{x}}})\\ \displaystyle&\displaystyle\mu^{T}\mathbf{x}+\gamma z\ge b,\qquad\forall\ \mathbf{x}\in W,\ z\le 0.\end{aligned}$

(4.2)

Zanim przejdziemy do analitycznych rozważań popatrzmy na geometryczny obraz. Zauważmy, że zbiory $C_{1}$ i $C_{2}$ ,,stykają” się w punkcie $({\bar{\mathbf{x}}},0)$ . Hiperpłaszczyzna oddzielająca te zbiory musi zatem przechodzić przez ten punkt. Jest ona styczna do wykresu funkcji $\mathbf{x}\mapsto f(\mathbf{x})-f({\bar{\mathbf{x}}})$ – pierwsza grupa współrzędnych $\mu$ wektora $(\mu,\gamma)$ do niej normalnego, z dokładnością do długości i zwrotu, wyznacza subgradient tego odwzorowania w punkcie ${\bar{\mathbf{x}}}$ (a zatem także subgradient $f$ ). Z faktu, że ta hiperpłaszczyzna jest również styczna do $C_{2}$ dostajemy $\mu^{T}(\mathbf{x}-{\bar{\mathbf{x}}})\ge 0$ .

Udowodnijmy to teraz analitycznie. Odejmijmy od obu stron nierówności (4.2) $\mu^{T}{\bar{\mathbf{x}}}$ :

		$\displaystyle\mu^{T}(\mathbf{x}-{\bar{\mathbf{x}}})+\gamma z\le\tilde{b},\qquad\forall\ \mathbf{x}\in\tilde{W},\ z>f(\mathbf{x})-f({\bar{\mathbf{x}}})$		(4.3)
		$\displaystyle\mu^{T}(\mathbf{x}-{\bar{\mathbf{x}}})+\gamma z\ge\tilde{b},\qquad\forall\ \mathbf{x}\in W,\ z\le 0,$		(4.4)

gdzie $\tilde{b}=b-\mu^{T}{\bar{\mathbf{x}}}$ . Zauważmy najpierw, że $\gamma$ nie może być większa od zera. Wówczas, wykorzystując dowolność $z\le 0$ , dostajemy sprzeczność z (4.4). Kładąc w (4.4) $\mathbf{x}={\bar{\mathbf{x}}}$ i $z=0$ , otrzymujemy $\tilde{b}\le 0$ . Wnioskujemy stąd, że niedopuszczalne jest $\gamma=0$ : z nierówności (4.3) (pamiętając o otwartości $\tilde{W}$ ) dostalibyśmy bowiem $\mu=\mathbf{0}$ , co przeczyłoby niezerowości wektora $(\mu,\gamma)$ . Wykazaliśmy więc, że

$\gamma<0.$

Biorąc $\mathbf{x}={\bar{\mathbf{x}}}$ , nierówność (4.3) upraszcza się do $\gamma z\le\tilde{b}$ dla $z>0$ . Stąd $\tilde{b}\ge 0$ . Łącząc to z poprzednio otrzymaną nierównością $\tilde{b}\le 0$ dostajemy

$\tilde{b}=0.$

Przechodząc w (4.3) z $z$ do $f(\mathbf{x})-f({\bar{\mathbf{x}}})$ mamy

$\mu^{T}(\mathbf{x}-{\bar{\mathbf{x}}})+\gamma\big(f(\mathbf{x})-f({\bar{\mathbf{x}}})\big)\le 0.$

Dzieląc obie strony przez $\gamma$ i pamiętając, że $\gamma<0$ dostajemy

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

co dowodzi, że $-\frac{\mu}{\gamma}\in\partial f({\bar{\mathbf{x}}})$ . Kładąc $z=0$ w (4.4) otrzymujemy $\mu^{T}(\mathbf{x}-{\bar{\mathbf{x}}})\ge 0$ . Dzielimy obie strony przez $-\gamma>0$ :

$-\frac{\mu^{T}}{\gamma}(\mathbf{x}-{\bar{\mathbf{x}}})\ge 0,$

co kończy dowód.

∎

4.2. Funkcje pseudowypukłe

W tym podrozdziale wprowadzimy rodzinę funkcji, dla której spełniony jest warunek:

$Df({\bar{\mathbf{x}}})=0\quad\Longleftrightarrow\quad\text{w ${\bar{\mathbf{x}}}$ jest minimum globalne}.$

Okazuje się, że rodzina ta obejmuje nie tylko funkcje wypukłe.

Definicja 4.1

Niech $W\subset\mathbb{R}^{n}$ będzie otwarty i niepusty, zaś $f:W\to\mathbb{R}$ – różniczkowalna w $W$ . Funkcja $f$ jest pseudowypukła w ${\bar{\mathbf{x}}}\in W$ , jeśli

$\forall\ \mathbf{y}\in W:\qquad Df({\bar{\mathbf{x}}})(\mathbf{y}-{\bar{\mathbf{x}}})\ge 0\implies f(\mathbf{y})\ge f({\bar{\mathbf{x}}}).$

Funkcja $f$ jest ściśle pseudowypukła w ${\bar{\mathbf{x}}}\in W$ , jeśli

$\forall\ \mathbf{y}\in W:\qquad Df({\bar{\mathbf{x}}})(\mathbf{y}-{\bar{\mathbf{x}}})\ge 0,\ {\bar{\mathbf{x}}}\ne\mathbf{y}\implies f(\mathbf{y})>f({\bar{\mathbf{x}}}).$

Funkcja $f$ jest (ściśle) pseudowypukła, jeśli jest ona (ściśle) pseudowypukła w każdym punkcie ${\bar{\mathbf{x}}}\in W$ .

Funkcja $f$ jest (ściśle) pseudowklęsła, jeśli $(-f)$ jest (ściśle) pseudowypukła.

Uwaga 4.3

Implikacja w definicji pseudowypukłości ma równoważną postać:

$\forall\ \mathbf{y}\in W:\qquad f(\mathbf{y})<f({\bar{\mathbf{x}}})\implies Df({\bar{\mathbf{x}}})(\mathbf{y}-{\bar{\mathbf{x}}})<0.$

Rys. 4.2. Przykłady funkcji pseudowypukłych i pseudowklęsłych.

Na rysunku 4.2 znajdują się przykłady jednowymiarowych funkcji pseudowypukłych i pseudowklęsłych.

Lemat 4.1

Niech $f:W\to\mathbb{R}$ , gdzie $W\subset\mathbb{R}^{n}$ wypukły, otwarty i niepusty. Jeśli $f$ jest (ściśle) wypukła i różniczkowalna na $W$ , to $f$ jest (ściśle) pseudowypukła.

Dowód

Załóżmy, że $f$ wypukła. Na mocy tw. 3.8 dla dowolnych ${\bar{\mathbf{x}}},\mathbf{x}\in W$ mamy

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

Jeśli zatem $Df({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})\ge 0$ , to $f(\mathbf{x})\ge f({\bar{\mathbf{x}}})$ i $f$ jest pseudowypukła. W analogiczny sposób dowodzimy, że ścisła wypukłość pociąga ścisłą pseudowypukłość.

∎

Lemat 4.2

Niech $f:W\to\mathbb{R}$ , gdzie $W\subset\mathbb{R}^{n}$ , otwarty, niepusty, będzie funkcją pseudowypukłą w ${\bar{\mathbf{x}}}\in W$ . Wówczas ${\bar{\mathbf{x}}}$ jest minimum globalnym wtw, gdy $Df({\bar{\mathbf{x}}})=0$ .

Dowód

Identyczny jak dowód wniosku 3.2.

∎

Dowód poniższego lematu jest identyczny jak dowód twierdzenia 4.2.

Lemat 4.3

Niech $W\subset R^{n}$ wypukły, $f:W\to\mathbb{R}$ pseudowypukła. Mamy następującą równoważność: ${\bar{\mathbf{x}}}$ jest rozwiązaniem (4.1) wtw, gdy $Df({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})\ge 0$ dla każdego $\mathbf{x}\in W$ .

4.3. Maksymalizacja funkcji wypukłej

Definicja 4.2

Punktem ekstremalnym zbioru wypukłego $W\subset\mathbb{R}^{n}$ nazwiemy taki punkt ${\bar{\mathbf{x}}}\in W$ , który nie jest punktem wewnętrznym żadnego odcinka zawartego w $W$ , tj. jeśli ${\bar{\mathbf{x}}}=\lambda\mathbf{x}_{1}+(1-\lambda)\mathbf{x}_{2}$ dla pewnych $\lambda\in(0,1)$ i $\mathbf{x}_{1},\mathbf{x}_{2}\in W$ , to $\mathbf{x}_{1}=\mathbf{x}_{2}={\bar{\mathbf{x}}}$ .

Definicja 4.3

Otoczką wypukłą punktów $(\mathbf{x}_{i})_{{i\in I}}$ nazywamy zbiór punktów będących kombinacją wypukłą skończonej liczby spośród punktów $(\mathbf{x}_{i})$ .

Otoczkę wypukłą można równoważnie definiować jako najmniejszy zbiór wypukły zawierający punkty $(\mathbf{x}_{i})_{{i\in I}}$ .

Przedstawimy teraz prostą wersję twierdzenia Kreina-Milmana.

Twierdzenie 4.4

Niech $U\subset\mathbb{R}^{n}$ będzie zbiorem wypukłym i zwartym. Jest on wówczas otoczką wypukłą swoich punktów ekstremalnych.

Przed przejściem do dowodu powyższego twierdzenia wprowadzimy niezbędne pojęcia. Przypomnijmy, że przestrzenią afiniczną nazywamy zbiór $A$ , taki że $\sum _{{i=1}}^{k}\lambda _{i}\mathbf{x}_{i}\in A$ dla dowolnych $(\mathbf{x}_{i})\subset A$ i $(\lambda _{i})\subset\mathbb{R}$ takich że $\sum _{{i=1}}^{k}\lambda _{i}=1$ . Każda podprzestrzeń afiniczna $\mathbb{R}^{n}$ może zostać przesunięta tak, aby zawierała $\mathbf{0}$ . Staje się ona wówczas podprzestrzenią liniową. Wymiarem podprzestrzeni afinicznej nazywamy wymiar związanej z nią podprzestrzeni liniowej.

Definicja 4.4

Wymiarem zbioru wypukłego $U\subset\mathbb{R}^{n}$ nazywamy wymiar otoczki afinicznej $U$ , tzn. podprzestrzeni afinicznej generowanej przez U:

$\mathop{\rm aff}U=\{\sum _{{i=1}}^{k}\lambda _{i}\mathbf{x}_{i}:\ \mathbf{x}_{1},\ldots,\mathbf{x}_{k}\in U,\ \sum _{{i=1}}^{k}\lambda _{i}=1\}.$

Zapiszmy łatwe wnioski z powyższej definicji i rozważań ją poprzedzających:

Wniosek 4.3

$\$

Zbiór wypukły o wymiarze $m<n$ możemy traktować jako podzbiór przestrzeni $\mathbb{R}^{m}$ .
Zbiór wypukły w przestrzeni $\mathbb{R}^{n}$ ma niepuste wnętrze wtw, gdy jego wymiar wynosi $n$ .

Dotychczas rozważaliśmy hiperpłaszczyzny podpierające epigraf funkcji wypukłej. Teraz uogólnimy to pojęcie na dowolny zbiór wypukły.

Lemat 4.4

Niech $U\subset\mathbb{R}^{n}$ będzie zbiorem wypukłym o niepustym wnętrzu. Przez punkt brzegowy ${\bar{\mathbf{x}}}\in U$ przechodzi wówczas hiperpłaszczyzna, taka że zbiór $U$ leży w jednej z wyznaczonych przez nią półprzestrzeni. Hiperpłaszczyznę tą nazywamy hiperpłaszczyzną podpierającą zbiór $U$ w punkcie ${\bar{\mathbf{x}}}$ .

Dowód

Na mocy słabego twierdzenia o oddzielaniu zastosowanego do $U$ i $V=\{{\bar{\mathbf{x}}}\}$ (zauważmy, że $(\mathop{\rm int}U)\cap V=\emptyset$ ) istnieje $\mathbf{a}\in\mathbb{R}^{n}$ , takie że $\mathbf{a}^{T}\mathbf{x}\le\mathbf{a}^{T}{\bar{\mathbf{x}}}$ dla każdego $\mathbf{x}\in U$ . Szukaną hiperpłaszczyzną jest

$H=\{\mathbf{x}\in\mathbb{R}^{n}:\ \mathbf{a}^{T}\mathbf{x}=\mathbf{a}^{T}{\bar{\mathbf{x}}}\}.$

Zbiór $U$ zawarty jest w półprzestrzeni $\{\mathbf{x}\in\mathbb{R}^{n}:\ \mathbf{a}^{T}\mathbf{x}\le\mathbf{a}^{T}{\bar{\mathbf{x}}}\}$ .

∎

Dowód twierdzenia 4.4

Przeprowadzimy indukcję po wymiarze $m$ zbioru zwartego i wypukłego $U$ . Przypadki $m=0$ ( $U$ jest punktem) i $m=1$ ( $U$ jest odcinkiem) są trywialne. Czas na krok indukcyjny. Załóżmy, że każdy zbiór wypukły i zwarty o wymiarze nie większym od $m$ jest otoczką wypukłą swoich punktów ekstremalnych. Weźmy zbiór wypukły i zwarty $U$ o wymiarze $m+1$ . Zbiór ten traktujemy jako podzbiór $\mathbb{R}^{{m+1}}$ . Ma on wówczas niepuste wnętrze. Niech ${\bar{\mathbf{x}}}\in U$ .

Przypadek (I): ${\bar{\mathbf{x}}}$ leży na brzegu $U$ . Na mocy lematu 4.4 istnieje hiperpłaszczyzna podpierająca $H$ przechodząca przez ${\bar{\mathbf{x}}}$ . Zbiór $U_{{\bar{\mathbf{x}}}}=U\cap H$ jest wypukły, zwarty i o wymiarze co najwyżej $m$ . Na mocy założenia indukcyjnego punkt ${\bar{\mathbf{x}}}$ jest kombinacją wypukłą punktów ekstremalnych $U_{{\bar{\mathbf{x}}}}$ . Pozostaje już tylko wykazać, że punkty ekstremalne $U_{{\bar{\mathbf{x}}}}$ są punktami ekstremalnymi $U$ . Wynika to stąd, że żaden punkt $\mathbf{x}\in U_{{\bar{\mathbf{x}}}}$ nie może być przedstawiony jako kombinacja wypukła punktów, z których jeden lub oba nie należą do $U_{{\bar{\mathbf{x}}}}$ .

Przypadek (II): ${\bar{\mathbf{x}}}$ leży we wnętrzu $U$ . Przeprowadźmy przez ${\bar{\mathbf{x}}}$ dowolną prostą. Przecina ona brzeg $U$ w dwóch punktach $\mathbf{x}_{1},\mathbf{x}_{2}$ . Z przypadku (I) wiemy, że każdy z punktów $\mathbf{x}_{1},\mathbf{x}_{2}$ może zostać przedstawiony jako kombinacja wypukła skończonej liczby punktów ekstremalnych $U$ . Punkt ${\bar{\mathbf{x}}}$ może być zapisany jako kombinacja wypukła $\mathbf{x}_{1},\mathbf{x}_{2}$ , a więc należy do otoczki wypukłej punktów ekstremalnych $U$ .

∎

Poniżej prezentujemy inny dowód twierdzenia 4.4 bazujący częściowo na pomysłach wykorzystywanych w dowodzie ogólnej wersji twierdzenia Kreina-Milmana. W przeciwieństwie do powyższego rozumowania, dowód ten nie jest konstruktywny.

Alternatywny dowód twierdzenia 4.4

Jeśli zbiór $U$ zawarty jest w $\mathbb{R}^{1}$ , to teza twierdzenia jest trywialna. Załóżmy więc, że każdy wypukły zwarty podzbiór $\mathbb{R}^{m}$ jest otoczką wypukłą swoich punktów ekstremalnych. Udowodnimy prawdziwość tego stwierdzenia dla $U\subset\mathbb{R}^{{m+1}}$ . Niech $W$ będzie otoczką wypukłą punktów ekstremalnych $U$ . Oczywiście $W\subset U$ . Przypuśćmy, że istnieje ${\bar{\mathbf{x}}}\in U\setminus W$ . Wówczas możemy znaleźć kulę o środku w ${\bar{\mathbf{x}}}$ i dostatecznie małym promieniu, która nie przecina $W$ . Na mocy mocnego twierdzenia o oddzielaniu, tw. 3.2, istnieje wektor $\mathbf{a}\in\mathbb{R}^{{m+1}}$ , taki że $\mathbf{a}^{T}\mathbf{x}\le\alpha$ dla $\mathbf{x}\in W$ i $\mathbf{a}^{T}{\bar{\mathbf{x}}}>\alpha$ . Niech $\beta=\sup _{{\mathbf{x}\in U}}\mathbf{a}^{T}\mathbf{x}$ . Supremum to jest po całym zbiorze $U$ i jest skończone ze zwartości $U$ . Hiperpłaszczyzna $P=\{\mathbf{x}\in\mathbb{R}^{{m+1}}:\ \mathbf{a}^{T}\mathbf{x}=\beta\}$ nie przecina $W$ (bo $\alpha<\mathbf{a}^{T}{\bar{\mathbf{x}}}\le\beta$ ), ale ma punkt wspólny z $U$ . Rzeczywiście, $P_{U}:=P\cap U$ jest niepusty, gdyż ze zwartości $U$ wynika, że supremum definiujące $\beta$ jest osiągane, czyli istnieje $\mathbf{x}\in U$ , dla którego $\mathbf{a}^{T}\mathbf{x}=\beta$ . Pokażemy, że $P_{U}$ zawiera punkt ekstremalny $U$ , co będzie sprzeczne z definicją zbioru $W$ . Zbiór $P_{U}$ jest niepustym, zwartym zbiorem wypukłym w przestrzeni afinicznej o wymiarze $m$ . Zbiór $P_{U}$ możemy traktować jako podzbiór $\mathbb{R}^{m}$ , czyli na mocy założenia indukcyjnego jest on otoczką wypukłą swoich punktów ekstremalnych. Niech ${\bar{\mathbf{y}}}$ będzie jednym z punktów ekstremalnych $P_{U}$ i załóżmy, że jest on kombinacją wypukłą $\mathbf{y}_{1},\mathbf{y}_{2}\in U$ , ${\bar{\mathbf{y}}}=\lambda\mathbf{y}_{1}+(1-\lambda)\mathbf{y}_{2}$ dla $\lambda\in(0,1)$ . Wówczas $\beta=\mathbf{a}^{T}{\bar{\mathbf{y}}}=\lambda\mathbf{a}^{T}\mathbf{y}_{1}+(1-\lambda)\mathbf{a}^{T}\mathbf{y}_{2}$ . Z konstrukcji $\beta$ wynika, że zarówno $\mathbf{a}^{T}\mathbf{y}_{1}$ jak i $\mathbf{a}^{T}\mathbf{y}_{2}$ muszą być równe $\beta$ , czyli $\mathbf{y}_{1},\mathbf{y}_{2}\in P_{U}$ . Z faktu, że ${\bar{\mathbf{y}}}$ jest punktem ekstremalnym $P_{U}$ wnioskujemy, że $\mathbf{y}_{1}=\mathbf{y}_{2}={\bar{\mathbf{y}}}$ , czyli ${\bar{\mathbf{y}}}$ jest punktem ekstremalnym $U$ .

∎

Twierdzenie 4.5

Niech $f:W\to\mathbb{R}$ 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 wypukłości $f$ dostajemy

$f({\bar{\mathbf{x}}})\le a_{1}f(\mathbf{x}_{1})+\ldots+a_{m}f(\mathbf{x}_{m}).$

Z faktu, że ${\bar{\mathbf{x}}}$ jest maksimum $f$ na zbiorze $W$ wynika, że $f(\mathbf{x}_{1})=\ldots=f(\mathbf{x}_{m})=f({\bar{\mathbf{x}}})$ .

∎

Przykład 4.2

Rozważmy następujące zadanie optymalizacyjne:

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

Rys. 4.3. Zbiór punktów dopuszczalnych. Punkty ekstremalne zaznaczone pogrubioną linią.

Funkcja celu jest wypukła, więc na mocy twierdzenia 4.5 punkt ekstremalny jest rozwiązaniem. Zbiór punktów dopuszczalnych jest kołem przeciętym z półprzestrzenią, czyli zbiorem wypukłym. Zbiór punktów ekstremalnych zaznaczony jest pogrubioną linią na rysunku 4.3. Jest to fragment okręgu. Zmaksymalizujmy więc funkcję celu na całym okręgu i zobaczmy, czy rozwiązanie należy do tego fragmentu okręgu. Podstawiając $x_{2}^{2}=1-x_{1}^{2}$ do funkcji celu dostajemy

$x_{1}+1-x_{1}^{2}\to\max.$

Rozwiązaniem tego problemu jest $x_{1}=1/2.$ Stąd $x_{2}=\pm\sqrt{3}/2.$ Para $(1/2,\sqrt{3}/2)$ należy do półokręgu punktów ekstremalnych, więc jest rozwiązaniem, lecz niekoniecznie jedynym. Para $(1/2,-\sqrt{3}/2)$ nie należy do zbioru punktów dopuszczalnych.

Twierdzenie 4.5 jest szczególnie użyteczne przy maksymalizacji funkcji wypukłej na zbiorach wielościennych:

Definicja 4.5

Zbiór $W\subset\mathbb{R}^{n}$ nazwiemy zbiorem wielościennym, jeśli jest przecięciem skończonej rodziny półprzestrzeni, tzn.

$W=\big\{\mathbf{x}\in\mathbb{R}^{n}:p_{i}^{T}x\le\alpha _{i},\ i=1,\ldots,m\big\},$

gdzie $p_{i}\in\mathbb{R}^{n}$ , $p_{i}\ne 0$ i $\alpha _{i}\in\mathbb{R}$ .

Rys. 4.4. Zbiory wielościenne. Ciemnymi kropami zaznaczone są punkty ekstremalne.

Łatwo można zauważyć, że punktami ekstremalnymi ograniczonych zbiorów wielościennych są ,,wierzchołki” (patrz rys. 4.4).

Lemat 4.5

Zbiór wielościenny jest domknięty i wypukły.

Dowód

Zbiór wielościenny jest domknięty i wypukły jako przecięcie rodziny zbiorów domkniętych i wypukłych.

∎

Przykład 4.3

Rozważmy problem optymalizacyjny

$\begin{cases}x_{1}^{2}+x_{2}^{2}\to\max,&\\ x_{1}+3x_{2}\le 12,&\\ 5x_{1}+x_{2}\le 18,&\\ 3x_{1}+2x_{2}\ge 8.&\end{cases}$

Rys. 4.5. Zbiór punktów dopuszczalnych. Punkty ekstremalne zaznaczone dużymi kropkami.

Funkcja celu jest wypukła, zaś zbiór punktów dopuszczalnych jest wielościenny. Jego punkty ekstremalne to $(0,4)^{T}$ , $(3,3)^{T}$ i $(4,-2)^{T}$ , patrz rysunek 4.5. Wartość funkcji celu w tych punktach wynosi odpowiednio: $16$ , $18$ i $20$ . Rozwiązaniem jest zatem punkt $(4,-2)^{T}$ . Można łatwo dowieść, że jest to jedyne rozwiązanie tego problemu.

4.4. Zadania

Ćwiczenie 4.1

Udowodnij, że zbiór rozwiązań globalnych zagadnienia (4.1) jest wypukły dla wypukłego zbioru $W\subset\mathbb{R}^{n}$ i wypukłej funkcji $f:W\to\mathbb{R}$ .

Ćwiczenie 4.2

Rozważmy zagadnienie (4.1) dla wypukłego zbioru $W\subset\mathbb{R}^{n}$ i wypukłej funkcji $f:W\to\mathbb{R}$ . Wykaż, że ścisłe rozwiązanie lokalne jest jedynym rozwiązaniem globalnym.

Ćwiczenie 4.3

Udowodnij: Niech $W\subset\mathbb{R}^{n}$ wypukły oraz $g,h:W\to\mathbb{R}$ różniczkowalne. Jeśli zachodzi jeden z poniższych warunków:

$g$ jest wypukła, $g\ge 0$ , oraz $h$ jest wklęsła, $h>0$ ,
$g$ jest wypukła, $g\le 0$ , oraz $h$ jest wypukła, $h>0$ ,

to $f=g/h$ jest pseudowypukła. Podaj przykład, że $f$ nie jest wypukła.

Ćwiczenie 4.4

Udowodnij: Niech $W\subset\mathbb{R}^{n}$ wypukły oraz $g,h:W\to\mathbb{R}$ różniczkowalne. Jeśli $g$ jest wypukła i $g\le 0$ oraz $h$ jest wklęsła, $h>0$ , to $f=gh$ jest pseudowypukła.

Ćwiczenie 4.5

Udowodnij, że zbiór minimów funkcji pseudowypukłej $f:W\to\mathbb{R}$ , gdzie $W\subset\mathbb{R}^{n}$ wypukły, jest zbiorem wypukłym.

Ćwiczenie 4.6

Odpowiedz na następujące pytania:

Czy suma funkcji pseudowypukłych jest pseudowypukła?
Czy jeśli funkcje $g_{1},g_{2}$ są pseudowypukłe w punkcie $\mathbf{x}$ oraz $Dg_{1}(\mathbf{x})=Dg_{2}(\mathbf{x})=\mathbf{0}^{T}$ , to funkcja $g_{1}+g_{2}$ jest pseudowypukła w $\mathbf{x}$ ?
Czy suma funkcji pseudowypukłej i wypukłej jest pseudowypukła?

Odpowiedzi uzasadnij kontrprzykładami lub dowodami.

Ćwiczenie 4.7

Korzystając z tw. 4.2 rozwiąż zadanie

$\begin{cases}2x+3y\to\min,&\\ x^{2}+2y^{2}\le 1.\end{cases}$

Ćwiczenie 4.8

Znaleźć rozwiązania zadania

$\begin{cases}\log(x_{1}+4)+x_{2}\to\max,&\\ x_{2}\ge 2|x_{1}|,&\\ x_{2}\le 4.&\end{cases}$

Wskazówka:

Skorzystaj z tw. 4.2.

Ćwiczenie 4.9

Rozwiąż zadanie

$\begin{cases}\frac{e^{{(x_{1}-3)^{2}+x_{2}}}}{\log(x_{2})}\to\min,&\\ x_{2}>1,&\\ x_{1}\in[1,100].&\end{cases}$

Ćwiczenie 4.10

Udowodnij, że ${\bar{\mathbf{x}}}\in W$ jest punktem ekstremalnym zbioru wypukłego $W\subset\mathbb{R}^{n}$ wtw, gdy $W\setminus{\bar{\mathbf{x}}}$ jest zbiorem wypukłym.

Ćwiczenie 4.11

Wykaż, że jeśli w punkcie brzegowym ${\bar{\mathbf{x}}}$ zbioru wypukłego $U$ istnieje hiperpłaszczyzna podpierająca $H$ , taka że $H\cap U=\{{\bar{\mathbf{x}}}\}$ , to punkt ${\bar{\mathbf{x}}}$ jest punktem ekstremalnym $U$ .

Ćwiczenie 4.12

Zbadaj związek pomiędzy subróżniczką funkcji wypukłej w punkcie ${\bar{\mathbf{x}}}$ a hiperpłaszczyznami podpierającymi epigraf tej funkcji w tym punkcie.

Ćwiczenie 4.13

Znaleźć rozwiązanie zadania

$\begin{cases}\log\Big(\frac{1}{x_{1}+4}\Big)+x_{2}\to\max,&\\ x_{2}\ge 2|x_{1}|,&\\ x_{2}\le 4.&\end{cases}$

Ćwiczenie 4.14

Rozwiąż problem programowania nieliniowego z ograniczeniami:

$\begin{cases}\log _{2}(x_{1}+x_{2})-2|x_{2}-2x_{1}|-x_{2}^{2}+2x_{2}\to\min,&\\ x_{1}\ge 0,\qquad x_{2}\ge 0,\qquad x_{1}+x_{2}\ge 1,&\\ |x_{1}-x_{2}|+|x_{1}|\le 4.&\end{cases}$

Ćwiczenie 4.15

([3, Zadania 3.28, 3.29]) Zdefiniujmy $f:[0,\infty)^{n}\to\mathbb{R}$ najstępująco:

$f(\mathbf{x})=\min\big\{{\mathbf{c}}^{T}\mathbf{y}+\mathbf{x}^{T}(A\mathbf{y}-\mathbf{b}):\ \mathbf{y}\in W\big\},$

gdzie $W$ jest zbiorem wielościennym, $\mathbf{b},\mathbf{c}\in\mathbb{R}^{n}$ , $A\in\mathbb{R}^{{n\times n}}$ .

Wykaż, że $f$ jest wklęsła.
Scharakteryzuj subróżniczkę $f$ .
Znajdź subróżniczkę w punktach $\mathbf{x}\ge\mathbf{0}$ dla

$A=\begin{pmatrix}3&2\\ -1&2\end{pmatrix},\qquad\mathbf{b}=\begin{pmatrix}6\\ 4\end{pmatrix},\qquad\mathbf{c}=\begin{pmatrix}-1\\ -2\end{pmatrix}.$

Ćwiczenie 4.16

Korzystając z tw. 4.3 rozwiąż następujący problem optymalizacyjny:

$\begin{cases}x^{2}-6x+y^{2}+2y\to\min,&\\ x+2y-10=0,&\\ 25-x^{2}-y^{2}\ge 0.&\end{cases}$

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

Optymalizacja II

Zagadnienia

4. Ekstrema funkcji wypukłej z ograniczeniami

4.1. Problem minimalizacyjny

Twierdzenie 4.1

Dowód twierdzenia 4.1

Twierdzenie 4.2

Uwaga 4.1

Uwaga 4.2

Dowód tw. 4.2

Wniosek 4.1

Przykład 4.1

Twierdzenie 4.3

Wniosek 4.2

Dowód twierdzenia 4.3

4.2. Funkcje pseudowypukłe

Definicja 4.1

Uwaga 4.3

Lemat 4.1

Dowód

Lemat 4.2

Dowód

Lemat 4.3

4.3. Maksymalizacja funkcji wypukłej

Definicja 4.2

Definicja 4.3

Twierdzenie 4.4

Definicja 4.4

Wniosek 4.3

Lemat 4.4

Dowód

Dowód twierdzenia 4.4

Alternatywny dowód twierdzenia 4.4

Twierdzenie 4.5

Dowód

Przykład 4.2

Definicja 4.5

Lemat 4.5

Dowód

Przykład 4.3

4.4. Zadania

Ćwiczenie 4.1

Ćwiczenie 4.2

Ćwiczenie 4.3

Ćwiczenie 4.4

Ćwiczenie 4.5

Ćwiczenie 4.6

Ćwiczenie 4.7

Ćwiczenie 4.8

Ćwiczenie 4.9

Ćwiczenie 4.10

Ćwiczenie 4.11

Ćwiczenie 4.12

Ćwiczenie 4.13

Ćwiczenie 4.14

Ćwiczenie 4.15

Ćwiczenie 4.16