Conditions suffisantes et nécessaires pour Global Optima

Théorème

Soit f une fonction deux fois différentiable. Si $ \ bar {x} $ est un minimum local, alors $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ et la matrice hessienne $ H \ left (\ bar {x} \ right) $ est un semi-défini positif.

Preuve

Soit $ d \ in \ mathbb {R} ^ n $. Puisque f est deux fois différentiable en $ \ bar {x} $.

Par conséquent,

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

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

Mais $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ et $ \ 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 $

Puisque $ \ bar {x} $ est un minimum local, il existe un $ \ delta> 0 $ tel que $ f \ left (x \ right) \ leq f \ left (\ bar {x} + \ lambda d \ right) ), \ forall \ lambda \ in \ left (0, \ delta \ right) $

Théorème

Soit $ f: S \ rightarrow \ mathbb {R} ^ n $ où $ S \ subset \ mathbb {R} ^ n $ soit deux fois différentiable sur S.Si $ \ bigtriangledown f \ left (x \ right) = 0 $ et $ H \ left (\ bar {x} \ right) $ est semi-défini positif, pour tout $ x \ dans S $, alors $ \ bar {x} $ est une solution globale optimale.

Preuve

Puisque $ H \ left (\ bar {x} \ right) $ est semi-défini positif, f est une fonction convexe sur S. Puisque f est différentiable et convexe en $ \ 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 $

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

Par conséquent, $ \ bar {x} $ est un optima global.

Théorème

Supposons que $ \ bar {x} \ in S $ est une solution optimale locale au problème $ f: S \ rightarrow \ mathbb {R} $ où S est un sous-ensemble non vide de $ \ mathbb {R} ^ n $ et S est convexe. $ min \: f \ left (x \ right) $ où $ x \ en S $.

Ensuite:

• $ \ bar {x} $ est une solution globale optimale.

• Si $ \ bar {x} $ est strictement des minima locaux ou f est une fonction strictement convexe, alors $ \ bar {x} $ est la solution optimale globale unique et est également des minima locaux forts.

Preuve

Soit $ \ bar {x} $ une autre solution globale optimale au problème telle que $ x \ neq \ bar {x} $ et $ f \ left (\ bar {x} \ right) = f \ left (\ hat { x} \ droite) $

Puisque $ \ hat {x}, \ bar {x} \ en S $ et S est convexe, alors $ \ frac {\ hat {x} + \ bar {x}} {2} \ en S $ et f est strictement convexe.

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

C'est une contradiction.

Par conséquent, $ \ hat {x} $ est une solution optimale globale unique.

Corollaire

Soit $ f: S \ subset \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ une fonction convexe différentiable où $ \ phi \ neq S \ subset \ mathbb {R} ^ n $ est un ensemble convexe. Considérons le problème $ min f \ left (x \ right), x \ in S $, alors $ \ bar {x} $ est une solution optimale si $ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) \ geq 0, \ forall x \ in S. $

Preuve

Soit $ \ bar {x} $ une solution optimale, c'est-à-dire $ f \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ forall x \ in S $

$ \ Flèche droite f \ gauche (x \ droite) = f \ gauche (\ bar {x} \ droite) \ geq 0 $

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

où $ \ 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 } \ droite) \ geq 0 $

Corollaire

Soit f une fonction convexe différentiable à $ \ bar {x} $, alors $ \ bar {x} $ est le minimum global iff $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $

Exemples

• $ 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 \ gauche (\ pm 1 \ droite) = 0, f \ gauche (0 \ droite) = - 1 $

  Par conséquent, $ 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 $ défini sur $ S = \ left \ {x \ in \ mathbb {R}, x> 0 \ right \} $.

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

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

  Ainsi, cette fonction est strictement convexe.

• $ f \ left (x \ right) = e ^ {x}, x \ in \ mathbb {R} $ est strictement convexe.