Global Optima için Yeterli ve Gerekli Koşullar

Teoremi

F iki kere türevlenebilir fonksiyon olsun. $ \ Bar {x} $ yerel bir minimum ise, $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ ve Hessian matrisi $ H \ left (\ bar {x} \ right) $ pozitif bir yarı kesin.

Kanıt

$ D \ in \ mathbb {R} ^ n $ olsun. F $ \ bar {x} $ 'da iki kez türevlenebilir olduğundan.

Bu nedenle,

$ 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 \ sol \ | d \ sağ \ | ^ 2 \ beta \ left (\ bar {x}, \ lambda d \ sağ) $

Ancak $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ ve $ \ beta \ left (\ bar {x}, \ lambda d \ right) \ rightarrow 0 $, $ \ lambda \ rightarrow 0 $ olarak

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

$ \ Bar {x} $ yerel bir minimum olduğundan, $ f \ left (x \ right) \ leq f \ left (\ bar {x} + \ lambda d \ right) şeklinde bir $ \ delta> 0 $ vardır ), \ forall \ lambda \ in \ left (0, \ delta \ right) $

Teoremi

$ F: S \ rightarrow \ mathbb {R} ^ n $ burada $ S \ subset \ mathbb {R} ^ n $, S'ye göre iki kez türevlenebilir olsun. $ \ Bigtriangledown f \ left (x \ right) = 0 $ ve $ H \ left (\ bar {x} \ right) $ pozitif yarı kesin, S $ içindeki tüm $ x \ için, o zaman $ \ bar {x} $ global bir optimal çözümdür.

Kanıt

$ H \ left (\ bar {x} \ right) $ pozitif yarı kesin olduğundan, f, S'ye göre dışbükey fonksiyondur. F türevlenebilir ve $ \ bar {x} $ 'da dışbükey olduğundan

$ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) \ leq f \ left (x \ sağ) -f \ left (\ bar {x} \ right), \ forall x \ in S $

$ \ Bigtriangledown f \ left (\ bar {x} \ right) = 0, f \ left (x \ right) \ geq f \ left (\ bar {x} \ right) $ olduğundan

Dolayısıyla, $ \ bar {x} $ global bir optimadır.

Teoremi

Diyelim ki S $ 'daki $ \ bar {x} \, $ f: S \ rightarrow \ mathbb {R} $ sorununa yerel olarak en uygun çözümdür burada S $ \ mathbb {R} ^ n $' ın boş olmayan bir alt kümesidir ve S dışbükeydir. $ min \: f \ left (x \ right) $ burada $ x \ S $ içinde.

Sonra:

• $ \ bar {x} $ küresel bir en uygun çözümdür.

• $ \ Bar {x} $ kesinlikle yerel minimumsa veya f kesinlikle dışbükey bir işlevse, o zaman $ \ bar {x} $ benzersiz küresel en iyi çözümdür ve ayrıca güçlü yerel minimumdur.

Kanıt

$ \ Bar {x} $, soruna $ x \ neq \ bar {x} $ ve $ f \ left (\ bar {x} \ right) = f \ left (\ hat { x} \ sağ) $

$ \ Hat {x}, S $ ve S içindeki \ bar {x} \ dışbükey olduğundan, S $ ve f içindeki $ \ frac {\ hat {x} + \ bar {x}} {2} \ kesinlikle dışbükey.

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

Bu bir çelişkidir.

Bu nedenle, $ \ hat {x} $ benzersiz bir küresel optimum çözümdür.

Sonuç

$ F: S \ subset \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $, $ \ phi \ neq S \ subküme \ mathbb {R} ^ n $ 'ın bir dışbükey küme olduğu, türevlenebilir bir dışbükey işlev olsun. S $ içindeki $ min f \ left (x \ right), x \ problemini düşünün, o zaman $ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T ise $ \ bar {x} $ en uygun çözümdür \ left (x- \ bar {x} \ right) \ geq 0, \ forall x \ in S. $

Kanıt

$ \ Bar {x} $ en uygun çözüm olsun, yani S $ için $ f \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ forall x \

$ \ Rightarrow f \ left (x \ right) = f \ left (\ bar {x} \ sağ) \ geq 0 $

$ f \ left (x \ right) = f \ left (\ bar {x} \ right) + \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ sağ) + \ sol \ | x- \ bar {x} \ right \ | \ alpha \ left (\ bar {x}, x- \ bar {x} \ sağ) $

$ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow 0 $ $ x \ rightarrow \ bar {x} $ olarak

$ \ Rightarrow f \ left (x \ right) -f \ left (\ bar {x} \ right) = \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x } \ sağ) \ geq 0 $

Sonuç

F $ \ bar {x} $ konumunda türevlenebilir bir dışbükey fonksiyon olsun, o zaman $ \ bar {x} $ global minimum ancak $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $

Örnekler

• $ f \ left (x \ sağ) = \ 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 \ sağ) = 6> 0 $.

  $ f \ left (\ pm 1 \ sağ) = 0, f \ left (0 \ sağ) = - 1 $

  Dolayısıyla, $ 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 \ sağ) = x \ log x $ $ S = \ left \ {x \ in \ mathbb {R}, x> 0 \ right \} $ için tanımlandı.

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

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

  Bu nedenle, bu işlev kesinlikle dışbükeydir.

• $ f \ left (x \ sağ) = e ^ {x}, x \ in \ mathbb {R} $ kesinlikle dışbükeydir.