Optimisation déterministe Flashcards
Soit C une partie convexe de E. Une fonction f : C → R est dite :
- convexe sur C ssi
- st convexe sur C ssi
- fortement convexe de module alpha >0 ssi
- f(tx + (1 − t)y) ≤ tf(x) + (1 − t)f(y), ∀x, y ∈ C, ∀t ∈ [0, 1]
- f(tx + (1 − t)y) < tf(x) + (1 − t)f(y), ∀x, y ∈ C t.q. x != y, ∀t ∈]0, 1[.
- f(tx + (1 − t)y) ≤ tf(x) + (1 − t)f(y) − α/2t(1 − t)||x − y||2, ∀x, y ∈ C, ∀t ∈ [0, 1].
Différentiabilité au sens de Fréchet.
-Une fonction f : E → R est dite différentiable (au sens de Fréchet) au point
x ∈ E ssi
-Une fonction f est dite de classe C^1 ssi
-Il existe un élément ∇f(x) ∈ E’ appelé gradient de f, tel que
f(x+h)=f(x) + (∇f(x), h) + o(h) quand h->0
-Elle est différentiable et son gradient ∇f est continue
Une fonction f : E → R est dite différentiable (au sens de Gâteaux) au point
x ∈ E ssi
il existe un élément ∇f(x) ∈ E’ appelé gradient de f, tel que
(∇f(x), u)= limt→0 f(x + tu) − f(x) / t , ∀u ∈ E.
Caractérisation de la convexité dans le cas des fonctions C^1
Soit C une partie convexe de E. Si f : C → R est de classe C1, alors les
trois propriétés suivantes sont équivalentes
i) f est convexe sur C
ii) f(y) ≥ f(x) + (∇f(x), y-x), ∀x, y ∈ C.
iii) ∇f est monotone sur C, dans le sens où (∇f(y)-∇f(x), y-x) ≥ 0, ∀x, y ∈ C.
Si f est de classe C2, alors f est convexe sur C ssi (∇2f(x).(y − x), y − x) ≥ 0, ∀x, y ∈ C.
Remarque. En particulier, si f est C2, alors la hessienne ∇2f(x) est semi-définie positive en
tout point intérieur x ∈ C◦
Caractérisation de la forte convexité dans le cas des fonctions C^1
Soit C une partie convexe de E. Si f : C → R est de classe C1, alors les
trois propriétés suivantes sont équivalentes
i) f est fortement convexe de module alpha sur C
ii) f(y) ≥ f(x) +(∇f(x), y − x) + alpha/2 ||y-x||2 , ∀x, y ∈ C.
iii) ∇f est monotone sur C, dans le sens où (∇f(y) − ∇f(x), y − x) ≥ alpha/||y-x||2, ∀x, y ∈ C.
Si f est de classe C2, alors f est convexe sur C ssi
(∇2f(x).(y − x), y − x) ≥ alpha||y − x||**2 ∀x, y ∈ C.
Définition d’une fonction coercive
Une fonction f : E → R est dite coercive ssi lim x→+∞ f(x) = +∞.
Une fonction fortement convexe sur E est coercive
Conditions pour que f :C->R possède au moins un minimiseur
Si E est un espace de dimension finie, C est une partie fermée, non vide,
de E et f : C → R est continue et coercive, la fonction f possède alors au moins un
minimiseur sur C.
Théorème : Règle de Fermat
Si f est différentiable et C est une partie convexe fermée
de E, alors
tout minimiseur de f sur C vérifie
(∇f(x), x − x) ≥ 0, ∀x ∈ C.
De plus, si f est convexe, alors x* est une minimiseur sur C ssi cette cond est vérifiée
Si f est diff´erentiable et convexe et si xˆ est un point int´erieur `a C, alors xˆ
est un minimiseur de f sur C ssi
∇f(ˆx) = 0.
Remarque. Si f est C1 et fortement convexe, on a alors
alpha/2||x − x||**2 ≤ f(x) − f(x), ∀x ∈ E.
Cette propriété permet de calculer des taux de convergence.
Vitesse de convergence :
Soient (xn)n∈N une suite convergente, x* ∈ E sa limite et
Q = lim sup n→+∞ ||xn+1 − xˆ||/||xn − xˆ||
On dit que la suite (xn)n∈N converge :
- sous-linéairement, si Q = 1,
- linéairement, si Q ∈]0, 1[,
- super-linéairement, si Q = 0.
Problème d’optimisation et problèmes de points fixes
Que ce soit dans le cas différentiable ou non-différentiable, un problème d’optimisation
est souvant reformulé comme un problème de point fixe, c’est-à-dire, résoudre une équation du type T(x) = x. Le théorème de Picard nous donne un algorithme pour en estimer la solution lorsque la fonction T est contractante. Les fonctions que l’on est amené à traiter
sont cependant rarement contractantes. Il convient donc de donner un é noncé plus général au théorème de point fixe. On introduit pour cela des notions plus faibles que la contraction.
Définition application non-expensive
Une application f de E->E est dite non expansive ssi elle est 1-lipschitzienne :
||T(x) − T(y)|| ≤ ||x − y||, ∀x, y ∈ E
Définition application alpha-moyennée
Soit α ∈]0, 1]. Une application T:E->E est dite α-moyennée ssi
Il existe R de E->E, non-expansive, telle que T=αR + (1-α)Id
Une application 1/2 -moyennée est dite fermement non-expansive
Autre caractérisation d’une application T α-moyennée (inégalité)
Une application T est α-moyennée ssi
||T(x) − T(y)||2 + (1 − α) / α ||(Id − T)(x) − (Id − T)(y)||2 ≤ ||x − y||2, ∀x, y ∈ E
