Criterium voor een globale extreem

Optimalisatie: Extreme punten

Criterium voor een globale extreem

Tot nu toe hebben we ons alleen beziggehouden met de lokale extrema van multivariate functies. Aangezien globale maxima van functies op $\mathbb{R}^2$ lokale maxima zijn, en hetzelfde geldt voor minima, is de lokale informatie relevant voor globale optimalisatie. Voor speciale functies, in het bijzonder voor convexe of concave functies, kunnen we zelfs globale conclusies trekken.

Omdat globale extremen van functies afhankelijk zijn van het domein waarop deze functies worden gedefinieerd, moeten we ook het domein van de functie in beeld te brengen. Voor de definitie van convexiteit van een functie op een domein moeten we eisen dat het domein zelf ook convex is in de volgende zin:

Laat $S$ een domein in de $x,y$ -vlak zijn. Dan noemen we $S$ convex als elk lijnstuk tussen twee punten van $S$ geheel binnen $S$ ligt.

Laat $f$ een functie zijn die gedefinieerd is op een convex domein $S$ . Dan heet $f$ convex als het lijnstuk tussen elk tweetal punten van de grafiek van $f$ geen enkel punt onder de grafiek heeft. Met andere woorden, als voor alle $u$ , $v$ in $S$ en $0\le t\le 1$ geldt $f(t \cdot u+(1-t)\cdot v) \le t\cdot f(u)+ (1-t)\cdot f(v)$

Als $-f$ convex is op $S$ dan heet $f$ concaaf op $S$ .

Voorbeelden

Voorbeelden van convexe domeinen zijn

het gehele vlak $\Bbb R^2$
open kwadranten, zoals de verzameling van alle $\rv{x,y}$ met $x\gt0$ en $y\gt 0$
gesloten kwadranten, zoals de verzameling van alle $\rv{x,y}$ met $x\ge0$ en $y\ge 0$
open cirkelschijven, zoals de verzameling van alle $\rv{x,y}$ met $x^2+y^2\lt 1$
gesloten cirkelschijven, zoals de verzameling van alle $\rv{x,y}$ met $x^2+y^2\le 1$
het bovengrafiek van een convexe univariate functie $f$ (zoals $f(x)=x^2$ of $f(x)=2^x$ ), dat wil zeggen de verzameling van alle $\rv{x,y}$ met $y\ge f(x)$
een lijn of een lijnsegment

In de theorie over Concaviteit en convexiteit staat een definitie van convexiteit van een functie op het hele vlak $\mathbb{R}^2$ . De huidige definitie komt overeen met deze definitie in dat speciale geval.

We zijn nu klaar om een voldoende voorwaarde te formuleren waaronder een lokaal extremum een globaal extremum is.

Van lokaal tot globaal extremum

Laat $S$ een convex domein zijn.

Als $f$ een convexe functie op $S$ is, dan is elk lokaal minimum van $f$ een globaal minimum van $f$ op $S$ .
Als $f$ een concave functie $S$ is, dan is elke lokaal maximum van $f$ een globaal maximum van $f$ op $S$ .

De tweede uitspraak volgt uit de eerste door over te gaan op de functie $-f$ . Daarom richten we ons op het bewijs van de eerste uitspraak.

Laat $u$ zijn een lokaal minimum van $f$ op $S$ zijn. Dan is er, per definitie, een getal $\epsilon\gt0$ zodanig dat voor alle $v\in S$ met $||u-v||\le \epsilon$ geldt $f(v)\ge f(u)$ .

Stel dat er een $v$ in $S$ is zodat $f(v)\lt f(u)$ . Voor $0\lt t\le 1$ geldt dan

$f((1-t) v+t u) \le (1-t)f(v)+ t f(u) \lt (1-t)f(u)+t f(u)=f(u)$

Kies $t=\min\left(1,\frac{\epsilon}{||u-v||}\right)$ , zodat $||\left((1-t)u+t v\right)-u|| \lt \epsilon$ Dan geldt vanwege het bovenstaande dat $f((1-t)u+t v)\lt f(u)$ , maar vanwege de definitie van lokale minimaliteit en de keuze van $\epsilon$ geldt $f((1-t)u+t v)\ge f(u)$ , een tegenspraak.

We concluderen dat voor elke $v$ in $S$ geldt $f(v)\ge f(u)$ . Dit betekent dat $u$ een globaal minimum van $f$ op $S$ is.

In het geval van een differentieerbare convexe functie op een complex domein, kunnen we zelfs concluderen dat een stationair punt een globaal extreem is.

Veronderstel dat $S$ een convex domein is en $f$ een differentieerbare functie op $S$ met continue partiële afgeleiden.

Als $f$ convex is, dan is elk stationair punt van $f$ in $S$ een globaal minimum.
Als $f$ concaaf is, dan is elk stationair punt van $f$ in $S$ een globaal maximum.

De tweede uitspraak is een onmiddellijk gevolg van de eerste, aangezien $-f$ dan en slechts dan convex is als $f$ concaaf is. Daarom richten we ons op het bewijs van de eerste uitspraak.

Laat $u=\rv{u_1,u_2}$ en $v=\rv{v_1,v_2}$ willekeurige punten van $S$ zijn en laat $t\in\ivoc{0}{1}$ . Uit de convexiteit van $f$ leiden we het volgende af: $\begin{array}{rcl}f(t\cdot u+(1-t)\cdot v) &\le& t\cdot f(u)+ (1-t)\cdot f(v) \\ &&\phantom{xx}\color{blue}{\text{convexiteit van }f}\\ t\cdot\left( f(u)-f(v)\right) &\ge& f(v+t\cdot (u-v))-f(v) \\ &&\phantom{xx}\color{blue}{\text{termen herschikt}}\\ f(u)-f(v)&\ge&\dfrac{f(v+t\cdot (u-v))-f(v)}{t} \\ &&\phantom{xx}\color{blue}{\text{beide zijden gedeeld door }t}\\ f(u)-f(v)&\ge&\left.\dfrac{\dd}{\dd t}\left(f(v+t\cdot (u-v))-f(v)\right) \right|_{t=0}\\ &&\phantom{xx}\color{blue}{\text{limiet genomen voor }t\downarrow 0}\\ f(u)-f(v)&\ge&f_x(v)\cdot (u_1-v_1) + f_y(v)\cdot(u_2-v_2)\\ &&\phantom{xx}\color{blue}{\text{kettingregel voor partiële differentiatie}}\\\end{array}$

Als $v$ een stationair punt van $f$ in $S$ is, dan geldt $f_x(v) = f_y(v) = 0$ , zodat de rechterzijde van bovenstaande ongelijkheid gelijk is aan $0$ . De ongelijkheid geeft dan $f(u)\ge f(v)$ alle $u$ in $S$ . Dit betekent dat $v$ een globaal minimum is.