Konveks funksjon

I matematikk er en reell funksjon konveks på et intervall (a,b) hvis akkorden som forbinder to punkter på grafen til funksjonen ligger over funksjonen.

Definisjon

En reell funksjon f definert på et intervall (eller på en hvilken som helst konveks delmengde av et vektorrom ) kalles en konveks funksjon hvis den er definert på en konveks mengde C og for to punkter x , y medlemmer av C , og for hver t i [0 ,1], det gjelder at:

$f(tx+(1-t)y)\leq tf(x)+(1-t)f(y).$

Med andre ord er en funksjon konveks hvis og bare hvis epigrafen ( settet med punkter som ligger i eller på grafen ) er et konveks sett .

En strengt konveks funksjon er en der

$f(tx+(1-t)y)<tf(x)+(1-t)f(y)\,$

for enhver t i (0,1) og $x\neq y.$

En funksjon er konkav hvis funksjonen er konveks. $F$ $-f$

Egenskaper

En konveks funksjon f definert på et åpent intervall C er kontinuerlig på C og differensierbar på alle punkter bortsett fra et tellbart sett . Hvis C er lukket, kan f ikke være kontinuerlig ved kritiske eller endepunkter av C.

En funksjon er midtpunkt konveks ( midtpunkt konveks ) på et intervall "C" if

f\left({\frac {x+y}{2}}\right)\leq {\frac {f(x)+f(y)}{2}}

for alle x og y i C. Denne tilstanden er bare litt mer avslappet enn konveksitetstilstanden. Spesielt vil en kontinuerlig funksjon som er midtpunktkonveks også være konveks.

En differensierbar funksjon av en variabel er konveks på et intervall hvis og bare hvis dens deriverte er monotont ikke-avtagende på det intervallet.

En kontinuerlig differensierbar funksjon av en variabel er konveks på et intervall hvis og bare hvis funksjonen ligger over alle tangentene : f ( y ) ≥ f ( x ) + f '( x ) ( y − x ) for alle x og y på intervallet. Spesielt hvis f '( c ) = 0 , så er c et absolutt minimum av f ( x ).

En dobbelt differensierbar funksjon av en variabel er konveks på et intervall hvis og bare hvis den andre deriverte er ikke-negativ på det intervallet; dette gir en praktisk test for konveksitet. Hvis den andre deriverte er positiv, så er den strengt tatt konveks, men dobbeltimplikasjonen holder ikke, som vi for eksempel kan se i f ( x ) = x 4 .

Generelt er en kontinuerlig dobbelt differensierbar funksjon av mange variabler konveks på et konveks sett hvis og bare hvis dens hessiske matrise er positiv bestemt i det indre av det konvekse settet.

Ethvert lokalt minimum av en konveks funksjon er også et absolutt minimum . En strengt konveks funksjon vil ha maksimalt ett absolutt minimum.

For en konveks funksjon f , setter nivået { x | f ( x ) < a } og { x | f ( x ) ≤ a } med a ∈ R er konvekse mengder. Imidlertid kan det hende at en funksjon hvis nivåsett er konvekse sett ikke viser seg å være konveks; en slik funksjon kalles en kvasi-konveks funksjon .

Jensens ulikhet gjelder enhver konveks funksjon f . Hvis er en tilfeldig variabel som tar verdier i domenet til f , så (Her betegner den matematiske forventningen .) $X$ $Ef(X)\geq f(EX).$ $OG$

Konveks funksjonskalkyle

Hvis og er konvekse funksjoner, så er y det også $F$ $g$ $m(x)=\max\{f(x),g(x)\}$ $h(x)=f(x)+g(x).$
Hvis og er konvekse funksjoner og øker, så er den konveks. $F$ $g$ $g$ $h(x)=g(f(x))$
Konveksitet er invariant under affine kartlegginger; det vil si hvis er konveks, med , så er det , hvor $f(x)$ $x\in \mathbb {R} n}$ $g(y)=f(Ay+b)$ $A\in \mathbb {R}<n\times m},\;b\in \mathbb {R}<m}.$
Hvis er konveks inn og er et ikke-tomt konveks sett, så er det konveks inn når for noen $f(x,y)$ $(x,y)$ $C$ $g(x)=\inf y\in C}f(x,y)$ $x,$ $g(x)>-\infty$ $x.$

Eksempler

Funksjonen har på alle punkter, så f er en (strengt) konveks funksjon. $f(x)=x^{2}$ $f''(x)=2>0$
Absoluttverdifunksjonen er konveks, selv om den ikke er differensierbar ved punktet x = 0. $f(x)=|x|$
Funksjonen for 1 ≤ p er konveks. $f(x)=|x|^{p}$
Funksjonen f med domene [0,1] definert av f (0)= f (1)=1, f ( x )=0 for 0< x <1 er konveks; er kontinuerlig på det åpne intervallet (0,1), men ikke på 0 eller 1.
Funksjonen x 3 har andrederiverte 6 x ; da er hun konveks på settet hvor x ≥ 0 og konkav på settet hvor x ≤ 0.
Hver lineær transformasjon med domene i er konveks, men ikke strengt tatt konveks, siden hvis f er lineær, så gjelder dette også hvis vi erstatter "konveks" med "konkav". $\mathbb{R}$ $f(a+b)=f(a)+f(b).$
Hver affin funksjon med domene i , det vil si hver funksjon av formen , er både konveks og konkav. $\mathbb{R}$ $f(x)=a^{T}x+b$
Hver vektornorm er en konveks funksjon, ved trekantens ulikhet .
Hvis den er konveks, er perspektivfunksjonen konveks for $F$ $g(x,t)=tf(x/t)$ $t>0.$
Funksjonene og er monotont økende , men ikke konvekse. $f(x)={\sqrt {x}}$ $g(x)=\log(x).$
Funksjonene og er konvekse, men ikke monotont økende . $h(x)=x^{2}$ $k(x)=-x$
Funksjonen f ( x ) = 1/ x 2 , med f (0)=+∞, er konveks på intervallene (0,+∞) og (-∞,0), men den er ikke konveks på (-∞, + ∞), på grunn av punktet x = 0.

Teoremer om konvekse funksjoner

Følgende teorem generaliserer et velkjent resultat til ethvert normert rom med uendelig eller endelig dimensjon: $\scriptstyle \mathbb {R}$

(Nødvendig lokal minimumsbetingelse) La være en funksjon definert på et konveks sett av et normert vektorrom. Hvis punktet er et lokalt minimum av funksjonen og hvis funksjonen er differensierbar (i Fréchet-forstand) i nærheten av det punktet, så $J:U\to \mathbb {R}$ $ELLER\,$ $u\in U$ $J:U\to \mathbb {R}$

$\mathrm {D} J(u)(vu)\geq 0,\qquad \forall :v\in U$

Den ovennevnte ulikheten kalles Eulers ulikhet .

Den forrige teoremet er gyldig for enhver funksjon, enten den er konveks eller ikke, mens følgende kun er gyldig for konvekse funksjoner:

(Konveksitet og derivert) La være en funksjon definert på et konveks sett av et normert rom, da: $J:U\to \mathbb {R}$ $ELLER\,$

a) Funksjonen er konveks i sitt domene hvis og bare hvis:

J\,

J(v)\geq J(u)+\mathrm {D} J(u)(vu),\qquad \forall :u,v\in U

b) Funksjonen er strengt konveks i sitt domene hvis og bare hvis:

J\,

J(v)>J(u)+\mathrm {D} J(u)(vu),\qquad \forall :u,v\in U,u\neq v

Den geometriske betydningen av teoremet ovenfor er tydelig, teoremet innebærer ganske enkelt at funksjonen i hvert punkt er over tangentplanet i et punkt. Følgende teorem er gyldig for konvekse funksjoner som er to ganger differensierbare (og dermed innrømmer en bilineær form som generaliserer den hessiske matrisen ):

(Konveksitet og andrederiverte) La være en funksjon definert på et konveks sett av et normert rom og være to ganger differensierbar, da: $J:U\to \mathbb {R}$ $ELLER\,$

a) Funksjonen er konveks i sitt domene hvis og bare hvis:

J\,

\mathrm {D} 2}J(u)(vu,vu)\geq 0,\qquad \forall :u,v\in U

b) Ja

\mathrm {D} 2}J(u)(vu,vu)>0,\qquad \forall :u,v\in U,u\neq v

Funksjonen er strengt konveks i sitt domene.

Legg merke til at i dette siste tilfellet er det motsatte av utsagn b) ikke sant generelt, for eksempel vurder hvis andrederiverte ved opprinnelsen forsvinner, men funksjonen forblir strengt konveks. $U=\mathbb {R} ,\ J(u)=u^{4}$

Det siste teoremet pålegger begrensninger på antall minima som en konveks funksjon kan ha og dens natur:

(minima av konvekse funksjoner) La være en funksjon definert på et konveks sett av et normert rom, da: $J:U\to \mathbb {R}$ $ELLER\,$

a) Ethvert lokalt minimum av funksjonen er faktisk et absolutt minimum (selv om ikke hvert absolutt minimum er et lokalt minimum).

J\,

b) Hvis den er strengt konveks, har den høyst et enkelt minimum, og det er et strengt minimum.

J\,

c) Hvis er et åpent sett, så er et punkt et minimum hvis og bare hvis

ELLER\,

u\in U

\mathrm {D} J(u)=0

Se også

Referanser

Rockafellar, R.T. (1970). Konveksanalyse . Princeton: Princeton University Press .
Luenberger, David (1984). Lineær og ikke-lineær programmering . Addison-Wesley.
Luenberger, David (1969). Optimalisering ved hjelp av vektorrommetoder . Wiley og sønner.
Bertsekas, Dimitri (2003). Konveksanalyse og optimalisering . Athena Scientific.
Thomson, Brian (1994). Symmetriske egenskaper for reelle funksjoner . CRC Trykk.
Hiriart-Urruty, Jean-Baptiste og Lemaréchal, Claude. (2004). Grunnleggende om konveks analyse. Berlin: Springer.
Mark Krasnosel'skii, Rutickii Ya.B. (1961). Konvekse funksjoner og Orlicz-rom . Groningen: P. Noordhoff Ltd.
Borwein, Jonathan og Lewis, Adrian. (2000). Konveks analyse og ikke-lineær optimalisering. Springer.

Eksterne lenker

Stephen Boyd og Lieven Vandenberghe, Convex Optimization (PDF)