Optimisation convexe - Fonction différenciable

Soit S un ensemble ouvert non vide dans $ \ mathbb {R} ^ n $, alors $ f: S \ rightarrow \ mathbb {R} $ est dit différentiable à $ \ hat {x} \ dans S $ si il existe un vecteur $ \ bigtriangledown f \ left (\ hat {x} \ right) $ appelé vecteur dégradé et une fonction $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ telle que

$ f \ left (x \ right) = f \ left (\ hat {x} \ right) + \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x- \ hat {x} \ droite) + \ gauche \ | x = \ hat {x} \ right \ | \ alpha \ left (\ hat {x}, x- \ hat {x} \ right), \ forall x \ in S $ où

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

Théorème

soit S un ensemble convexe ouvert non vide dans $ \ mathbb {R} ^ n $ et soit $ f: S \ rightarrow \ mathbb {R} $ différentiable sur S. Alors, f est convexe si et seulement si pour $ 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) $

Preuve

Soit f une fonction convexe. ie, pour $ 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 \ droite) $

$ \ 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 \ gauche (x_2 \ droite) $

$ \ 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 \ gauche (x_2 \ droite) $

$ \ 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 \ gauche (x_1-x_2 \ droite) \ lambda + $

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

où $ \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) \ right) \ rightarrow 0 $ as $ \ lambda \ rightarrow 0 $

En divisant par $ \ lambda $ des deux côtés, nous obtenons -

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

Converser

Soit pour $ 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) $

Montrer que f est convexe.

Puisque S est convexe, $ x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $

Puisque $ x_1, x_3 \ dans S $, donc

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

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

Puisque, $ x_2, x_3 \ dans S $ donc

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

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

Ainsi, en combinant les équations ci-dessus, nous obtenons -

$ \ lambda \ gauche (f \ gauche (x_1 \ droite) -f \ gauche (x_3 \ droite) \ droite) + \ gauche (1- \ lambda \ droite) \ gauche (f \ gauche (x_2 \ droite) -f \ gauche (x_3 \ droite) \ droite) \ geq 0 $

$ \ Flèche droite f \ gauche (x_3 \ droite) \ leq \ lambda f \ gauche (x_1 \ droite) + \ gauche (1- \ lambda \ droite) f \ gauche (x_2 \ droite) $

Théorème

soit S un convexe ouvert non vide défini dans $ \ mathbb {R} ^ n $ et soit $ f: S \ rightarrow \ mathbb {R} $ différentiable sur S, alors f est convexe sur S si et seulement si pour any $ 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 $

Preuve

soit f une fonction convexe, alors en utilisant le théorème précédent -

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

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

En ajoutant les deux équations ci-dessus, nous obtenons -

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

Converser

Soit pour tout $ 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 $

Montrer que f est convexe.

Soit $ x_1, x_2 \ in S $, donc par théorème de la valeur moyenne, $ \ frac {f \ left (x_1 \ right) -f \ left (x_2 \ right)} {x_1-x_2} = \ bigtriangledown f \ left ( x \ right), x \ in \ left (x_1-x_2 \ right) \ Rightarrow x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ car S est un ensemble convexe.

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

pour $ x, x_1 $, nous savons -

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

En combinant les équations ci-dessus, nous obtenons -

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

Par conséquent, en utilisant le dernier théorème, f est une fonction convexe.

Fonction deux fois différentiable

Soit S un sous-ensemble non vide de $ \ mathbb {R} ^ n $ et soit $ f: S \ rightarrow \ mathbb {R} $ alors f est dit deux fois différentiable en $ \ bar {x} \ dans S $ s'il existe un vecteur $ \ bigtriangledown f \ left (\ bar {x} \ right), une \: nXn $ matrice $ H \ left (x \ right) $ (appelée matrice hessienne) et une fonction $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ tel que $ f \ left (x \ right) = f \ left (\ bar {x} + x- \ bar {x} \ right) = f \ left (\ bar {x} \ right) + \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) + \ frac {1} {2} \ left (x- \ bar {x} \ right) H \ left (\ bar {x} \ right) \ left (x- \ bar {x} \ right) $

où $ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow Oasx \ rightarrow \ bar {x} $