Ch1 Outil Optim ECC Sept22

Outils Mathématiques en Optimisation differentielle
convexe
ECC
Abdelilah Hakim
Laboratory of Applied Mathematics and Computer Science

Faculty of Science and Techniques
Cady Ayyad University
19/09/2022
(FSTG) Outils Mathématiques en Optimisation differentielle convexe

19/09/2022 1 / 71
Définition et Domaines d’application
Definition de l’optimisation : Choisir parmi plusieurs possibilités une

solution d’un problème mathématique qui répond le mieux à certains
critères
Domaines d’applications
Optimisation des ressources : Gains, coùt dans l’industrie
Transports : trafic aérien, ferroviaire, routier
Domaines millitaire : Couverture radar, réactivité d’intervention,

Gestions de stocks et des troupes
Sciences dures : Physique, chimie, informatique, automatique,

traitement du signal, Intelligence artificielle etc...

19/09/2022 2 / 71
Objectifs du cours
Principales notion : Espace de Hilbert, Differentiabilité, Convexité...
Résultats théoriques : Existence de solution et Unicité
Conditions d’optimalité : Problèmes sans contraintes, Problèmes avec

contraintes, Conditions d’Euler, Conditions Euler Legendre
Algorithmes : Gradient de décentes et ses variantes, Méthode de

Newton

19/09/2022 3 / 71
Qu’est ce que l’optimisation ?
Forme Abstraite d’un problème d’optimisation

E un ensemble
K un sous ensemble de E
une application J : E −→ R
Formulation Mathématique de problème

on veut résoudre le problème
x∗ ∈ K
(
(P) J (x ∗ ) = inf J(x )
x ∈K

19/09/2022 4 / 71
Questions traitées dans un problème de minimisation
Est-ce que inf J(x ) existe ? c.à.d. est-ce que J est bornée
x ∈K
inférieurement ?
Est-ce que l’infimum est atteint dans K ? c.à.d. est-ce qu’il existe
x ∗ ∈ K vérifiant J (x ∗ ) = min J(x )?
Est-ce que l’infimum est atteint dans K ? c.à.d. est-ce qu’il existe
x ∗ ∈ K vérifiant J (x + ) = minx ∈K J(x )?

19/09/2022 5 / 71
Questions traitées dans un problème de minimisation
Est-ce que x ∗ est unique ? Sinon, quelle est la taille de l’ensemble des
solutions ?
Est-ce que l’on peut caractériser x ∗ ? c.à.d. peut-on trouver des

conditions nécessaires et suffisantes pour caractériser un minimum.
Trouver un algorithme d’optimisation pour déterminer la, resp. les,

solutions de (P).

19/09/2022 6 / 71
Résolution d’un problème d’optimisation
la structure de E : espace vectoriel, muni d’une norme, d’un produit

scalaire, de dimension finie ou infinie, ...
les propriétés de K ⊂ E : fermé, borné, convexe, compacte...
les propriétés de J : E −→ R : continuité, différentiabilité, coercivité,

convexité,...

19/09/2022 7 / 71
Est-il vraiment nécessaire d’étudier l’optimisation dans un
espace de Hilbert de dimension infinie ?
On pourrait croire que non :

Beaucoup de problèmes d’optimisation sont posés en dimension finie,
V = Rn ,
Après "discrétisation" tout se ramène à la dimension finie,
C’est beaucoup plus simple en dimension finie.
Néanmoins, la dimension infinie est essentielle :

Souvent la variable d’optimisation est une fonction (comme en
contrôle optimal), donc il faut travailler en dimension infinie,
Même en dimension finie, si la dimension est grande, le point de vue
et les méthodes de la dimension infinie sont très utiles,
Les espaces de Hilbert sont les plus simples en dim. infinie.

19/09/2022 8 / 71
Types de problèmes en optimisation
L’optimisation se scinde essentiellement en deux disciplines dont les outils

et méthodes sont complètement differents. Il s’agit de l’optimisation
discrète et l’optimisation continue.
Si K est discret (K ⊂ Z n , fini ou dénombrable),on parle

d’optimisation combinatoire.Les outils proviennent des mathématiques
discrètes ( Théorie de graphe )
Si K est continue, et J est continue, on parle d’optimisation continue.

Les outils proviennent essentiellement de l’analyse ( Calcul
différentiel, Convexité, Algèbre linéaire )

19/09/2022 9 / 71
Classes de problèmes d’optimisation continues
la classe des problemes d’optimisation continue est bien trop large pour
espérer obtenir une méthode de résolution générale efficiente. On va
restreindre cette classe de problèmes à des sous-classes,
K = {(x1 , x2 , . . . , xn ) ∈ U ⊂ Rn | φi (x1 , . . . , xn ) ⩽ 0, i = 1, . . . , p ,
| {z }
contraintes inégalitaires
ψj (x1 , . . . , xn ) = 0, j = 1, . . . , q }
| {z }
contraintes égalitaires

19/09/2022 10 / 71
Classes de problèmes d’optimisation continues
Programmation linéaire :
lorsque J, φ1 , . . . , φp , ψ1 , . . . , ψq sont des applications affines et,
U = Rn .
Programmation quadratique :
lorsque J est une application quadratique, φ1 , . . . , . . . φp , ψ1 , . . . , ψq
sont, des applications affines et, U = Rn .
Programmation convexe :
problème de minimisaticn lorscue J et φ1 , . . . , φp sont des
applications convexes, ψ1 , . . . , ψq sont des applications affines, et. U
est convexe.

19/09/2022 11 / 71
Problèmes typiques d’optimisation
Résolution d’un système matriciel.
A une matrice symétrique N × N définie positive
b un vecteur de RN .
La solution du système linéaire Ax = b est donnée par le point de

minimum suivant :
1
inf (Ax , x ) − (b, x )
x ∈R 2
N

19/09/2022 12 / 71
Problème de transport.
Exemple de programmation linéaire.
But : Optimiser la livraison d’une marchandise (un problème classique
en logistique).
Problèmatique : On dispose de M entrepôts, indicés par 1 ≤ i ≤ M,
disposant chacun d’un niveau de stocks si . Il faut livrer N clients,
indicés par 1 ≤ j ≤ N, qui ont commandé chacun une quantité rj . Le
coût de transport unitaire entre l’entrepôt i et le client j est donné par
cij .
Les variables de décision : les quantités vij de marchandise partant de
l’entrepôt i vers le client j.
Résolution : Minimiser le coût du transport tout en satisfaisant les
XM XN
commandes deas clients (on suppose que si ≥ rj ).
i=1 j=1
 
XM X
N
inf  cij vij 
(vij )
i=1 j=1
Les contraintes de limites des stocks et de satisfaction des clients :
19/09/2022 13 / 71
Problèmes de moindre carré :

Problème en statistique ou bien en analyse de donnée.
Probleme d’estimation de parametres d’un modele en fonction de
données mesurées ou expérimentales.
Problème de régression linéaire
Formulation du problème :
inf ∥Ax − b∥2 ,
x ∈Rn
b ∈ Rp les données du problème

x ∈ Rn les paramètres inconnus
A, matrice réelle
Exemple algebrique : Quotient de Rayleigh qui permet de calculer les
valeurs et vecteurs proppres d’une matrice symétrique.

19/09/2022 14 / 71
Première valeur propre
A une matrice carré d’ordre n, symétrique
Résolution du problème :
inf (Ax , x )
x ∈Rn ,∥x ∥=1
où ∥x ∥ est la norme euclidienne de x .

19/09/2022 15 / 71
Problèmes d’Entropie
Notion en thérmodynamique, physique statistique et théorie de

l’information.
Problème de maximisation ( changement de signe )
Exemple : Entropie de Shannon en théorie de l’information
n
!
X
inf pi log pi
n
X i=1
p∈Rn+ pi = 1
i=1

19/09/2022 16 / 71
Minimisation d’une énergie mécanique
Minimisation de l’energie mécanique d’une membrane ou bien l’energie

électrostatique d’un conducteur.
Ω un ouvert borné de RN et f une fonction continue sur Ω̄.
Résolution du probleme de Dirichlet pour le Laplacien,
Minimisation de l’energie J(v ) :
1
Z Z
J(v ) = |∇v |2 dx − fvdx
2 Ω Ω
n o
v ∈ V0 = ϕ ∈ C 1 (Ω̄) tel que ϕ = 0 sur ∂Ω .

19/09/2022 17 / 71
Traitement des images
On représente une image noir et blanc par une fonction définie sur un
domaine Ω du plan dont les valeurs indiquent un niveau de gris. Une
image acquise, par exemple par un appareil photographique, f (x ) est
entachée de "bruit" qui correspond à des défauts du capteur
Reduction du bruit : Technique de lissage et régularisation
Préservation des contours
Minimisation de la variation totale
La régularisation u(x ) de l’image originale f (x ) :
Z Z
2
inf J(u) = |∇u|dx + ℓ |f − u| dx ,
u(x ):Ω→R Ω Ω
où ℓ > 0 est un paramètre qui permet de moduler le lissage.

19/09/2022 18 / 71
Apprentissagemachine
On dispose d’un très grand nombre de données (xi )1≤i≤n (des images,
du texte, des mesures expérimentales, etc.)
Données caractérisées par des vecteurs xi ∈ Rd
Un label yi , très souvent un booléen (ici, −1 ou +1 ), qui donne un
type à la donnée xi
On introduit une fonction affine, dite de prédiction,
hw ,τ (x ) = w · x − τ
où w ∈ Rd et τ ∈ R sont des paramètres à optimiser.

On souhaite trouver des paramètres (w , τ ) tels que la prédiction
sgn (hw ,τ (xi )) ≈ yi

soit la meilleure possible.

19/09/2022 19 / 71
Introduction
X , Y et Z trois espaces de Banach
Les conditions d’existence d’optima locaux : Les dérivées d’ordre un

et deux de la fonction coût.
Développement d’un formalisme général pour la notion de dérivation.
Le cas particulier d’espaces X et Y tels que X = Rn et Y = Rm .

19/09/2022 20 / 71
Motivations
Motivations de l’étude des conditions d’optimalité
Calcul des minima d’une fonction dérivable J(x ) définie sur l’intervalle
[a, b] ⊂ R à valeurs réelles
Si x0 est un point de minimum local de J sur l’intervalle [a, b], alors

on a
J ′ (x0 ) ≥ 0 si x0 = a, J ′ (x0 ) = 0 si x0 ∈ a, b , J ′ (x0 ) ≤ 0 si x0 = b


19/09/2022 21 / 71
Motivations
Preuve
Si x0 ∈ [a, b[, on peut choisir x = x0 + h avec h > 0 petit et écrire
J(x ) ≥ J (x0 ), d’où J (x0 ) + hJ ′ (x0 ) + o(h) ≥ J (x0 ), ce qui donne
J ′ (x0 ) ≥ 0 en divisant par h et en faisant tendre h vers 0 .
De même on obtient J ′ (x0 ) ≤ 0 si x0 ∈] a, b] en considérant

x = x0 − h,
Ce qui permet de conclure.

19/09/2022 22 / 71
Conclusion
Conclusion
La stratégie d’obtention des conditions de minimalité tient compte
des contraintes x ∈ [a, b]
Tester la minimalité de x0 dans des directions particulières qui

respectent les contraintes
x0 + h avec h > 0 si x0 ∈ [a, b[,
x0 − h avec h > 0 si x0 ∈ ]a, b]
Notion des directions admissibles

19/09/2022 23 / 71
Définition
Soit f une application X → Y . La dérivée directionnelle de f en x ∈ X
dans la direction h ∈ X est, si elle existe, la limite
f (x + th) − f (x )
f ′ (x , h) := lim . (1)
t10 t
On dira que f est directionellement dérivable en x si les dérivées
directionnelles existent dans toutes les directions.
La dérivée directionnelle est positivement homogène
f ′ (x , th) = tf ′ (x , h), ∀t > 0, (2)
et elle est caractérisée par la relation
∀h ∈ X ; f (x + th) = f (x ) + tf ′ (x , h) + o(t), t ⩾ 0. (3)

19/09/2022 24 / 71
Exemple
Soit f : X → R définie par f (x ) = ∥x ∥. Alors f a des dérivées
directionnelles en x = 0, données par f ′ (0, h) = ∥h∥, pour tout h ∈ X .

19/09/2022 25 / 71
Définition
(i) Si la dérivée directionnelle de f en x existe pour tout h ∈ X , et si
l’application h → f ′ (x , h) est linéaire continue, f est dite Gâteaux
différentiable en x et on note Df (x ) ∈ L(X , Y ) ou bient dx f ou bien f ′ (x )
sa G-dérivée, définie par Df (x )h = f ′ (x , h), pour tout h ∈ X .
(ii) On dit que f est Fréchet différentiable en x , si elle est G-différentiable

en x et vérifie l’identité suivante :
f (x + h) = f (x ) + Df (x )h + o(∥h∥). (4)

19/09/2022 26 / 71
On appelle alors Df (x ) la F-dérivée, ou dérivée Fréchet, de f en x . La
relation 4 équivaut à
f (x + h) − f (x ) − Df (x )h
lim = 0.
h→0 ∥h∥
Si f est F -différentiable, alors f est G-différentiable avec la même dérivée

et les deux notions coïncident si X = R.

19/09/2022 27 / 71
Remarque
Si f est F -différentiable en x , pour tout ε > 0, il existe r > 0 tel que
∥f (x + h) − f (x )∥ ⩽ (∥Df (x )∥ + ε)∥h∥, ∀h; ∥h∥ ⩽ r .

En particulier, f est continue en x .
En revanche, la G-différentiabilité en un point n’implique pas la continuité.

19/09/2022 28 / 71
Lemme
Soit f : X → Y continument G-différentiable. Alors, pour tout x1 et x2
dans X , on a
Z 1
f (x2 ) = f (x1 ) + Df (x1 + t (x2 − x1 )) dt (x2 − x1 )
0

19/09/2022 29 / 71
Proposition(composition)
Soient X , Y , Z trois espaces de Banach, f : X → Y et g : Y → Z . Soit
x ∈ X tel que f et g soient F -differentiables en x et f (x ), respectivement.
Alors l’application composée g ◦ f est F -différentiable, et
D[g ◦ f ](x ) = Dg[f (x )] ◦ Df (x ).
Si de plus f et g sont continument différentiables en x et f (x ),

respectivement, alors g ◦ f est continûment différentiable en x .

19/09/2022 30 / 71
Théorème(Accroissements finis)
Soient a et b dans R, f : [a, b] → X et g : [a, b] → M. Si f et g sont
différentiables sur ]a, b[ et vérifient
∥Df (x )∥ ⩽ Dg(x ), ∀x ∈]a, b[
alors
∥f (b) − f (a)∥ ⩽ g(b) − g(a).

19/09/2022 31 / 71
Corollaires
Corollaire :
Soit f Gâteaux différentiable X → Y , telle que ∥Df (x )∥ ⩽ c, pour tout
x ∈ X . Alors f est lipschitzienne de constante c.
Par ailleurs, prenant f constante dans le théorème des accroissements finis,

on obtient le corollaire suivant :
Corollaire :
Soit [a, b] ⊂ R, g : [a, b] → R de dérivé positive en tout point. Alors g est
croissante.

19/09/2022 32 / 71
Dérivée Partielle
Définition
Soit f une application de X × Y vers Z . On appelle dérivées partielles de f
en (x0 , y0 ), et on note ∂x f (x0 , y0 ) et ∂y f (x0 , y0 ), les dérivées, si elles
existent, des applications x → f (x , y0 ) en x0 et y → f (x0 , y ) en y0 .

19/09/2022 33 / 71
Remarque
Il est facile de vérifier que si f est différentiable en (x0 , y0 ), alors les
dérivées partielles ∂x f (x0 , y0 ) et ∂y f (x0 , y0 ) existent, et sont
caractérisées par la relation
Df (x0 , y0 ) (h, w ) = ∂x f (x0 , y0 ) h + ∂y f (x0 , y0 ) w , pour tout
h ∈ X, w ∈ Y .
A l’inverse, l’existence de ∂x f (x0 , y0 ) et partialy f (x0 , y0 ) n’implique

bien sûr pas la dérivabilité de f en (x0 , y0 )

19/09/2022 34 / 71
Proposition
Si la fonction f a des dérivées partielles continues (par rapport à (x , y )) au
voisinage de (x0 , y0 ), alors elle est continûment différentiable au voisinage
(x0 , y0 ) et
Df (x0 , y0 ) (h, w ) = ∂x f (x0 , y0 ) h+∂y f (x0 , y0 ) w , pourtouth ∈ X , w ∈ Y
Définition
soit f une application différentiable X → Y . Si l’application x → Df (x )
est dérivable pour un certain x ∈ X , on appelle dérivée seconde et on la
note D 2 f (x ). Par définition de la dérivée, on a donc
Df (x + h) = Df (x ) + D 2 f (x )h + o(∥h}
Puisque Df (x ) ∈ L(X , Y ), on a D 2 f (x ) ∈ L(X , L(X , Y )). On peut

montrer que les espaces L(X , L(X , Y )) et L(X × X ; Y ) sont isométriques.
Dans la suite on identifiera donc la dérivée seconde de f à une application
bilinéaire X × X → Y .
19/09/2022 35 / 71
Lemme(Schwarz)
Soit f différentiable X → Y , telle que D 2 f (x0 ) existe. Alors l’application
bilinéaire (h1 , h2 ) → D 2 f (x0 ) (h1 , h2 ) est symétrique. Autrement dit,
D 2 f (x0 ) (h1 , h2 ) = D 2 f (x0 ) (h2 , h1 ) , ∀h1 , h2 ∈ X .
Lemme
Sous les hypothèses du lemme précédent on a
1
f (x0 + h) = f (x0 ) + Df (x0 ) h + D 2 f (x0 ) (h, h) + o ∥h∥2
2

19/09/2022 36 / 71
Espaces Euclidiens
Soit Rn , muni du produit scalaire standard et de la b.o.n. canonique

{e1 , . . . , en } : ⟨x , y ⟩ = x t y en identifiant x et X .
Soit Ω un ouvert de Rn et f : Ω → Rm . Soit a ∈ Ω et v ∈ Rn , la dérivée

de f au point a, dans la direction v , est définie par
1
∂v f (a) = lim (f (a + hv ) − f (a)) (h ∈ R).
h→0 h
Si v = ei , on obtient la dérivée partielle de f par rapport à la i i e variable,

notée, ∂i f (a) ∈ Rm .
∂f
Si m = 1, f : Ω → R, on note aussi ∂i f (a) = ∂x i
(a).

19/09/2022 37 / 71
Définition
Soit Ω un ouvert de Rn et f : Ω → Rm . On dit que f est différentiable en
a ∈ Ω s’il existe une application linéaire L ∈ L (Rn , Rm ) qui vérifie
∥f (a + u) − f (a) − L(u)∥ = o(∥u∥) (u ∈ Rn ) .
On note L = da f la différentielle de f en a et Df (a) ∈ M(m, n) la matrice

associée est appelée matrice jacobienne.

19/09/2022 38 / 71
Proposition
Soit Ω un ouvert de Rn et f : Ω → Rm différentiable au point a ∈ Ω, alors
pour tout v ∈ Rn :
∂v f (a) = da f (v ) = Df (a)v .
 ∂f1 ∂f1 ∂f1 
∂x (a) ∂x2 (a) ... ∂xn (a)
 ∂f21 ∂f2 ∂f2
 ∂x1 (a) ∂x2 (a) ... ∂xn (a)


Df (a) =  .. .. .. 
. . .
 
 
∂fm ∂fm ∂fm
∂x1 (a) ∂x2 (a) . . . ∂xn (a)

∂f ∂f
Si m = 1, f : Ω → R , on a :Df (a) = ∂x1 (a) ··· ∂xn (a) .
Remarque
la réciproque est fausse, il existe des fonctions pour lesquelles toutes les
dérivées directionnelles existent et qui ne sont pas différentiables.

19/09/2022 39 / 71
Proposition
Soit Ω un ouvert de Rn et f : Ω → R différentiable au point a ∈ Ω, alors
pour tout v ∈ Rn :
n
X ∂f
∂v f (a) = vi (a) = ⟨∇f (a), v ⟩ = ∇f (a)t v
i=1
∂xi
 ∂f 
(a)
t
 ∂x1. 
où ∇f (a) = (Df (a)) = 
 ..  est le gradient de f au point a.

∂f
∂xn (a)

19/09/2022 40 / 71
Application
Soit a ∈ Rn , f : Rn → R différentiable en a, on a
∀v ∈ Rn , ∥v ∥2 = 1 : |∂v f (a)| ≤ ∥∇f (a)∥2
et
−∇f (a)
min ∂v f (a) = −∥∇f (a)∥2 et est atteint en v =
∥v ∥2 =1 ∥∇f (a)∥2
+∇f (a)
max ∂v f (a) = +∥∇f (a)∥2 et est atteint en v = .
∥v ∥2 =1 ∥∇f (a)∥2

19/09/2022 41 / 71
Application
Au point a, la direction de la plus forte croissance de f est donnée par
+∇f (a) et la direction de la plus forte descente est donnée par −∇f (a).
D’où les algorithmes de minimisation dits de "descente de gradient.
Dans la direction ±(∇f (a))⊥ , ∂v f (a) = 0, on reste à la. même cote.
On dit aussi que le gradient est perpendiculaire aux lignes de niveau

Lf (α) = {x ∈ Rn /f (x ) = α}. Si ∇f (a) = 0, a est un point critique et
localement la fonction est plate.

19/09/2022 42 / 71
Proposition
Soit Ω un ouvert de Rn , f : Ω → Rm et a ∈ Ω. Si au point a toutes les
dérivées partielles ∂i f (a), 1 ≤ i ≤ n , existent et si les fonctions x 7→
∂i f (x ) 1 ≤ i ≤ n , sont continues dans un voisinage de a, alors f est
différentiable en a.
On dit que f est continûment différentiable, f ∈ C 1 (Ω, Rm ), si on a la
continuité des dérivées partielles en tout point de l’ouvert Ω.
Dans la, suite, on va considérer des fonctions suffisamment régulières,

c.-àr-d. de classe C1 ou C 2 , ainsi ne se posera plus la question de
différentiabilité.

19/09/2022 43 / 71
Proposition
Soient f : Rn → Rm , g : Rm → Rp des fonctions différentiables. On pose
h = g ◦ f , alors h : Rn → Rp est differentiable et, pour tout a ∈ Rn :
da h = df (a) g ◦ da f
∂1 h1 (a) . . . ∂n h1 (a)
 
 .. ..
=

 . .
∂1 hp (a) . . . ∂n hp (a)
∂1 g1 (f (a)) . . . ∂m g1 (f (a)) ∂1 f1 (a) . . . ∂n f1 (a)
  
 .. ..   .. .. 
 . .  . . 
∂1 gp (f (a)) . . . ∂m gp (f (a)) ∂1 fm (a) . . . ∂n fm (a)

19/09/2022 44 / 71
Exemple
Si n = p = 1, h(a) = g (f1 (a), . . . , fm (a)) ∈ R, a ∈ R et
m
h′ (a) = ∂i g(f (a))fi ′ (a).
X
i=1
Proposition
Soit Ω un ouvert de Rn , f : Ω → R et a ∈ Ω et on suppose que
f ∈ C 2 (Ω, R). La différentielle d’ordre 2, da2 f est une forme bilinéaire
symétrique, dont la matrice s’écrit
 
∂11 f (a) ∂12 f (a) . . . ∂1nf f (a)
!

 ∂21 f (a) ∂22 f (a) . . . ∂2nf f (a) 
 ∂2f
Hf (a) =  .. .. .. = (a) .

 . . .

 ∂xi ∂xj 1≤,i,n≤n
∂n1 f (a) ∂n2 f (a) . . . ∂nna f (a)
C’est la matrice hessienne de f . On a pour

h, k ∈ Rn : d 2 fa (h, k) = ht Hf (a)k
19/09/2022 45 / 71
Proposition( Formule de Taylor à l’ordre 2
Soit Ω un ouvert de Rn , | f : Ω → R et a ∈ Ω. On suppose que
f ∈ C 2 Ω, R2 , alors

1
f (a + h) = f (a) + da f (h) + da2 f (h, h) + o ∥h∥2
2
1
= f (a) + (∇f (a))t h + ht Hf (a)h + o ∥h∥2 (h ∈ Rn ) .
2
Cas particulier : f : R2 → R, a = (a1 , a2 ) et h = (h1 , h2 ) :
∂f ∂f
f (a1 + h1 , a2 + h2 ) = f (a1 , a2 ) + f (a)h1 + f (a)h2
∂x1 ∂x2
1 ∂2f 2 1 ∂2f
+ (a)h 1 + (a)h22
2 ∂x1 2 2 ∂x2 2
∂2f
+ (a)h1 h2 + o h12 + h22 .
∂x1 ∂x2

19/09/2022 46 / 71
Cas Hilbertien
On introduit de même les notions de gradient et hessien dans le cas d’un

espace de Hilbert.
Si X est un espace de Hilbert, d’après le théorème de Riesz , toute forme
linéaire continue sur X coïncide avec un produit scalaire.
Définition
Soit X un espace de Hilbert et f : X → R. Si f est G-dérivable en un
point x , on appelle gradient de f en x , et on note ∇f (x ), l’unique élément
de X telque
Df (x )h = (∇f (x ), h), pour tout h ∈ X.

19/09/2022 47 / 71
Définition
Soit X un espace de Hilbert et f : X → R. Si f est deux fois dérivable en
un point x , on appelle hessien de f en x , et on note ∇2 f (x ), l’élément de
L(X , R) tel que

D 2 f (x )(h, h) = ∇2 f (x )h, h , pour tout h ∈ X.

19/09/2022 48 / 71
Formules de Taylor
Taylor Mac-Laurin ordre 1
Si f : X 7→ R est définie et continue sur [u, v ], différentiable sur ]u, v [, il
existe θ ∈]0, 1[ tel que
f (v ) = f (u) + f ′ (u + θ(v − u)) · (v − u)
On l’appelle aussi la formule de la moyenne, et on peut la formuler ainsi il

existe w ∈]u, v [ tel que
f (v ) = f (u) + f ′ (w ) · (v − u)
Taylor Mac-Laurin ordre 2

Si f : X → 7 R est définie et continue sur [u, v ], 2 fois différentiable sur
]u, v [, il existe θ ∈]0, 1[ tel que
1
f (v ) = f (u) + f ′ (u) · (v − u) + f ′′ (u + θ(v − u)) · (v − u) · (v − u)
2
19/09/2022 49 / 71
Formules de Taylor
Taylor Young ordre 2

Si f : V 7→ Rp est 2 fois différentiable en u, alors pour tout v
1
f (v ) = f (u) + f ′ (u) · (v − u) + f ′′ (u) · (v − u) · (v − u) + ϵ(v − u)∥v − u∥2
2
avec
lim ϵ(w ) = 0
w →0

19/09/2022 50 / 71
Formule de Taylor avec reste intégral
Si f : V 7→ Rp est de classe C 1 alors pour tout a et h on a :
Z
f ′ (a + th)h dt.

f (a + h) = f (a) +
[0,1]

19/09/2022 51 / 71
Exemples de bases
Les formes linéaires f (u) = (c, u), où c est un vecteur donné dans X .
Alors f ′ (u) = ∇f (u) = c
Les fonctions f (u) = a(u, u), ou a est une forme bilinéaire continue
sur X . Alors f ′ (u).v = a(u, v ) + a(v , u), et si a est symétrique
f ′ (u) · v = 2a(u, v ).

19/09/2022 52 / 71
Convexité
V Espace de Hilbert réel.

∥ · ∥ sa norme et (·, ·) son produit scalaire.
Définition(Ensemble convexe
On dit que l’ensemble K ⊂ V est convexe si
∀(x , y ) ∈ K × K , ∀t ∈ [0, 1] tx + (1 − t)y ∈ K .
Autrement dit, K est convexe s’il contient tout "segment" reliant deux
quelconques de ses points.
Exemples
Un intervalle [a, b] est convexe dans R
Une réunion disjointe d’intervalles de R n’est pas convexe.

19/09/2022 53 / 71
Définition( Fonctions convexes )
On dit que la fonction J : K ⊂ V → R est convexe si K est convexe et si
∀(x , y ) ∈ K × K , ∀t ∈ [0, 1] J(tx + (1 − t)y ) ≤ tJ(x ) + (1 − t)J(y )
Définition( Fonctions strictement convexes )

On dit que la fonction J : K → R est strictement convexe si K est convexe
et si
∀(x , y ) ∈ K ×K avec x ̸= y , ∀t ∈]0, 1[ J(tx +(1−t)y ) < tJ(x )+(1−t)J(y )

19/09/2022 54 / 71
Exemples( Fonctions convexes et strictement convexes )
J(x) = ∥x ∥2 est strictement convexe.
Toute application affine, c’est-à-dire de la forme
J(x ) = (b, x ) + β,
où b et x sont des éléments de V et β ∈ R est convexe mais pas

strictement.
Soit A une matrice carrée symétrique d’ordre n semi-définie positive
et b un vecteur de Rn . Alors J définie par
1
J(x ) = (Ax , x ) − (b, x )
2
est convexe. Si de plus A est définie positive, J est strictement
convexe.

19/09/2022 55 / 71
A est un opérateur linéaire de V (espace de Hilbert) dans V ,
autoadjoint et monotone c’est-à-dire
∀(x , y ) ∈ V × V (A(x ) − A(y ), x − y ) ≥ 0,
et b ∈ V avec J définie par

1
J(x ) = (Ax , x ) − (b, x )
2
est convexe.

19/09/2022 56 / 71
Définition(α convexe )
On dit qu’une fonction f , définie sur un ensemble convexe K , est
fortement convexe (ou α-convexe) s’il existe α > 0 tel que, pour tout
u, v ∈ K et tout θ ∈ [0, 1]
αθ(1 − θ)
f (θu + (1 − θ)v ) ≤ θf (u) + (1 − θ)f (v ) − ∥u − v ∥2 .
2
Evidemment, les fonctions fortement convexes sont également strictement
convexes.
Dans la Définition il est possible de ne tester la forte convexité de f que
pour la valeur θ = 12 ,c.a.d si f est une fonction localement bornée sur un
ensemble convexe K et α > 0 tels que, pour tout u, v ∈ K ,
u+v f (u) + f (v ) α

f ≤ − ∥u − v ∥2 .
2 2 8
alors f est fortement ou α-convexe.

19/09/2022 57 / 71
Théorème(caractérisation des fonctions convexes)
J est convexe sur V si et seulement si l’une des conditions équivalentes
suivantes est vérifiée :
1) Si J est différentiable, le graphe de J est au-dessus de l’hyperplan
tangent, i.e.
∀u, v ∈ V , J(v ) ⩾ J(u) + J ′ (u) · (v − u)
2) Si J est différentiable, J ′ est un opérateur monotone, i.e.
∀u, v ∈ V , J ′ (v ) − J ′ (u) · (v − u) ⩾ 0

3) Si J est deux fois différentiable, J ′′ est un opérateur non négatif,

i.e.
∀u, w ∈ V , J ′′ (u)w .w ⩾ 0

19/09/2022 58 / 71
Preuve
convexe =⇒ (1)
J(θv + (1 − θ)u) ≤ θJ(v ) + (1 − θ)J(u).

Divisons par θ
J(u + θ(v − u)) − J(u)

≤ J(v ) − J(u)
θ
Passons à la limite en θ → 0 :
J ′ (u) · (v − u) ≤ J(v ) − J(u)

19/09/2022 59 / 71
Preuve
(1) =⇒ convexe
On applique l’inégalité (1) successivement aux couples
(θu + (1 − θ)v , u) et (θu + (1 − θ)v , v ) :
×θ J(u) ⩾ J(θu + (1 − θ)v ) + J ′ (θu + (1 − θ)v ) · (1 − θ)(u − v

×(1 − θ) J(v ) ⩾ J(θu + (1 − θ)v ) + J ′ (θu + (1 − θ)v ) · θ(v − u)
Lorsque l’on ajoute ces deux inégalités, les termes de droit se

neutralisent, il ne reste plus que l’inégalité de convexité
θJ(u) + (1 − θ)J(v ) ⩾ J(θu + (1 − θ)v )

19/09/2022 60 / 71
Preuve
(1) =⇒ (2)
Appliquons successivement (1) aux couples (u, v ) et (v , u).
J(v ) ⩾ J(u) + J ′ (u) · (v − u)

J(u) ⩾ J(v ) − J ′ (v ) · (v − u)
et ajoutons les pour obtenir 0 ⩾ (J ′ (u) − J ′ (v )) · (v − u) qui donne le

résultat souhaité en changeant les signes.

19/09/2022 61 / 71
Preuve
(2) =⇒ (3)
Pour tout w dans V , et θ > 0, posons v = u + θw , et appliquons (2)
au couple (u, v ). On obtient
J ′ (u + θw ) − J ′ (u) · w ⩾ 0

ce qui implique
(J ′ (u + θw ) − J ′ (u)) · w
⩾0
θ
Par définition de la différentiabilité de J ′
J ′ (u + θw ) − J ′ (u) = θJ ′′ (u)w + ϵ(θ)∥θw ∥
Remplaçons dans l’inégalité précédente et divisons par θ :
J ′′ (u)w + ε(θ)∥w ∥ · w ⩾ 0

Faisons tendre maintenant θ vers 0 pour obtenir le résultat.

19/09/2022 62 / 71
Preuve
(3) =⇒ (1)
On utilise la formule de Taylor Mac-Laurin à l’ordre 2 et on obtient le
résultat.

19/09/2022 63 / 71
Théorème(caractérisation des fonctions strictement)
Soit J différentiable sur V . J est strictement convexe si et seulement si
l’une des conditions équivalentes suivantes est vérifiée :
(1) ∀u, v ∈ V , u ̸= v , J(v ) > J(u) + J ′ (u) · (v − u)

(2) ∀u, v ∈ V , u ̸= v , J ′ (v ) − J ′ (u) · (v − u) > 0

Si J est deux fois différentiable, et si
(3) ∀u, w ∈ V , w ̸= 0, J ′′ (u)w .w > 0,
alors J elst strictement convexe.

Remarque :
SI on cherche à refaire la démonstration précédente, lorsque l’on utilise un
passage à la limite, les inégalités strictes deviennent des inégalités larges, et
on ne peut pas conclure. C’est le cas pour strictement convexe =⇒ (1)

19/09/2022 64 / 71
Théorèmé(Caractérisation des fonctions α convexes)
J est α - convexe sur V si et seulement si l’une des conditions équivalentes
suivantes est vérifiée :
(1) Si J est différentiable,
α
∀u, v ∈ V , J(v ) ⩾ J(u) + J ′ (u) · (v − u) + ∥v − u∥2
2
(2) Si J est différentiable,
∀u, v ∈ V , J ′ (v ) − J ′ (u) · (v − u) ⩾ α∥v − u∥2

(3) Si J est deux fois différentiable,
∀u, w ∈ V , J ′′ (u)w .w ⩾ α∥w ∥2 .

19/09/2022 65 / 71
Remarque
la première inégalité affirme que J(v ) est au dessus d’une fonction
quadratique en v qui lui est tangente en u.
Le résultat suivant sera essentiel dans l’obtention d’un résultat d’existence

d’un minimum en dimension infinie.
Proposition
Si J est convexe continue sur un ensemble K convexe fermé non vide,
alors il existe une forme linéaire continue L ∈ V ′ et une constante δ ∈ R
telles que
J(v ) ≥ L(v ) + δ ∀v ∈ K
Si de plus J est fortement convexe sur K , alors il existe deux constantes
γ > 0 et η ∈ R telles que
J(v ) ≥ γ∥v ∥2 + η ∀v ∈ K .

19/09/2022 66 / 71
Lemme
Soit J une fonction différentiable de V dans R telle que sa dérivée J ′ est
Lipschitzienne de constante L > 0. Alors
L
J(v ) ≤ J(u) + J ′ (u), v − u + ∥v − u∥2

pour tout v , u ∈ V .
2

19/09/2022 67 / 71
Remarque
Une interprétation du Lemme est qu’une fonction différentiable à dérivée
L-Lipschitzienne peut être majorée par une fonction quadratique qui lui est
tangente au point u.
C’est en quelque sorte une version opposée (majoration au lieu de

minoration) de la Remarque pour une fonction α-convexe différentiable
(notons néanmoins qu’il n’y a pas d’hypothèse de convexité dans le
Lemme ).
Par conséquent, les fonctions fortement convexes à dérivée Lipschitzienne

sont remarquables car elles sont encadrées par deux fonctions quadratiques
qui sont tangentes au point u. Cette propriété très utile sera exploitée dans
les preuves de convergence des algorithmes d’optimisation.

19/09/2022 68 / 71
Preuve
Ecrivons une formule de Taylor avec reste exact
Z 1
J ′ (u + t(v − u)), v − u dt.

J(v ) = J(u) +
0
Par conséquent,
Z 1
J(v ) − J(u) − J ′ (u), v − u ≤
′
J (u + t(v − u)) − J ′ (u) ∥v −u∥dt,

0
d’où la conclusion en utilisant l’hypothèse de Lipschitziannité de J ′ .

19/09/2022 69 / 71
Exemple
les fonctionnelles de la forme J(u) |= a(u, u), où a est une forme bilinéaire
symétrique continue sur V sont α-convexes si et seulement si
∀u ∈ V , 2a(w , w ) ⩾ α∥w ∥2
Si l’on est dans Rn , avec J(u) = 21 (Au, u), ceci revient à
∀w ∈ V , (Aw , w ) ⩾ α∥w ∥2
La matrice A étant symétrique, elle diagonalise en base orthonormée,

A = PDP T , où D est la matrice des valeurs propres di et P la matrice des
vecteurs propres. On a alors

19/09/2022 70 / 71
n n
X
di ((Pw )i )2 ⩾ ((Pw )i )2
X
(Aw , w ) = min di
1≤i≤n
i=1 i=1

(Aw , w ) ⩾ min di ∥Pw ∥2 = min di ∥w ∥2
1≤i≤n 1≤i≤n
car, puisque P est orthogonale, ∥Pw ∥ = ∥w ∥.
Si A est définie positive, la fonctionnelle J est min1≤i≤n di -convexe.

19/09/2022 71 / 71

Ch1 Outil Optim ECC Sept22

Transféré par

Droits d'auteur :

Formats disponibles

Ch1 Outil Optim ECC Sept22

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Ch1 Outil Optim ECC Sept22

Transféré par

Droits d'auteur :

Formats disponibles

Outils Mathématiques en Optimisation differentielle

Laboratory of Applied Mathematics and Computer Science

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

Definition de l’optimisation : Choisir parmi plusieurs possibilités une

Transports : trafic aérien, ferroviaire, routier

Domaines millitaire : Couverture radar, réactivité d’intervention,

Sciences dures : Physique, chimie, informatique, automatique,

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

Principales notion : Espace de Hilbert, Differentiabilité, Convexité...

Résultats théoriques : Existence de solution et Unicité

Conditions d’optimalité : Problèmes sans contraintes, Problèmes avec

Algorithmes : Gradient de décentes et ses variantes, Méthode de

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

Forme Abstraite d’un problème d’optimisation

Formulation Mathématique de problème

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

Est-ce que l’on peut caractériser x ∗ ? c.à.d. peut-on trouver des

Trouver un algorithme d’optimisation pour déterminer la, resp. les,

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

la structure de E : espace vectoriel, muni d’une norme, d’un produit

les propriétés de K ⊂ E : fermé, borné, convexe, compacte...

les propriétés de J : E −→ R : continuité, différentiabilité, coercivité,

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

On pourrait croire que non :

Néanmoins, la dimension infinie est essentielle :

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

L’optimisation se scinde essentiellement en deux disciplines dont les outils

Si K est discret (K ⊂ Z n , fini ou dénombrable),on parle

Si K est continue, et J est continue, on parle d’optimisation continue.

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

Résolution d’un système matriciel.

A une matrice symétrique N × N définie positive

La solution du système linéaire Ax = b est donnée par le point de

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

Problèmes de moindre carré :

b ∈ Rp les données du problème

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

Première valeur propre

A une matrice carré d’ordre n, symétrique

où ∥x ∥ est la norme euclidienne de x .

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

Notion en thérmodynamique, physique statistique et théorie de

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

Minimisation d’une énergie mécanique

Minimisation de l’energie mécanique d’une membrane ou bien l’energie

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

Traitement des images

où ℓ > 0 est un paramètre qui permet de moduler le lissage.

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

où w ∈ Rd et τ ∈ R sont des paramètres à optimiser.

sgn (hw ,τ (xi )) ≈ yi

(FSTG) Outils Mathématiques en Optimisation differentielle convexe

X , Y et Z trois espaces de Banach

Les conditions d’existence d’optima locaux : Les dérivées d’ordre un

Développement d’un formalisme général pour la notion de dérivation.

Le cas particulier d’espaces X et Y tels que X = Rn et Y = Rm .