Fonction Quasiconvex différenciable

Théorème

Soit S un ensemble convexe non vide dans $ \ mathbb {R} ^ n $ et $ f: S \ rightarrow \ mathbb {R} $ être différentiable sur S, alors f est quasiconvexe si et seulement si pour tout $ x_1, x_2 \ dans S $ et $ f \ left (x_1 \ right) \ leq f \ left (x_2 \ right) $, nous avons $ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_2-x_1 \ right) \ leq 0 $

Preuve

Soit f une fonction quasiconvexe.

Soit $ x_1, x_2 \ dans S $ tel que $ f \ left (x_1 \ right) \ leq f \ left (x_2 \ right) $

Par différentiabilité de f à $ x_2, \ lambda \ in \ left (0, 1 \ right) $

$ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) = f \ left (x_2 + \ lambda \ left (x_1-x_2 \ right) \ right) = f \ left (x_2 \ right) ) + \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) $

$ + \ lambda \ gauche \ | x_1-x_2 \ droite \ | \ alpha \ gauche (x_2, \ lambda \ gauche (x_1-x_2 \ droite) \ droite) $

$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) -f \ left (x_2 \ right) -f \ left (x_2 \ right) = \ bigtriangledown f \ left (x_2 \ droite) ^ T \ gauche (x_1-x_2 \ droite) $

$ + \ lambda \ gauche \ | x_1-x_2 \ droite \ | \ alpha \ gauche (x2, \ lambda \ gauche (x_1-x_2 \ droite) \ droite) $

Mais puisque f est quasiconvexe, $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq f \ left (x_2 \ right) $

$ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) + \ lambda \ left \ | x_1-x_2 \ droite \ | \ alpha \ gauche (x_2, \ lambda \ gauche (x_1, x_2 \ droite) \ droite) \ leq 0 $

Mais $ \ alpha \ left (x_2, \ lambda \ left (x_1, x_2 \ right) \ right) \ rightarrow 0 $ as $ \ lambda \ rightarrow 0 $

Par conséquent, $ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq 0 $

Converser

laissez pour $ x_1, x_2 \ in S $ et $ f \ left (x_1 \ right) \ leq f \ left (x_2 \ right) $, $ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1, x_2 \ droite) \ leq 0 $

Montrer que f est quasiconvexe, c'est-à-dire $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq f \ left (x_2 \ right) $

Proof by contradiction

Supposons qu'il existe un $ x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ tel que $ f \ left (x_2 \ right) <f \ left (x_3 \ right) $ pour certains $ \ lambda \ in \ gauche (0, 1 \ droite) $

Pour $ x_2 $ et $ x_3, \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2-x_3 \ right) \ leq 0 $

$ \ Rightarrow - \ lambda \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2-x_3 \ right) \ leq 0 $

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

Pour $ x_1 $ et $ x_3, \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_3 \ right) \ leq 0 $

$ \ Rightarrow \ left (1- \ lambda \ right) \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ right) \ leq 0 $

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

ainsi, à partir des équations ci-dessus, $ \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ right) = 0 $

Définissez $ U = \ left \ {x: f \ left (x \ right) \ leq f \ left (x_2 \ right), x = \ mu x_2 + \ left (1- \ mu \ right) x_3, \ mu \ in \ gauche (0,1 \ droite) \ droite \} $

Ainsi on peut trouver $ x_0 \ dans U $ tel que $ x_0 = \ mu_0 x_2 = \ mu x_2 + \ left (1- \ mu \ right) x_3 $ pour certains $ \ mu _0 \ in \ left (0,1 \ right ) $ qui est le plus proche de $ x_3 $ et $ \ hat {x} \ in \ left (x_0, x_1 \ right) $ tel que par le théorème de la valeur moyenne,

$$ \ frac {f \ left (x_3 \ right) -f \ left (x_0 \ right)} {x_3-x_0} = \ bigtriangledown f \ left (\ hat {x} \ right) $$

$$ \ Rightarrow f \ left (x_3 \ right) = f \ left (x_0 \ right) + \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x_3-x_0 \ right) $$

$$ \ Rightarrow f \ left (x_3 \ right) = f \ left (x_0 \ right) + \ mu_0 \ lambda f \ left (\ hat {x} \ right) ^ T \ left (x_1-x_2 \ right) $ $

Puisque $ x_0 $ est une combinaison de $ x_1 $ et $ x_2 $ et $ f \ left (x_2 \ right) <f \ left (\ hat {x} \ right) $

En répétant la procédure de départ, $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x_1-x_2 \ right) = 0 $

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

$$ f \ left (x_3 \ right) = f \ left (x_0 \ right) \ leq f \ left (x_2 \ right) $$

$$ \ Flèche droite f \ gauche (x_3 \ droite) \ leq f \ gauche (x_2 \ droite) $$

C'est donc une contradiction.

Exemples

Step 1 - $ f \ gauche (x \ droite) = X ^ 3 $

$ Soit f \ left (x_1 \ right) \ leq f \ left (x_2 \ right) $

$ \ Rightarrow x_ {1} ^ {3} \ leq x_ {2} ^ {3} \ Rightarrow x_1 \ leq x_2 $

$ \ bigtriangledown f \ left (x_2 \ right) \ left (x_1-x_2 \ right) = 3x_ {2} ^ {2} \ left (x_1-x_2 \ right) \ leq 0 $

Ainsi, $ f \ left (x \ right) $ est quasiconvexe.

Step 2 - $ f \ gauche (x \ droite) = x_ {1} ^ {3} + x_ {2} ^ {3} $

Soit $ \ hat {x_1} = \ left (2, -2 \ right) $ et $ \ hat {x_2} = \ left (1, 0 \ right) $

ainsi, $ f \ left (\ hat {x_1} \ right) = 0, f \ left (\ hat {x_2} \ right) = 1 \ Rightarrow f \ left (\ hat {x_1} \ right) \ setminus <f \ gauche (\ hat {x_2} \ droite) $

Ainsi, $ \ bigtriangledown f \ left (\ hat {x_2} \ right) ^ T \ left (\ hat {x_1} - \ hat {x_2} \ right) = \ left (3, 0 \ right) ^ T \ left (1, -2 \ droite) = 3> 0 $

Donc $ f \ left (x \ right) $ n'est pas quasiconvexe.