Funkcja wypukła i wklęsła
Niech $ f: S \ rightarrow \ mathbb {R} $, gdzie S jest niepustym wypukłym ustawionym w $ \ mathbb {R} ^ n $, a następnie $ f \ left (x \ right) $ jest wypukłe na S if $ 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 \ right), \ forall \ lambda \ in \ left (0,1 \ right) $.
Z drugiej strony Niech $ f: S \ rightarrow \ mathbb {R} $, gdzie S jest niepustym wypukłym ustawionym w $ \ mathbb {R} ^ n $, a następnie mówi się $ f \ left (x \ right) $ być wklęsłym na S, jeśli $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ geq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) ) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.
Niech $ f: S \ rightarrow \ mathbb {R} $ gdzie S jest niepustym wypukłym ustawionym w $ \ mathbb {R} ^ n $, a następnie $ f \ left (x \ right) $ mówi się, że jest ściśle wypukłe na S if $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) <\ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.
Niech $ f: S \ rightarrow \ mathbb {R} $ gdzie S jest niepustym wypukłym ustawionym w $ \ mathbb {R} ^ n $, a następnie $ f \ left (x \ right) $ mówi się, że jest ściśle wklęsłe na S if $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right)> \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.
Przykłady
Funkcja liniowa jest zarówno wypukła, jak i wklęsła.
$ f \ left (x \ right) = \ left | x \ right | $ to funkcja wypukła.
$ f \ left (x \ right) = \ frac {1} {x} $ jest funkcją wypukłą.
Twierdzenie
Niech $ f_1, f_2, ..., f_k: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ będą wypukłymi funkcjami. Rozważmy funkcję $ f \ lewo (x \ w prawo) = \ Displaystyle \ sum \ limity_ {j = 1} ^ k \ alpha_jf_j \ lewo (x \ prawo) $, gdzie $ \ alpha_j> 0, j = 1, 2,. ..k, $ następnie $ f \ left (x \ right) $ jest funkcją wypukłą.
Dowód
Ponieważ $ f_1, f_2, ... f_k $ są funkcjami wypukłymi
Dlatego $ f_i \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f_i \ left (x_1 \ right) + \ left (1- \ lambda \ right) f_i \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $ i $ i = 1, 2, ...., k $
Rozważmy funkcję $ f \ left (x \ right) $.
W związku z tym,
$ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) $
$ = \ Displaystyle \ suma \ limity_ {j = 1} ^ k \ alpha_jf_j \ lewo (\ lambda x_1 + 1- \ lambda \ prawo) x_2 \ równoważnik \ Displaystyle \ suma \ limity_ {j = 1} ^ k \ alpha_j \ lambda f_j \ left (x_1 \ right) + \ left (1- \ lambda \ right) f_j \ left (x_2 \ right) $
$ \ Rightarrow f \ lewo (\ lambda x_1 + \ lewo (1- \ lambda \ prawej) x_2 \ prawej) \ równoważnik \ lambda \ lewo (\ Displaystyle \ suma \ limity_ {j = 1} ^ k \ alfa _jf_j \ lewo ( x_1 \ po prawej) \ po prawej) + \ lewo (\ Displaystyle \ suma \ limit_ {j = 1} ^ k \ alpha _jf_j \ lewo (x_2 \ prawo) \ po prawej) $
$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_2 \ right) \ leq \ left (1- \ lambda \ right) f \ lewo (x_2 \ prawo) $
Stąd $ f \ left (x \ right) $ jest funkcją wypukłą.
Twierdzenie
Niech $ f \ left (x \ right) $ będzie wypukłą funkcją na wypukłym zbiorze $ S \ subset \ mathbb {R} ^ n $ wtedy lokalne minima $ f \ left (x \ right) $ na S to a globalne minima.
Dowód
Niech $ \ hat {x} $ będzie lokalną wartością minimalną dla $ f \ left (x \ right) $, a $ \ hat {x} $ nie jest minimą globalną.
zatem $ \ istnieje \ hat {x} \ in S $ tak, że $ f \ left (\ bar {x} \ right) <f \ left (\ hat {x} \ right) $
Ponieważ $ \ hat {x} $ jest lokalną minimą, istnieje sąsiedztwo $ N_ \ varepsilon \ left (\ hat {x} \ right) $ takie, że $ f \ left (\ hat {x} \ right) \ leq f \ left (x \ right), \ forall x \ in N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $
Ale $ f \ left (x \ right) $ jest wypukłą funkcją na S, więc dla $ \ lambda \ in \ left (0, 1 \ right) $
mamy $ \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} \ leq \ lambda f \ left (\ hat {x} \ right) + \ left (1- \ lambda \ right) f \ left (\ bar {x} \ right) $
$ \ Rightarrow \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} <\ lambda f \ left (\ hat {x} \ right) + \ left (1- \ lambda \ po prawej) f \ left (\ hat {x} \ right) $
$ \ Rightarrow \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} <f \ left (\ hat {x} \ right), \ forall \ lambda \ in \ left (0 , 1 \ po prawej) $
Ale dla jakiejś $ \ lambda <1 $, ale bliskiej 1, mamy
$ \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} \ in N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $ i $ f \ left ( \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} \ right) <f \ left (\ bar {x} \ right) $
co jest sprzecznością.
Stąd $ \ bar {x} $ to globalne minimum.
Epigraf
niech S będzie niepustym podzbiorem w $ \ mathbb {R} ^ n $ i niech $ f: S \ rightarrow \ mathbb {R} $ wtedy epigraf f oznaczony przez epi (f) lub $ E_f $ będzie podzbiorem z $ \ mathbb {R} ^ n + 1 $ zdefiniowane przez $ E_f = \ left \ {\ left (x, \ alpha \ right): x \ in \ mathbb {R} ^ n, \ alpha \ in \ mathbb { R}, f \ left (x \ right) \ leq \ alpha \ right \} $
Hypograph
niech S będzie niepustym podzbiorem w $ \ mathbb {R} ^ n $ i niech $ f: S \ rightarrow \ mathbb {R} $, a następnie hipografią f oznaczoną przez hyp (f) lub $ H_f = \ left \ {\ left (x, \ alpha \ right): x \ in \ mathbb {R} ^ n, \ alpha \ in \ mathbb {R} ^ n, \ alpha \ in \ mathbb {R}, f \ left ( x \ right) \ geq \ alpha \ right \} $
Twierdzenie
Niech S będzie niepustym wypukłym zbiorem w $ \ mathbb {R} ^ n $ i niech $ f: S \ rightarrow \ mathbb {R} ^ n $, wtedy f jest wypukłe wtedy i tylko wtedy, gdy jego epigraf $ E_f $ jest zestaw wypukły.
Dowód
Niech f jest funkcją wypukłą.
Aby pokazać $ E_f $ jest zbiorem wypukłym.
Niech $ \ left (x_1, \ alpha_1 \ right), \ left (x_2, \ alpha_2 \ right) \ in E_f, \ lambda \ in \ left (0, 1 \ right) $
Aby wyświetlić $ \ lambda \ left (x_1, \ alpha_1 \ right) + \ left (1- \ lambda \ right) \ left (x_2, \ alpha_2 \ right) \ in E_f $
$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2, \ lambda \ alpha_1 + \ left (1- \ lambda \ right) \ alpha_2 \ right] \ in E_f $
$ f \ left (x_1 \ right) \ leq \ alpha _1, f \ left (x_2 \ right) \ leq \ alpha _2 $
Dlatego $ 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 \ right) $
$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda \ alpha_1 + \ left (1- \ lambda \ right) \ alpha_2 $
Rozmawiać
Niech $ E_f $ jest zbiorem wypukłym.
Aby pokazać, że f jest wypukłe.
tj. aby pokazać, czy $ x_1, x_2 \ in S, \ lambda \ 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 \ right) $
Niech $ x_1, x_2 \ in S, \ lambda \ in \ left (0, 1 \ right), f \ left (x_1 \ right), f \ left (x_2 \ right) \ in \ mathbb {R} $
Ponieważ $ E_f $ jest zbiorem wypukłym, $ \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2, \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) \ po prawej) f \ left (x_2 \ right) \ in E_f $
Dlatego $ 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 \ right) $