Wystarczające i niezbędne warunki dla Global Optima

Twierdzenie

Niech f będzie funkcją podwójnie różniczkowalną. Jeśli $ \ bar {x} $ jest lokalną minimą, to $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ i macierz Hesji $ H \ left (\ bar {x} \ right) $ jest dodatnią, częściowo skończoną.

Dowód

Niech $ d \ in \ mathbb {R} ^ n $. Ponieważ f jest dwukrotnie różniczkowalne przy $ \ bar {x} $.

W związku z tym,

$ f \ left (\ bar {x} + \ lambda d \ right) = f \ left (\ bar {x} \ right) + \ lambda \ bigtriangledown f \ left (\ bar {x} \ right) ^ T d + \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d + \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d + $

$ \ lambda ^ 2 \ left \ | d \ right \ | ^ 2 \ beta \ left (\ bar {x}, \ lambda d \ right) $

Ale $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ i $ \ beta \ left (\ bar {x}, \ lambda d \ right) \ rightarrow 0 $ as $ \ lambda \ rightarrow 0 $

$ \ Rightarrow f \ left (\ bar {x} + \ lambda d \ right) -f \ left (\ bar {x} \ right) = \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d $

Ponieważ $ \ bar {x} $ jest lokalną minimą, istnieje $ \ delta> 0 $ taka, że ​​$ f \ left (x \ right) \ leq f \ left (\ bar {x} + \ lambda d \ right ), \ forall \ lambda \ in \ left (0, \ delta \ right) $

Twierdzenie

Niech $ f: S \ rightarrow \ mathbb {R} ^ n $ gdzie $ S \ subset \ mathbb {R} ^ n $ będzie dwa razy różniczkowalne po S. Jeśli $ \ bigtriangledown f \ left (x \ right) = 0 $ i $ H \ left (\ bar {x} \ right) $ jest dodatnią półokreśloną, dla wszystkich $ x \ w S $, to $ \ bar {x} $ jest globalnym optymalnym rozwiązaniem.

Dowód

Ponieważ $ H \ left (\ bar {x} \ right) $ jest dodatnią półokreśloną, f jest funkcją wypukłą nad S. Ponieważ f jest różniczkowalne i wypukłe przy $ \ bar {x} $

$ \ 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 $

Ponieważ $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0, f \ left (x \ right) \ geq f \ left (\ bar {x} \ right) $

Stąd $ \ bar {x} $ jest optymalną globalną wartością.

Twierdzenie

Załóżmy, że $ \ bar {x} \ in S $ jest lokalnym optymalnym rozwiązaniem problemu $ f: S \ rightarrow \ mathbb {R} $ gdzie S jest niepustym podzbiorem $ \ mathbb {R} ^ n $ i S jest wypukła. $ min \: f \ left (x \ right) $ gdzie $ x \ in S $.

Następnie:

• $ \ bar {x} $ to optymalne rozwiązanie globalne.

• Jeśli albo $ \ bar {x} $ jest ściśle lokalnymi minimami, albo f jest funkcją ściśle wypukłą, to $ \ bar {x} $ jest unikalnym globalnym optymalnym rozwiązaniem, a także silnymi lokalnymi minimami.

Dowód

Niech $ \ bar {x} $ będzie kolejnym globalnym optymalnym rozwiązaniem problemu takim, że $ x \ neq \ bar {x} $ i $ f \ left (\ bar {x} \ right) = f \ left (\ hat { x} \ right) $

Ponieważ $ \ hat {x}, \ bar {x} \ in S $ i S jest wypukłe, to $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $ if jest ściśle wypukły.

$ \ 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) $

To jest sprzeczność.

Dlatego $ \ hat {x} $ jest unikalnym, optymalnym rozwiązaniem globalnym.

Następstwo

Niech $ f: S \ subset \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ będzie różniczkowalną funkcją wypukłą, gdzie $ \ phi \ neq S \ subset \ mathbb {R} ^ n $ jest zbiorem wypukłym. Rozważ problem $ min f \ left (x \ right), x \ in S $, a następnie $ \ bar {x} $ jest optymalnym rozwiązaniem, jeśli $ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) \ geq 0, \ forall x \ in S. $

Dowód

Niech $ \ bar {x} $ jest rozwiązaniem optymalnym, tj. $ 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} \ po prawej) + \ lewo \ | x- \ bar {x} \ right \ | \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) $

gdzie $ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow 0 $ as $ 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 $

Następstwo

Niech f będzie różniczkowalną wypukłą funkcją przy $ \ bar {x} $, a następnie $ \ bar {x} $ to globalne minimum iff $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $

Przykłady

• $ 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 $

  Stąd $ 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 $ zdefiniowane w $ S = \ left \ {x \ in \ mathbb {R}, x> 0 \ right \} $.

  $ {f} 'x = 1 + \ log x $

  $ {f} '' x = \ frac {1} {x}> 0 $

  Zatem funkcja ta jest ściśle wypukła.

• $ f \ left (x \ right) = e ^ {x}, x \ in \ mathbb {R} $ jest ściśle wypukłe.