Analiza wypukła i optymalizacja

Streszczenie

Zbiory wypukłe i operacje, które wypukłość zachowują, funkcje wypukłe i wklęsłe wraz z charakteryzacją przez epigraf, kryteria pierwszego i drugiego rzędu, nierówność Jensena, quasi-wypukłość, a przede wszystkim twierdzenia czyniące optymalizację łatwą: minimum lokalne funkcji wypukłej jest globalne, a punkt stacjonarny jest minimum globalnym. Z zastosowaniami w programowaniu liniowym i metodzie najmniejszych kwadratów. Każde twierdzenie z dowodem i rysunkiem.

Wypukłość to najważniejsza struktura w optymalizacji. Dla funkcji wypukłej znika różnica między tym, co lokalne, a tym, co globalne: każde minimum lokalne jest globalne, a zwykłe zerowanie pochodnej wystarcza, by mieć pewność optimum. To dlatego metoda najmniejszych kwadratów ma jedno, jednoznaczne rozwiązanie, a estymacja największej wiarygodności w modelach wykładniczych jest „dobrze postawiona”. Ten rozdział buduje analizę wypukłą od zbiorów i funkcji, przez kryteria różniczkowe i nierówność Jensena, aż po twierdzenia, które czynią optymalizację wypukłą tak dogodną.

Zbiory wypukłe

Definicja

Zbiór wypukły

Zbiór $C\subseteq\mathbb{R}^n$ jest wypukły, gdy wraz z każdymi dwoma punktami zawiera łączący je odcinek:

$$ \forall_{x,y\in C}\;\forall_{t\in[0,1]}\;\; tx+(1-t)y\in C. $$

Punkt $tx+(1-t)y$ to kombinacja wypukła $x$ i $y$.

Zbiór wypukły i niewypukły z odcinkiem między punktami — Zbiór wypukły (po lewej) zawiera każdy odcinek między swoimi punktami; zbiór niewypukły (po prawej) — nie: odcinek „wychodzi na zewnątrz”. To geometryczne sedno całego rozdziału.

Twierdzenie

Przekrój zbiorów wypukłych jest wypukły

Jeśli $C_1,C_2$ są wypukłe, to $C_1\cap C_2$ jest wypukły. (Ogólniej — przekrój dowolnej rodziny zbiorów wypukłych jest wypukły; stąd wypukłe są zbiory rozwiązań układów nierówności liniowych.)

Przekrój dwóch zbiorów wypukłych jako zbiór wypukły — Przekrój dwóch zbiorów wypukłych pozostaje wypukły: jeśli odcinek mieści się w każdym z osobna, to mieści się i w części wspólnej. To dlatego zbiór dopuszczalny zadania z wieloma ograniczeniami liniowymi jest wypukły.

Funkcje wypukłe

Definicja

Funkcja wypukła i wklęsła

Funkcja $f$ jest wypukła, gdy dla wszystkich $x,y$ i $t\in[0,1]$

$$ f\big(tx+(1-t)y\big)\le t f(x)+(1-t)f(y), $$

czyli wykres leży pod każdą cięciwą. Funkcja jest wklęsła, gdy zachodzi nierówność odwrotna (wykres nad cięciwą) — równoważnie, gdy $-f$ jest wypukła.

Funkcja wypukła pod cięciwą — Funkcja wypukła: wartość w punkcie pośrednim nie przekracza odpowiedniej wartości na cięciwie. „Wgięcie ku górze” — to samo, co $f''\ge 0$ z rozdziału 6, lecz tu bez zakładania różniczkowalności.

Funkcja wklęsła nad cięciwą — Funkcja wklęsła leży **nad** cięciwą — typowa dla funkcji użyteczności i produkcji (malejące przychody krańcowe). Wklęsłość $f$ to wypukłość $-f$, więc cała teoria przenosi się przez zmianę znaku.

Twierdzenie

Charakteryzacja przez epigraf

Funkcja $f$ jest wypukła wtedy i tylko wtedy, gdy jej epigraf

$$ \operatorname{epi} f=\{(x,y) : y\ge f(x)\} $$

jest zbiorem wypukłym. To most łączący wypukłość funkcji z wypukłością zbiorów.

Epigraf funkcji wypukłej jako zbiór wypukły — Epigraf to obszar **nad** wykresem. Funkcja jest wypukła dokładnie wtedy, gdy ten obszar jest zbiorem wypukłym — cięciwa między dwoma punktami epigrafu cała leży w epigrafie. Dwa pojęcia wypukłości stają się jednym.

Kryteria różniczkowe

Twierdzenie

Kryterium pierwszego rzędu

Funkcja różniczkowalna $f$ jest wypukła wtedy i tylko wtedy, gdy jej wykres leży nad każdą styczną:

$$ f(y)\ge f(x)+f'(x)(y-x)\qquad\text{dla wszystkich }x,y. $$

(W wielu wymiarach: $f(y)\ge f(x)+\nabla f(x)\cdot(y-x)$.)

Dowód

Wypukłość ⇒ wykres nad styczną

Z definicji wypukłości. Dla $t\in(0,1]$ punkt $x+t(y-x)$ jest kombinacją wypukłą $x$ i $y$, więc $$f\big(x+t(y-x)\big)\le (1-t)f(x)+t f(y).$$
Przekształcenie. Odejmujemy $f(x)$ i dzielimy przez $t\gt 0$: $$\frac{f\big(x+t(y-x)\big)-f(x)}{t}\le f(y)-f(x).$$
Granica $t\to 0^+$. Lewa strona to iloraz różnicowy w kierunku $y-x$ i dąży do $f'(x)(y-x)$. Stąd $$f'(x)(y-x)\le f(y)-f(x),$$ czyli $f(y)\ge f(x)+f'(x)(y-x)$. Implikację odwrotną dowodzi się, stosując nierówność stycznej w dwóch punktach kombinacji wypukłej. $\;$

∎

Styczna jako minoranta funkcji wypukłej — Kryterium pierwszego rzędu: styczna do funkcji wypukłej jest jej **globalnym minorantem** — cały wykres leży nad nią. To właśnie dzięki tej własności znikanie pochodnej będzie gwarantować minimum globalne.

Twierdzenie

Kryterium drugiego rzędu

Funkcja dwukrotnie różniczkowalna jest wypukła wtedy i tylko wtedy, gdy $f''(x)\ge 0$ wszędzie (w wielu wymiarach: hesjan $H(x)$ jest dodatnio półokreślony). Ściśle dodatnia druga pochodna daje wypukłość ścisłą.

Dodatnia druga pochodna jako warunek wypukłości — Kryterium drugiego rzędu: $f''\ge 0$ oznacza, że nachylenie $f'$ rośnie — krzywa „odgina się” ku górze. Tam, gdzie $f''$ jest dodatnia, funkcja jest wypukła; ujemna — wklęsła; zero przy zmianie znaku to punkt przegięcia.

Twierdzenie

Nierówność Jensena

Dla funkcji wypukłej $f$, wag $\lambda_i\ge 0$ z $\sum_i\lambda_i=1$ oraz punktów $x_i$:

$$ f\Big(\sum_i \lambda_i x_i\Big)\le \sum_i \lambda_i f(x_i). $$

W języku probabilistycznym: $f\big(\mathbb{E}[X]\big)\le\mathbb{E}\big[f(X)\big]$ — fundament wielu nierówności w statystyce.

Dowód

Nierówność Jensena (indukcja po liczbie punktów)

Baza. Dla $n=2$ nierówność jest wprost definicją wypukłości.
Krok indukcyjny. Załóżmy tezę dla $n-1$ punktów. Dla $n$ punktów i $\lambda_n\lt 1$ piszemy $\sum_{i=1}^n\lambda_i x_i=(1-\lambda_n)\,s+\lambda_n x_n$, gdzie $s=\sum_{i=1}^{n-1}\tfrac{\lambda_i}{1-\lambda_n}x_i$ jest kombinacją wypukłą $n-1$ punktów.
Najpierw wypukłość dla dwóch. $$f\Big(\sum_i\lambda_i x_i\Big)\le (1-\lambda_n)f(s)+\lambda_n f(x_n).$$
Potem hipoteza indukcyjna do $f(s)$. Stosujemy ją do $s$ z wagami $\tfrac{\lambda_i}{1-\lambda_n}$ (sumują się do $1$) i otrzymujemy $f(s)\le\sum_{i=1}^{n-1}\tfrac{\lambda_i}{1-\lambda_n}f(x_i)$. Po podstawieniu człony $(1-\lambda_n)$ się skracają i zostaje $f(\sum\lambda_i x_i)\le\sum\lambda_i f(x_i)$. $\;$

∎

Nierówność Jensena: funkcja średniej poniżej średniej wartości — Nierówność Jensena dla dwóch punktów: wartość funkcji wypukłej w średniej argumentów ($f$ punktu na osi) leży **poniżej** średniej wartości (punktu na cięciwie). Luka między nimi to „defekt wypukłości”.

Quasi-wypukłość

Definicja

Funkcja quasi-wypukła

Funkcja jest quasi-wypukła, gdy wszystkie jej zbiory poziomicowe $\{x : f(x)\le\alpha\}$ są wypukłe — równoważnie

$$ f\big(tx+(1-t)y\big)\le\max\big(f(x),f(y)\big). $$

Każda funkcja wypukła jest quasi-wypukła, ale nie odwrotnie. To słabsze pojęcie wystarcza w wielu zadaniach mikroekonomii (quasi-wklęsłe funkcje użyteczności).

Funkcja quasi-wypukła z wypukłymi zbiorami poziomicowymi — Funkcja quasi-wypukła, która **nie** jest wypukła: jej wykres bywa „wygięty”, ale każdy zbiór poziomicowy $\{f\le\alpha\}$ pozostaje przedziałem (zbiorem wypukłym). Quasi-wypukłość kontroluje poziomice, nie samą krzywiznę.

Optymalizacja funkcji wypukłych

Wypukłość sprowadza trudne pytania globalne do łatwych pytań lokalnych.

Twierdzenie

Minimum lokalne jest globalne

Dla funkcji wypukłej każde minimum lokalne jest minimum globalnym. Jeśli funkcja jest ściśle wypukła, minimum jest co najwyżej jedno.

Dowód

Lokalne ⇒ globalne (nie wprost)

Założenie przeciwne. Niech $x^*$ będzie minimum lokalnym, lecz nie globalnym: istnieje $z$ z $f(z)\lt f(x^*)$.
Idziemy po odcinku. Dla $t\in(0,1)$ z wypukłości $$f\big(tz+(1-t)x^*\big)\le t f(z)+(1-t)f(x^*)\lt f(x^*),$$ bo $f(z)\lt f(x^*)$.
Sprzeczność. Punkty $tz+(1-t)x^*$ dla małych $t$ leżą **dowolnie blisko** $x^*$, a mają wartość mniejszą niż $f(x^*)$. To przeczy temu, że $x^*$ jest minimum lokalnym.
Jedyność przy ścisłej wypukłości. Gdyby były dwa różne minima globalne $a,b$, to środek odcinka miałby wartość ostro mniejszą — sprzeczność. $\;$

∎

Funkcja wypukła z jednym minimum kontra niewypukła z wieloma — Dla funkcji wypukłej nie ma „pułapek” lokalnych minimów: dolina jest jedna, więc minimum lokalne pokrywa się z globalnym. To kontrast z funkcją niewypukłą, gdzie algorytm może utknąć w gorszym minimum lokalnym.

Twierdzenie

Punkt stacjonarny jest minimum globalnym

Dla różniczkowalnej funkcji wypukłej warunek $\nabla f(x^*)=\mathbf{0}$ (lub $f'(x^*)=0$) jest nie tylko konieczny, ale i dostateczny dla globalnego minimum.

Dowód

Stacjonarność ⇒ globalne minimum

Z kryterium pierwszego rzędu. Dla każdego $y$ wypukłość daje $$f(y)\ge f(x^*)+\nabla f(x^*)\cdot(y-x^*).$$
Wstawiamy stacjonarność. Skoro $\nabla f(x^*)=\mathbf{0}$, drugi składnik znika i zostaje $f(y)\ge f(x^*)$ dla **każdego** $y$.
Wniosek. Zatem $x^*$ jest minimum globalnym. To dlatego w zadaniach wypukłych wystarczy rozwiązać równanie $\nabla f=0$ — nie trzeba sprawdzać warunków drugiego rzędu ani porównywać minimów. $\;$

∎

Punkt stacjonarny funkcji wypukłej jako minimum globalne — W funkcji wypukłej zerowanie pochodnej natychmiast lokalizuje minimum globalne: jedyny punkt o poziomej stycznej jest dnem doliny. Warunek konieczny staje się dostateczny — sedno „łatwości” optymalizacji wypukłej.

Przykład

Programowanie liniowe: optimum w wierzchołku

Gdy minimalizujemy funkcję liniową na wielościanie (przekroju półprzestrzeni — zbiorze wypukłym), optimum jest osiągane w wierzchołku. Na tym opiera się metoda sympleks: zamiast przeszukiwać całe continuum, wystarczy obejść skończony zbiór wierzchołków.

Optimum programowania liniowego w wierzchołku wielokąta dopuszczalnego — Programowanie liniowe: zbiór dopuszczalny to wypukły wielokąt, a poziomice celu to równoległe proste. Przesuwając je w kierunku optymalizacji, „ostatni” dotknięty punkt to **wierzchołek** — stąd optimum zawsze w narożniku.

Przykład

Metoda najmniejszych kwadratów jako zadanie wypukłe

Suma kwadratów reszt $\mathrm{RSS}(\beta)=\sum_i (y_i-x_i^{\!\top}\beta)^2$ jest funkcją wypukłą (kwadratową o dodatnio półokreślonym hesjanie $2X^{\!\top}X$). Dlatego warunek pierwszego rzędu — równania normalne $X^{\!\top}X\beta=X^{\!\top}y$ — daje od razu globalny estymator MNK, bez ryzyka utknięcia w minimum lokalnym.

Wypukła funkcja straty MNK z jednym minimum globalnym — Funkcja straty MNK $\mathrm{RSS}(\beta)$ jest wypukłą parabolą: ma jedno, globalne minimum w estymatorze $\hat\beta$. Wypukłość gwarantuje, że równania normalne wskazują najlepsze dopasowanie — to matematyczny fundament regresji liniowej.

Podsumowanie

Wypukłość okazała się strukturą, która upraszcza optymalizację do granic możliwości. Zaczęliśmy od zbiorów wypukłych (zamkniętych na odcinki i na przekroje), przeszliśmy do funkcji wypukłych — scharakteryzowanych równoważnie przez cięciwę, epigraf, położenie nad styczną ($f'$ rosnące) oraz znak drugiej pochodnej — i wyprowadziliśmy nierówność Jensena, filar nierówności statystycznych. Quasi-wypukłość pokazała, że dla samej optymalizacji liczą się wypukłe poziomice. Kulminacją są dwa twierdzenia: dla funkcji wypukłej minimum lokalne jest globalne, a punkt stacjonarny jest minimum globalnym — dzięki czemu programowanie liniowe rozwiązujemy po wierzchołkach, a estymator MNK wyznaczamy z równań normalnych z pewnością globalności. W następnym rozdziale przejdziemy od różniczkowania do jego odwrotności — całki Riemanna.