Konvexe Optimierung - Differenzierbare Funktion

Sei S eine nicht leere offene Menge in $ \ mathbb {R} ^ n $, dann soll $ f: S \ rightarrow \ mathbb {R} $ bei $ \ hat {x} \ in S $ if differenzierbar sein Es gibt einen Vektor $ \ bigtriangledown f \ left (\ hat {x} \ right) $ namens Gradientenvektor und eine Funktion $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $, so dass

$ f \ left (x \ right) = f \ left (\ hat {x} \ right) + \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x- \ hat {x} \ rechts) + \ left \ | x = \ hat {x} \ right \ | \ alpha \ left (\ hat {x}, x- \ hat {x} \ right), \ forall x \ in S $ where

$ \ alpha \ left (\ hat {x}, x- \ hat {x} \ right) \ rightarrow 0 \ bigtriangledown f \ left (\ hat {x} \ right) = \ left [\ frac {\ partielle f} {\ partielle x_1} \ frac {\ partielle f} {\ partielle x_2} ... \ frac {\ partielle f} {\ partielle x_n} \ rechts] _ {x = \ hat {x}} ^ {T} $

Satz

Sei S eine nicht leere, offene Konvexmenge in $ \ mathbb {R} ^ n $ und sei $ f: S \ rightarrow \ mathbb {R} $ auf S differenzierbar. Dann ist f genau dann konvex, wenn für $ x_1, x_2 \ in S, \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $

Beweis

Sei f eine konvexe Funktion. dh für $ x_1, x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $

$ f \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ rechts) $

$ \ Rightarrow f \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] \ leq \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right ) + f \ left (x_2 \ right) $

$ \ Rightarrow \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right) \ geq f \ left (x_2 + \ lambda \ left (x_1-x_2 \ right) \ right) - f \ left (x_2 \ right) $

$ \ Rightarrow \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right) \ geq f \ left (x_2 \ right) + \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ lambda + $

$ \ left \ | \ lambda \ left (x_1-x_2 \ right) \ right \ | \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) -f \ left (x_2 \ right) \ right) $

Dabei ist $ \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) \ right) \ rightarrow 0 $ als $ \ lambda \ rightarrow 0 $

Wenn wir auf beiden Seiten durch $ \ lambda $ dividieren, erhalten wir -

$ f \ left (x_1 \ right) -f \ left (x_2 \ right) \ geq \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) $

Umgekehrt

Sei für $ x_1, x_2 \ in S, \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $

Um zu zeigen, dass f konvex ist.

Da S konvex ist, ist $ x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $

Da also $ x_1, x_3 \ in S $

$ f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 -x_3 \ right) $

$ \ Rightarrow f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 - \ lambda x_1- \ left (1- \ lambda) \ rechts) x_2 \ rechts) $

$ \ Rightarrow f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ left (1- \ lambda \ right) \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 - x_2 \ rechts) $

Da also $ x_2, x_3 \ in S $

$ f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2-x_3 \ right) $

$ \ Rightarrow f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2- \ lambda x_1- \ left (1- \ lambda) \ rechts) x_2 \ rechts) $

$ \ Rightarrow f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ left (- \ lambda \ right) \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ rechts) $

Wenn wir also die obigen Gleichungen kombinieren, erhalten wir -

$ \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_3 \ right) \ right) + \ left (1- \ lambda \ right) \ left (f \ left (x_2 \ right) -f \ left (x_3 \ right) \ right) \ geq 0 $

$ \ Rightarrow f \ left (x_3 \ right) \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right) $

Satz

Sei S eine nicht leere offene konvexe Menge in $ \ mathbb {R} ^ n $ und sei $ f: S \ rightarrow \ mathbb {R} $ auf S differenzierbar, dann ist f auf S genau dann konvex, wenn für beliebig $ x_1, x_2 \ in S, \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

Beweis

sei f eine konvexe Funktion, dann benutze den vorherigen Satz -

$ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $ und

$ \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq f \ left (x_2 \ right) -f \ left (x_1 \ right) $

Wenn wir die beiden obigen Gleichungen addieren, erhalten wir -

$ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) + \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_1-x_2 \ right) \ leq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

Umgekehrt

Lassen Sie für jedes $ x_1, x_2 \ in S, \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

Um zu zeigen, dass f konvex ist.

Sei $ x_1, x_2 \ in S $, also nach dem Mittelwertsatz $ \ frac {f \ left (x_1 \ right) -f \ left (x_2 \ right)} {x_1-x_2} = \ bigtriangledown f \ left ( x \ rechts), x \ in \ links (x_1-x_2 \ rechts) \ Rechtspfeil x = \ Lambda x_1 + \ links (1- \ Lambda \ rechts) x_2 $, da S eine konvexe Menge ist.

$ \ Rightarrow f \ left (x_1 \ right) - f \ left (x_2 \ right) = \ left (\ bigtriangledown f \ left (x \ right) ^ T \ right) \ left (x_1-x_2 \ right) $

für $ x, x_1 $ wissen wir -

$ \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x-x_1 \ right) \ geq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2- x_1 \ right) \ geq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (1- \ lambda \ right) \ left (x_2-x_1 \ right) ) \ geq 0 $

$ \ Rightarrow \ bigtriangledown f \ left (x \ right) ^ T \ left (x_2-x_1 \ right) \ geq \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) $

Wenn wir die obigen Gleichungen kombinieren, erhalten wir -

$ \ Rightarrow \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq f \ left (x_2 \ right) -f \ left (x_1 \ right) $

Unter Verwendung des letzten Satzes ist f daher eine konvexe Funktion.

Zweimal differenzierbare Funktion

Sei S eine nicht leere Teilmenge von $ \ mathbb {R} ^ n $ und sei $ f: S \ rightarrow \ mathbb {R} $, dann soll f bei $ \ bar {x} \ in S zweimal differenzierbar sein $ wenn es einen Vektor $ \ bigtriangledown f \ left (\ bar {x} \ right), eine \: nXn $ -Matrix $ H \ left (x \ right) $ (hessische Matrix genannt) und eine Funktion $ \ alpha gibt: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $, so dass $ f \ left (x \ right) = f \ left (\ bar {x} + x- \ bar {x} \ right) = f \ links (\ bar {x} \ rechts) + \ bigtriangledown f \ links (\ bar {x} \ rechts) ^ T \ links (x- \ bar {x} \ rechts) + \ frac {1} {2} \ links (x- \ bar {x} \ rechts) H \ links (\ bar {x} \ rechts) \ links (x- \ bar {x} \ rechts) $

Dabei ist $ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow Oasx \ rightarrow \ bar {x} $