Ausreichende und notwendige Bedingungen für Global Optima
Satz
Sei f eine doppelt differenzierbare Funktion. Wenn $ \ bar {x} $ ein lokales Minimum ist, dann ist $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ und die hessische Matrix $ H \ left (\ bar {x} \ right) $ ist ein positives Semidefinit.
Beweis
Sei $ d \ in \ mathbb {R} ^ n $. Da f bei $ \ bar {x} $ zweimal differenzierbar ist.
Deshalb,
$ f \ left (\ bar {x} + \ lambda d \ right) = f \ left (\ bar {x} \ right) + \ lambda \ bigtriangledown f \ left (\ bar {x} \ right) ^ T d + \ lambda ^ 2d ^ TH \ links (\ bar {x} \ rechts) d + \ lambda ^ 2d ^ TH \ links (\ bar {x} \ rechts) d + $
$ \ lambda ^ 2 \ left \ | d \ right \ | ^ 2 \ beta \ left (\ bar {x}, \ lambda d \ right) $
Aber $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ und $ \ beta \ left (\ bar {x}, \ lambda d \ right) \ rightarrow 0 $ als $ \ lambda \ rightarrow 0 $
$ \ Rightarrow f \ left (\ bar {x} + \ lambda d \ right) -f \ left (\ bar {x} \ right) = \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d $
Da $ \ bar {x} $ ein lokales Minimum ist, existiert ein $ \ delta> 0 $, so dass $ f \ left (x \ right) \ leq f \ left (\ bar {x} + \ lambda d \ right) ), \ forall \ lambda \ in \ left (0, \ delta \ right) $
Satz
Sei $ f: S \ rightarrow \ mathbb {R} ^ n $, wobei $ S \ subset \ mathbb {R} ^ n $ zweimal über S differenzierbar ist. Wenn $ \ bigtriangledown f \ left (x \ right) = 0 $ und $ H \ left (\ bar {x} \ right) $ ist positiv semidefinit, für alle $ x \ in S $ ist $ \ bar {x} $ eine global optimale Lösung.
Beweis
Da $ H \ left (\ bar {x} \ right) $ positiv semidefinit ist, ist f eine konvexe Funktion über S. Da f bei $ \ bar {x} $ differenzierbar und konvex ist
$ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) \ leq f \ left (x \ right) -f \ left (\ bar {x}) \ right), \ forall x \ in S $
Da $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 ist, ist f \ left (x \ right) \ geq f \ left (\ bar {x} \ right) $
Daher ist $ \ bar {x} $ ein globales Optima.
Satz
Angenommen, $ \ bar {x} \ in S $ ist eine lokale optimale Lösung für das Problem $ f: S \ rightarrow \ mathbb {R} $, wobei S eine nicht leere Teilmenge von $ \ mathbb {R} ^ n $ und ist S ist konvex. $ min \: f \ left (x \ right) $ wobei $ x \ in S $.
Dann:
$ \ bar {x} $ ist eine global optimale Lösung.
Wenn entweder $ \ bar {x} $ streng lokale Minima oder f eine streng konvexe Funktion ist, dann ist $ \ bar {x} $ die eindeutige globale optimale Lösung und auch starke lokale Minima.
Beweis
Sei $ \ bar {x} $ eine weitere globale optimale Lösung für das Problem, so dass $ x \ neq \ bar {x} $ und $ f \ left (\ bar {x} \ right) = f \ left (\ hat { x} \ right) $
Da $ \ hat {x}, \ bar {x} \ in S $ und S konvex ist, ist $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $ und f streng konvex.
$ \ Rightarrow f \ left (\ frac {\ hat {x} + \ bar {x}} {2} \ right) <\ frac {1} {2} f \ left (\ bar {x} \ right) + \ frac {1} {2} f \ left (\ hat {x} \ right) = f \ left (\ hat {x} \ right) $
Das ist Widerspruch.
Daher ist $ \ hat {x} $ eine einzigartige globale optimale Lösung.
Logische Folge
Sei $ f: S \ subset \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ eine differenzierbare konvexe Funktion, wobei $ \ phi \ neq S \ subset \ mathbb {R} ^ n $ eine konvexe Menge ist. Betrachten Sie das Problem $ min f \ left (x \ right), x \ in S $, dann ist $ \ bar {x} $ eine optimale Lösung, wenn $ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T. \ left (x- \ bar {x} \ right) \ geq 0, \ forall x \ in S. $
Beweis
Sei $ \ bar {x} $ eine optimale Lösung, dh $ f \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ forall x \ in S $
$ \ Rightarrow f \ left (x \ right) = f \ left (\ bar {x} \ right) \ geq 0 $
$ f \ left (x \ right) = f \ left (\ bar {x} \ right) + \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ rechts) + \ left \ | x- \ bar {x} \ right \ | \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) $
Dabei ist $ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow 0 $ als $ x \ rightarrow \ bar {x} $
$ \ Rightarrow f \ left (x \ right) -f \ left (\ bar {x} \ right) = \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x } \ right) \ geq 0 $
Logische Folge
Sei f eine differenzierbare konvexe Funktion bei $ \ bar {x} $, dann ist $ \ bar {x} $ das globale Minimum, wenn $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $
Beispiele
$ f \ left (x \ right) = \ left (x ^ 2-1 \ right) ^ {3}, x \ in \ mathbb {R} $.
$ \ bigtriangledown f \ left (x \ right) = 0 \ Rightarrow x = -1,0,1 $.
$ \ bigtriangledown ^ 2f \ left (\ pm 1 \ right) = 0, \ bigtriangledown ^ 2 f \ left (0 \ right) = 6> 0 $.
$ f \ left (\ pm 1 \ right) = 0, f \ left (0 \ right) = - 1 $
Daher ist $ f \ left (x \ right) \ geq -1 = f \ left (0 \ right) \ Rightarrow f \ left (0 \ right) \ leq f \ left (x \ right) \ forall x \ in \ mathbb {R} $
$ f \ left (x \ right) = x \ log x $ definiert auf $ S = \ left \ {x \ in \ mathbb {R}, x> 0 \ right \} $.
$ {f} 'x = 1 + \ log x $
$ {f} '' x = \ frac {1} {x}> 0 $
Somit ist diese Funktion streng konvex.
$ f \ left (x \ right) = e ^ {x}, x \ in \ mathbb {R} $ ist streng konvex.