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 – 4. Ekstrema funkcji wypukłej z ograniczeniami – MIM UW

Zagadnienia

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

\

  1. Zbiór wypukły o wymiarze m<n możemy traktować jako podzbiór przestrzeni \mathbb{R}^{m}.

  2. 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}
Wykres zbioru punktów dopuszczalnych
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}.

Przykład dwóch zbiorów wielościennych
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}
Wykres zbioru punktów dopuszczalnych
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:

  1. Czy suma funkcji pseudowypukłych jest pseudowypukła?

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

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

  1. Wykaż, że f jest wklęsła.

  2. Scharakteryzuj subróżniczkę f.

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

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.