Calcul Différentiel et Optimisation 2023
Calcul Différentiel et Optimisation 2023
OPTIMISATION
ET
CALCUL DIFFERENTIEL
Amaury Freslon
2023 – 2024
AVANT-PROPOS
• Enfin, on trouve facilement sur internet de très nombreuses notes de cours sur
les sujets traités ici. Nous nous sommes appuyés sur certaines dont il serait mal-
heureusement trop long de citer tous les auteurs.
Mentionnons pour conclure que les figures planes de ce texte ont été réalisées avec
GeoGebra et que les images de surfaces sont issues de 3D-XplorMath.
Table des matières
3.2 Inégalités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.2.1 Plus fort que Lagrange . . . . . . . . . . . . . . . . . . . . . . . . 84
3.2.2 Une page de publicité . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.2.3 Qualification linéaire des contraintes . . . . . . . . . . . . . . . . 93
3.3 Le cas linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.3.1 Le KKT amélioré . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.3.2 La méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . 98
TABLE DES MATIÈRES 3.4 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.4.1 Le Lagrangien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.4.2 Dualité linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
– viii –
Chapitre 1. Introduction
Le cadre étant posé, nous allons maintenant présenter plusieurs problèmes d’opti-
misation issus de domaines différents. L’objectif est double. D’une part, nous voulons
montrer que l’optimisation est omniprésente et qu’il est donc pertinent, voire indis-
pensable, de savoir gérer ces questions, et d’autre part, nous voulons introduire diffé-
rents types de problèmes d’optimisation qui nécessiteront des techniques différentes
ou plus ou moins élaborées, afin de motiver la suite de ce texte.
CHAPITRE 1
1.1 Deux problèmes élémentaires
INTRODUCTION S’il n’y a pas de solution, c’est qu’il n’y a pas de problème.
J. Rouxel, Les Shadocks
– 2 –
1.1. Deux problèmes élémentaires Chapitre 1. Introduction
Nous avons ainsi résolu le problème de l’abeille et trouvé le temps optimal à passer sur
chaque fleur pour que le rendement soit le meilleur possible, à savoir
√
topt = ατ
Remarque 1.1.1. On remarquera que le temps optimal ne dépend pas de β. Ceci est
assez logique, puisqu’on a supposé que ce nombre était le même pour toutes les fleurs.
Ceci est évidemment un cadre simplifié. En particulier, nous ne considérons qu’une
seule variable, à savoir le temps. Pour rendre le modèle plus réaliste, on pourrait faire
varier les coefficients α et β en fonction de la fleur. Où alors, on pourrait prendre pour
N (t) une fonction plus compliquée. Pour ce qui nous concerne, peu importe. L’essentiel
est de retenir les deux point suivants :
L’abeille doit donc résoudre le problème d’optimisation suivant : pour quelle valeur de t 1.1.2 Une histoire de camions
la fonction f est-elle maximale ?
Voici un second exemple qui, quoique simpliste dans sa formulation, illustre bien
On le sait, pour trouver le maximum d’une fonction il faut commencer par savoir le genre de questions que la logistique peut poser. Une entreprise effectuant de gros
où sa dérivée s’annule. Ici, on a chantiers possède deux dépôts D1 et D2 où sont rangés ses camions, à raison de 8
camion dans D1 et 6 camions dans D2 . Elle doit effectuer simultanément deux chantiers
β(t + τ)(t + α) − βt(2t + τ + α)
f ′ (t) = T C1 et C2 situés à des distance des dépôts indiquées sur le schéma suivant :
(t + τ)2 (t + α)2
2
−βt + βατ
=T
(t + τ)2 (t + α)2
β(ατ − t 2 )
=T .
(t + τ)2 (t + α)2
Comme
√ on ne considère que des valeurs positives de t, cette fonction ne s’annule qu’en
t = ατ. On en déduit le tableau de variations
√
t 0 ατ +∞
fmax
f (t)
0 0
– 3 – – 4 –
1.1. Deux problèmes élémentaires Chapitre 1. Introduction
f (x1 , 0, 0, 0) −→ +∞
x1 →+∞
f (x1 , 0, 0, 0) −→ −∞
x1 →−∞
Mais on ne veut pas minimiser la fonction f sur R4 , on veut la minimiser sur une partie Nous sommes ici face à un problème plus difficile que le précédent. Pas tant parce
de R4 vérifiant les contraintes suivantes : qu’il a deux variables, mais à cause des contraintes. En effet, rien ne sert a priori de
chercher des points où les “dérivées partielles 4 ” de F s’annulent, puisqu’elles sont
constantes. Il faudra faire intervenir d’une façon ou d’une autre les contraintes pour
x1 , x2 , x3 , x4 ⩾ 0 résoudre ce problème. Ceci fera l’objet du chapitre 3, mais nous pouvons déjà faire
x1 + x2 ⩽ 8 quelques remarques importantes :
x3 + x4 ⩽ 6
x1 + x3 = 4 • Il faudrait déjà savoir si le minimum que nous cherchons existe bien. C’est le
cas pour une raison topologique : la zone hachurée délimitée par les contraintes
x2 + x4 = 7
est un compact de R2 . Comme F est continue, elle admet un maximum et un
minimum sur ce compact.
On peut remarquer que les deux dernières égalités permettent de réduire le nombre • Si le minimum était atteint à l’intérieur de la zone hachurée, alors on aurait un
de variables du problème à deux, par exemple x1 et x2 . On cherche alors à minimiser minimum local. Il est facile de se convaincre que comme F est affine, elle n’a pas
de tel minimum local. Ainsi, le point que nous recherchons est sur le bord.
F : (x1 , x2 ) 7→ 4x1 + 5x2 + 41 • Le bord peut se décomposer en cinq segments. Sur chacun de ces segments, soit
x1 est constante, soit on peut exprimer x2 en fonction de x1 , de sorte qu’on se
ramène à chercher à chaque fois le minimum d’une fonction d’une variable, ce
avec les contraintes qui peut se faire à l’aide d’un tableau de variations.
Les contraintes définissent une zone du plan qu’on peut dessiner : 4. Quel que soit le sens de cette expression, que nous définirons bientôt (voir Paragraphe 2.2.1).
– 5 – – 6 –
1.2. Les petites cellules grises Chapitre 1. Introduction
Remarquons que, de façon peu intuitive, cette solution optimale fait emprunter le fonction d’activation ϕ. Idéalement, ϕ est la fonction de Heaviside 8 – aussi connue
trajet le plus long à 4 camions. Notons aussi que si le problème peut être résolu à la sous le nom de “fonction créneau” – c’est-à-dire que
main – bien que nous ne l’ayons pas fait – c’est parce qu’il a une forme relativement (
simple : la fonction à minimiser est affine. On parle dans ce cas d’optimisation linéaire 1 si x ⩾ 0
ϕ(x) =
ou parfois de programmation linéaire 5 . La première approche générale de l’optimisa- 0 si x > 0
tion linéaire a été développée par Kantorovich 6 en 1939 dans le cadre de travaux en
économie. Ces travaux lui valurent le Prix de la Banque de Suède en sciences écono- Un tel neurone peut être utilisé comme une sorte de “porte logique” pour effectuer
miques en mémoire d’Alfred Nobel – généralement appelé improprement Prix Nobel une tâche simple. Par exemple, imaginons que nous voulions fabriquer un neurone qui
d’économie – en 1975, partagé avec Koopmans 7 qui avait travaillé sur le même su- permette de distinguer les ronds des carrés dans la grille ci-dessous.
jet de façon indépendante à la même époque. Nous aborderons quelques aspects de
l’optimisation linéaire au Paragraphe 3.3.
• Un neurone est une cellule excitable : sous certaines conditions, elle émettra elle-
même des impulsions électriques en réponse au stimulus. On remarque que la droite d’équation 2x + 5y = 2 sépare le plan en deux demi-plans
qui ne contiennent chacun qu’un type de point :
Ces deux aspects ont conduit les informaticiens à modéliser un neurone comme une
composée de deux fonctions. Plus précisément, un neurone (parfois appelé perceptron)
est un objet prenant en entrée un vecteur à n coordonnées et produisant en sortie un
nombre selon la procédure suivante :
Ici, les coefficients (ai )1⩽i⩽n ne dépendent que du neurone et a0 est appelé le biais.
Cette opération est la partie affine.
2. Le résultat produit par la partie affine est ensuite utilisé comme argument d’une
5. Ce terme n’a rien à voir avec l’informatique mais traduit le fait qu’on cherche à résoudre ce qu’on
appelle parfois un programme d’optimisation linéaire. Cette terminologie est cependant de moins en
moins usitée. 8. Oliver Heaviside (1850–1925) : Physicien et mathématicien autodidacte, il s’est beaucoup intéressé
6. Leonid Kantorovich (1912–1986) : Mathématicien et économiste russe, qui a contribué de façon à l’étude mathématique des circuits électriques. Outre la définition de la fonction qui porte son nom,
importante à l’analyse fonctionnelle et à la théorie de l’optimisation. on lui doit l’idée d’utiliser les nombres complexes (notamment l’impédance) pour l’étude des circuits
7. Tjalling Koopmans (1910–1985) : Mathématicien et économiste néerlando-américain qui s’est électriques. C’est aussi lui qui a donné aux Équations de Maxwell leur forme la plus courante en
beaucoup intéressé à l’optimisation en économie, appliquée à l’établissement des prix et l’allocation utilisant des opérateurs vectoriels (Maxwell avait encore huit équations au lieu des quatre couramment
des ressources. enseignées aujourd’hui).
– 7 – – 8 –
1.2. Les petites cellules grises Chapitre 1. Introduction
Or, appartenir à un demi-plan, c’est vérifier une inégalité du type f (x, y) ⩾ 0 avec f
une fonction affine. Ainsi, si la partie affine du neurone est
alors si on donne au neurone les coordonnées d’un point, il renverra 1 si le point est
un rond et 0 si c’est un carré.
Mais en pratique il peut être utile d’avoir à la place de la fonction de Heaviside
une fonction plus régulière qui “ressemble” à un créneau. On parle alors de fonction
sigmoïde, et en voici un exemple :
– 9 – – 10 –
1.3. Le juste prix Chapitre 1. Introduction
1.3 Le juste prix correspond à un service, alors elle est négative. À la i-ème commodité est associé un
prix pi , de sorte que le prix total d’un élément x ∈ Rn est
Les politiques grecs ne reconnaissent d’autre force que celle de la vertu. n
X
Ceux d’aujourd’hui ne vous parlent que de manufactures,
de commerce, de finances, de richesses et de luxe même. pi xi = ⟨p, x⟩.
Montesqieu, De l’esprit des lois (1748) i=1
Pour échanger des biens, il faut les produire. On considère donc des unités de pro-
Nous allons maintenant présenter un autre type de problème d’optimisation, cette
ductions qui sont chacune décrites par une partie Y ⊂ Rn . Chaque élément de Y repré-
fois dans le domaine de l’économie. L’un des problèmes fondamentaux de l’économé-
sente un plan de production : les coordonnées positives sont les biens qu’on produit et
trie est celle de l’équilibre entre l’offre et la demande. Pour simplifier, considérons un
les composantes négatives sont ceux que l’on consomme. Les hypothèse générales sur
marché isolé, c’est-à-dire un ensemble d’agents qui vendent ou achètent un unique
le fonctionnement économique du système se traduisent en conditions sur les unités
bien. Il y a une certaine quantité de biens disponibles – c’est l’offre – et les acheteurs
de production, à savoir : si Y1 , · · · , Ym désignent les m unités de production du marché,
désirent acquérir une autre quantité du même bien – c’est la demande. Ces deux quan-
alors
tités dépendent du prix du bien : s’il est très cher, il y aura moins de demande et donc
beaucoup d’offre puisque les stocks s’écouleront mal. On modélise le problème par
deux fonctions, l’une décrivant l’offre 10 S(p) en fonction du prix, et l’autre décrivant • Si y ∈ Yj et t ∈ [0; 1], alors ty ∈ Yj , pour tout 1 ⩽ j ⩽ m. Cela signifie qu’on peut
la demande D(p). Un prix d’équilibre est une valeur e p qui vérifie l’égalité réaliser des changements d’échelles décroissants des plans de production : si on divise
tous les moyens, on produit alors les mêmes biens mais en quantité divisée par le
p) = D(e
S(e p). même facteur. Cela signifie aussi que 0 ∈ Yj de sorte qu’il est possible de ne rien
produire.
Dans notre exemple, les fonctions S et D ont souvent la forme ci-dessous, qui rend
l’existence d’un prix d’équilibre assez intuitive. • Pour tout 1 ⩽ j ⩽ m, si y, y ′ ∈ Yj , alors y +y ′ ∈ Yj . En effet, si l’on peut produire cer-
tains biens en consommant certaines ressources, alors en consommant la somme
des ressources on peut produire la somme des biens. On remarquera que cette
hypothèse peut poser questions : n’y a-t-il pas de limites absolues aux quanti-
tés qu’on peut produire (capacité de production des usines, capacité de stockage,
disponibilité des matières premières) ?
• Soit
m
X n o
Y= Yj = y1 + · · · + ym | yj ∈ Yj pour tout 1 ⩽ j ⩽ m ,
i=1
alors Y ne contient aucun élément dont toutes les composantes soit strictement
positives. En effet, on pourrait alors produire sans rien consommer.
• On a Y ∩ (−Y ) = {0}. Cela signifie que l’économie n’est pas réversible : s’il est
possible de produire globalement des commodités en en consommant d’autres, il
n’est pas possible de faire exactement l’inverse.
Remarque 1.3.1. Les deux premières hypothèses peuvent se résumer dans l’assertion
suivante : Yj est un cône convexe de sommet 0.
Mais pour que le marché fonctionne, il faut surtout des consommateurs. Chacun est
décrit par une partie X ⊂ Rn qui représente les souhaits du consommateur, c’est-à-dire
les paniers qu’il aimerait détenir. Pour comparer ces différents souhaits, on dispose
d’une fonction d’utilité
Le problème de l’équilibre global consiste à étendre les considérations précédentes u : X → R+
à des marchés plus complexes sur lesquels plusieurs biens sont échangés. Plus préci-
telle que u(x′ ) > u(x) si le consommateur préfère le panier x′ au panier x. Ces parties
sément, on considère un marché global constitué d’un nombre fini n de commodités,
satisfont certaines hypothèses :
qui peuvent être de deux natures : les biens ou les services (par exemple du travail).
À chaque agent du système correspond un vecteur x ∈ Rn , son panier, dont les coor-
• X est convexe, fermée et minorée au sens où il existe x0 tel que x ⩾ x0 (au sens où
données correspondent à la quantité de chaque bien qu’il possède. Si une coordonnée
l’inégalité est vérifiée pour chaque coordonnée) pour tout x ∈ X. Cette dernière
10. Notée S à cause du mot supply en anglais, mais aussi parce que O est une notation peu pratique. condition signifie que tout le monde a un minimum d’exigences.
– 11 – – 12 –
1.3. Le juste prix Chapitre 1. Introduction
• Pour tout x ∈ X, il existe x′ ∈ X tel que u(x′ ) > u(x). Autrement dit, on n’en veut admet un maximum en un point yej .
toujours plus : il n’y a pas de satiété du consommateur.
• Pour tout 1 ⩽ i ⩽ ℓ la fonction uj admet un maximum en un point e
xj sous la
• La fonction u est convexe (voir le Chapitre 4). contrainte
m
X
Enfin, pour éviter que la monnaie ne s’épuise, il faut que les unités de production ⟨e p , ζi ⟩ +
p, x⟩ ⩽ ⟨e αij ⟨e
p, yej ⟩
profitent d’une manière ou d’une autre aux consommateurs. Ceci est incarné par des j=1
nombres αX,Y ∈ [0; 1] représentant la fraction de dividendes de l’unité de production Y
que touche le consommateur X. On doit bien sûr avoir
• L’état du marché satisfait l’équilibre de l’offre et de la demande :
X
αX,Y = 1
X ℓ m ℓ
X X X
pour toute unité de production Y . Il est important de remarquer que ce cadre signi- xi − yj − ζi ⩽ 0.
fie que nous sommes dans une économie fictive entièrement capitaliste : les moyens i=1 j=1 i=1
de productions appartiennent entièrement aux agents qui en touchent donc des divi-
dendes. • L’état du marché satisfait la Loi de Walras
On considère un marché global avec des unités de production Y1 , · · · , Ym et des ℓ
X m
X ℓ
X
consommateurs (X1 , u1 ), · · · , (Xℓ , uℓ ) vérifiant toutes les hypothèses ci-dessus. Un état ⟨p, xi ⟩ − ⟨p, yj ⟩ − ⟨p, ζi ⟩ = 0.
du marché est donné par i=1 j=1 i=1
(x1 , · · · , xℓ , y1 , · · · , ym , p),
où les ℓ + m premières coordonnées désignent l’état des acteurs et p ∈ Rn+ désigne
l’ensemble des prix des commodités. Pour pouvoir lancer la machine économique, il Remarque 1.3.3. La Loi de Walras exprime une contrainte budgétaire globale du mar-
faut que les consommateurs puissent initialement s’appauvrir. On suppose que pour ché et est un aspect essentiel de cette approche du problème. En particulier, elle signi-
chaque 1 ⩽ j ⩽ ℓ, le consommateur correspondant démarre avec un panier ζi pour fie que les prix des commodités ne dépendent que du marché lui-même, et pas d’autres
lequel il existe x ∈ Xi vérifiant xi < ζi . biens auxquels les agents n’auraient pas accès.
L’existence d’un prix pour lequel l’ensemble du marché est à l’équilibre est un sujet La preuve de ce résultat d’optimisation est loin d’être facile 14 et sort du cadre de
de réflexion pour les économistes depuis que le cadre précédent a été pour la pre- ce cours (on pourra par exemple consulter [3] pour un exposé complet). D’ailleurs, on
mière fois posé (quoique pas en ces termes) par Walras 11 au XIXe siècle. Cependant, remarquera qu’aucune hypothèse de régularité n’a été faite sur les fonctions, ce qui
la rigueur mathématique n’était pas toujours au rendez-vous : Walras considérait par prévient a priori tout recourt au calcul différentiel. Ceci n’est toutefois qu’apparent, et
exemple qu’un système comportant autant d’équations que d’inconnues possède né- on peut démontrer ce théorème et bien d’autres du même type en utilisant le calcul
cessairement une unique solution. Or, nous savons que ceci n’est même pas vrai quand différentiel, comme illustré dans [10].
le système est linéaire ... L’un de résultats les plus importants dans le domaine fut
Notons enfin que notre description du marché fait appel à une hypothèse très im-
obtenu en par Arrow 12 et Debreu 13 .
portante dans les problèmes d’optimisation, à savoir la convexité. Le fait que les fonc-
Théorème 1.3.2 (Arrow-Debreu) Sous les hypothèses précédentes, il existe un tions d’utilités ui soient convexes est un point essentiel et la preuve ne fonctionne
p ∈ Rn tel que
prix e plus sans elle ! La justification micro-économique de cette hypothèse est donc essen-
tielle pour assurer sa pertinence. Profitons-en pour ajouter que l’étude des fonctions
• Pour tout 1 ⩽ j ⩽ m, la fonction convexes est un domaine riche et important des mathématiques. En fait, beaucoup de
résultat d’optimisation que nous allons voir sont encore vrais pour des fonctions qui
y ∈ Yj 7→ ⟨e
p, y⟩ ne sont pas différentiables, pour peu qu’elles soient convexes. L’un des raisons princi-
pales de ce phénomène est que les fonctions convexes sont en sens toujours “presque
différentiables”.
11. Léon Walras (1834–1910) : économiste français, il est l’un des premiers à s’intéresser aux pro-
blèmes d’équilibre en économie et à tenter de les formaliser, sans pour autant être en mesure de dé- Remarque 1.3.4. On pourra aussi remarquer que toutes les équations intervenant dans
terminer leur existence. On lui doit aussi une métaphore qui a fait florès en économie, le tâtonnement le modèle ci-dessus sont homogènes de degré 1, c’est-à-dire que si on multiplie toutes
Walrassien. les variables par un scalaire λ, alors les relations sont multipliées par λ dans chaque
12. Kenneth J. Arrow (1921–2017) : économiste américain, considéré comme l’un des fondateurs de
l’école néoclassique. Outre ses travaux sur la théorie de l’équilibre général, il a également donné une ver-
membre. En particulier, cela veut dire qu’on peut toujours décider de normaliser une
sion rigoureuse et générale du Paradoxe de Condorcet, aujourd’hui connu sous le nome de Théorème partie des variables. En général, on suppose donc que la somme des prix vaut 1.
d’impossibilité d’Arrow.
13. Gérard Debreu (1921–2004) : mathématicien et économiste français. Il a apporté ses compétences
mathématiques à plusieurs domaines de l’analyse économique et a contribué à les développer en impor- 14. Elle a valu le Prix de la Banque de Suède en sciences économiques en mémoire d’Alfred Nobel
tant les techniques modernes, notamment d’analyse convexe. à ses auteurs.
– 13 – – 14 –
1.4. Thème et variations Chapitre 1. Introduction
1.4 Thème et variations utilise une méthode analytique inspirée de ses travaux sur la détermination des maxima
et des minima : le calcul différentiel naît ici de l’optimisation ! Dans cette méthode dite
d’adégalisation (terme qu’il emprunte à Diophante 19 ), on part de f (x+e), auquel on re-
tranche ensuite f (x). On observe (par exemple dans le cas d’une fonction polynomiale)
qu’on parvient alors à factoriser e. En le simplifiant et en posant e = 0, on obtient la
Nous avons mentionné plusieurs problèmes d’optimisation, et tenté de suggérer la
pente de la tangente ! Comme on le voit, ceci revient à calculer la limite du taux d’ac-
façon dont les outils connus pour les fonctions d’une variable pourraient être éten-
croissement dans le cas simple où ce dernier est continu en 0.
dus pour les étudier. Ce n’est pas la seule méthode, comme nous l’avons évoqué pour
le Théorème 1.3.2, mais c’en est une redoutablement efficace quand elle s’applique. Mais la concurrence est rude à l’époque et Descartes 20 engage une polémique vio-
Avant de la décrire dans les chapitres qui suivent, nous aimerions revenir sur ce calcul lente avec Fermat sur la paternité de la méthode. Vers la même époque, un autre
différentiel en donnant quelques éléments de son histoire. mathématicien, Barrow 21 , fait une contribution importante en remarquant par des
raisonnements géométriques que le problème des tangentes et le problème de la qua-
drature sont inverses l’un de l’autre, mais sans parvenir à en tirer pleinement parti.
1.4.1 Une brève histoire du calcul différentiel
C’est finalement avec une nouvelle polémique entre deux autres grandes figures
Il est difficile de distinguer dans l’histoire des mathématiques l’origine d’une idée que se jouera l’élaboration du calcul différentiel tel que nous le connaissons aujour-
ou d’une théorie particulière parmi toutes les tentatives plus ou moins fructueuses. d’hui. En effet, dans la même période, Newton 22 et Leibniz 23 développent un cadre
En ce qui concerne le calcul différentiel, on peut néanmoins mentionner un problème théorique qui permet de réorganiser tous les résultats précédents et de donner des mé-
mathématique proche qui a intéressé les mathématiciens pendant longtemps : le pro- thodes algorithmiques générales et efficaces pour calculer les tangentes ou les aires,
blème de la quadrature. Il s’agit de calculer l’aire d’une partie du plan délimité par une tout en mettant en évidence la réciprocité des deux opérations. La querelle de priorité
ou plusieurs courbes, c’est-à-dire de l’exprimer en termes de “carrés” dont le côté fait entre les deux personnages, dans laquelle se sont engagés nombres de scientifiques de
une unité de longueur, d’où le nom. En langage moderne, cela revient essentiellement l’époque, est un problème historique complexe que nous n’aborderons pas. Disons sim-
à calculer des intégrales. Pour ce faire, on est assez naturellement mené à considérer plement que du point de vue du vocabulaire et des notations, c’est finalement Leibniz
des limites ou des quantités “infiniment petites”, comme le fameux symbole “dx” de qui est passé à la postérité.
l’intégration le rappelle. On voit donc que le problème de la quadrature mène à des
questions qui sont au fondement du calcul différentiel.
1.4.2 Du calcul différentiel à l’optimisation
De nombreuses techniques ont été élaborées pour aborder le problème de la qua-
drature. Citons en particulier la Méthode d’exhaustion qui consiste à encadrer la par- Nous avons présenté quelques étapes de l’histoire du calcul différentiel au regard
tie du plan à laquelle on s’intéresse par des polygones dont on sait calculer l’aire. Due des deux problèmes mathématiques de la quadrature et des tangentes, mais il ne s’agit
peut-être à Eudoxe 15 , la méthode a été reprise et raffinée par Archimède 16 qui en que d’une des facettes du sujet. En effet, pour établir rigoureusement le calcul différen-
fit un grand usage, d’une part pour le quadrature de la parabole, et d’autre part pour tiel, il a fallut ensuite une bonne notion de limite, qui manquait toujours chez Newton
calculer des approximations du nombre π. Cette méthode a également un intérêt théo- et Leibniz. Cette nécessité n’était pas que mathématique, mais également physique.
rique puisque c’est grâce à elle qu’Euclide 17 démontre que la circonférence du cercle En effet, la mécanique moderne décrit le mouvement des objets à partir de quantités
est proportionnelle au diamètre et qu’Archimède démontre que l’aire du disque est instantanées comme l’accélération ou la vitesse. Si l’on étudie par exemple le mouve-
proportionnelle au carré du diamètre. ment d’un point matériel se déplaçant au cours du temps, il est facile de définir sa
Un second problème mathématique qui a passionné les mathématiciens au tour-
qu’un “grand” théorème qui ne fut démontré que trois siècles après sa mort.
nant du XVIIe est le problème des tangentes. Il s’agit, étant donné une courbe, de dé-
19. Diophante d’Alexandrie (entre le I e et le IV e siècle avant notre ère) : on ne sait pratiquement rien
terminer ses tangentes, c’est-à-dire d’en trouver une description géométrique ou une de la vie de ce mathématicien grec, si ce n’est qu’il a vécu à Alexandrie. On ne possède que des fragments
équation. En langage moderne, ceci consiste essentiellement à calculer le nombre dé- de son œuvre, notamment l’Arithmétique qui a eu une grande influence sur les mathématiques arabes
rivé d’une fonction. Plusieurs mathématiciens développèrent des méthodes plus ou et occidentales, mais dont les marges étaient trop étroites pour que Fermat y écrive la démonstration de
moins rigoureuses et plus ou moins justifiées pour ce faire. En particulier, Fermat 18 son célèbre théorème.
20. René Descartes (1596–1650) : philosophe, mathématicien et physicien français. Il a introduit les
15. Eudoxe de Cnide (408 – 355) : mathématicien, astronome, médecin et philosophe grec, contempo- notations qui portent son nom pour repérer les points dans le plan ou dans l’espace, et a publié des
rain de Platon. ouvrages de mécanique et d’optique. Son œuvre philosophique a eu une postérité au moins égale à son
16. Archimède (287–212) : l’un des plus grands scientifiques de l’antiquité, dont la vie est malheu- œuvre mathématique.
reusement peu connue. Ses travaux en géométrie sont fondateurs sur de nombreux sujets : calculs de 21. Isaac Barrow (1630–1677) : philologue, mathématicien et théologien anglais. Outre ses travaux
longueurs, d’aires et de volumes, courbes paramétrées, coniques. Il a également une œuvre considérable précurseurs pour le calcul différentiel, il est connu pour avoir été le professeur de Newton.
en physique (statique des fluides, balances, mécanique). 22. Isaac Newton (1642–1727) : on ne présente plus l’un des physiciens et mathématiciens majeurs
17. Euclide (vers 300) : on ne sait presque rien de sa vie. Il a transmis à la postérité une fraction de de l’histoire européenne. Ses Principa Mathematica Philosophiæ Naturalis eurent un retentissement im-
son ouvrage monumental, les Éléments, qui sont souvent considérés comme l’un de premiers traités de portant pour l’exposé qu’il donne d’une théorie complète de la gravitation et des lois fondamentales de
mathématiques. De nombreux sujets y sont abordés, de l’arithmétique à la géométrie. la mécanique.
18. Pierre de Fermat (1601–1665) : magistrat, scientifique et homme de lettres français qui a beaucoup 23. Gottfried-Wilhelm Leibniz (1646–1716) : philosophe et scientifique qui fut une figure intellec-
contribué aux mathématiques et à la physique. Outre ses travaux en optique et son “petit” théorème tuelle marquante du XVIIe siècle par ses contributions importantes dans des domaines très variés des
d’arithmétique, on lui doit une formule des tangentes avant le développement du calcul différentiel, ainsi sciences : philosophie, philologie, histoire, droit, logique, mathématiques.
– 15 – – 16 –
1.4. Thème et variations
vitesse moyenne sur un intervalle de temps [t, t + δt] : elle sera donnée par le rapport
entre la distance parcourue et la durée de l’intervalle
x(t + δt) − x(t)
v= .
δt
Sous cette forme, on voit bien qu’il est naturel de chercher à comprendre ce qui se
passe lorsque la durée δt de l’intervalle devient “arbitrairement” ou “infiniment” pe-
tite. Décrire rigoureusement ce phénomène revient à définir le nombre dérivée, et donc
le calcul différentiel. Cette approche est notamment celle de Newton, à l’aide de la-
quelle il formule ses célèbres lois qui permettent de décrire entièrement la mécanique
classique. Ceci mène naturellement à décrire les phénomènes physiques par des équa-
tions différentielles, comme la Troisième Loi de Newton :
mx′′ (t) = F.
Ce n’est pas la seule approche possible. En effet, Fermat propose par exemple en
optique le Principe de moindre temps, stipulant que la lumière suit entre deux points
le trajet le plus rapide. Il s’agit a priori d’une approche très différente de l’approche
géométrique usuelle, mais elle permet de retrouver toutes les lois de l’optique géomé-
trique (voir le Paragraphe 2.2.2 pour un exemple). Ce qui nous intéresse ici, c’est que
le problème mathématique sous-jacent est un problème d’optimisation.
Une approche similaire est possible en mécanique. Maupertuis a ainsi proposé un
Principe de moindre action : on peut associer à tout système mécanique une fonction
appelée action, de sorte que la trajectoire du système soit celle qui minimise l’action. In-
troduisons quelques notations pour rendre ceci plus précis. On considère par exemple
un point matériel dont la position à un instant donné est x(t) ∈ R3 . On suppose qu’on
connait la position du point l’instant t0 , qu’on note x0 , et la position à un instant t1 > t0 ,
que l’on note x1 . Si le point est soumis à une force dérivant d’un potentiel V : R3 → R,
alors l’action est Z t1
1
S= m∥x′ (t)∥2 − V dt.
t0 2
Ainsi écrite, on ne voit pas de quoi l’action S peut être fonction. Elle l’est en fait de la
trajectoire. Si γ : [t0 ; t1 ] 7→ R3 est une fonction dérivable telle que γ(t0 ) = x0 et γ(t1 ) = x1 ,
alors l’action correspondante est
Z t1
1
S(γ) = m∥γ ′ (t)∥2 − V (γ(t))dt.
t0 2
Le Principe de Maupertuis affirme alors que la trajectoire réelle du point sera donnée
par la courbe γ qui minimise cette action.
La formulation via l’action permet de remplacer la formulation à partir d’équations
différentielles en une formulation d’optimisation. Cela dit, ce problème d’optimisation
n’est pas de la même forme que ceux que nous avons présenté précédemment. En effet,
la variable sur laquelle on chercher à optimiser la fonction n’est pas un vecteur d’un es-
pace vectoriel, mais une courbe. Ceci signifie que les outils que nous allons développer
ci-après ne s’appliquent pas dans ce cadre. Il s’agit d’une théorie différente, qu’on ap-
pelle parfois calcul des variations. Même si nous ne l’aborderons pas, il est important de
signaler qu’il s’agit d’une approche centrale dans la physique moderne, par exemple en
relativité générale avec l’action d’Einstein-Hilbert. Il est également possible de transfor-
mer le Principe de moindre action en optimisation d’une autre fonctionnelle appelée
le Lagrangien du système. Cette dernière formulation admet une forme de dualité avec
une autre fonctionnelle appelée Hamiltionnien. L’étude de ces formulations est parfois
connue sous le nom de mécanique analytique.
– 17 –
Chapitre 2. À la recherche des extrema
La grande nouveauté dans ce texte est de considérer des fonctions ayant plusieurs
variables. Mais cela nous poussera aussi à considérer des fonctions dont l’espace d’ar-
rivée est une partie d’un espace vectoriel. Heureusement, ceci ne pose pas de difficulté
particulière, mais nous allons tout de même expliquer brièvement pourquoi. Pour un
CHAPITRE 2 intervalle I de R et un entier m, on considère une fonction f : I → Rm . Pour tout x ∈ I,
f (x) est un vecteur qu’on peut écrire en coordonnées de la façon suivante :
f1 (x)
À LA RECHERCHE DES EXTREMA .
f (x) = .. .
fm (x)
– 20 –
2.1. Existence Chapitre 2. À la recherche des extrema
Le fait que cette quantité est une norme signifie – outre le fait qu’elle est à valeurs Définition 2.1.7. L’intérieur d’une partie U de Rn est le plus grand ouvert contenu
positives, les trois propriétés suivantes : dans U , c’est-à-dire la réunion de tous les ouverts contenus dans U .
L’adhérence de U est le plus petit fermé contenant U , c’est-à-dire l’intersection de
• Homogénéïté : ∥λx∥ = |λ|∥x∥ pour tout λ ∈ R et x ∈ Rn ;
tous les fermés contenus dans U .
• Séparation : ∥x∥ = 0 si et seulement si x = 0 ;
• Inégalité triangulaire : ∥x + y∥ ⩽ ∥x∥ + ∥y∥. Limites et continuité
Remarque 2.1.2. Dans Rn ,
toutes les normes sont équivalentes, ce qui signifie que dans
Le but de la topologie est de permettre de définir des limites. Dans le cas d’une
tout ce que nous allons faire on pourrait remplacer la norme euclidienne par n’importe
seule variable, la définition fait intervenir, outre les incontournables δ et ϵ, des valeurs
quelle autre norme. Nous avons choisi la norme euclidienne parce que c’est la plus
absolues. En fait, il s’agit simplement de la norme euclidienne sur R. Donc, en rem-
intuitive et souvent la plus pratique.
plaçant les valeurs absolues par des normes, on obtient les généralisation des notions
La norme permet de mesurer la distance entre deux éléments de Rn , et notamment usuelles, que nous rappelons maintenant. Soit f : U → Rm une fonction, avec U une
de quantifier le fait qu’ils soient “proches” l’un de l’autre. La définition la plus pratique partie de Rn , et soit x ∈ U .
pour ce faire est celle de boule ouverte.
Définition 2.1.3. Soit x ∈ Rn et r > 0. La boule ouverte de centre x et de rayon r est • On dit que f a pour limite ℓ ∈ Rm au point x si pour tout ϵ > 0, il existe δ > 0 tel
l’ensemble que pour tout y ∈ B(x, δ) ∩ U , ∥f (y) − ℓ∥ < ϵ.
B(x, r) = {y ∈ Rn | ∥x − y∥ < r}.
• On dit que f est continue en x si f a pour limite f (x) en x.
Nous aurons souvent besoin de considérer une partie de Rn , typiquement le do-
• On dit que f est continue sur U si f est continue en tout point de U .
maine de définition d’une fonction, dans lequel on peut trouver des boules centrées
autour de n’importe quel point. Ceci correspond à la notion centrale de la topologie :
Nous aurons besoin dans la suite d’un résultat important concernant la continuité
Définition 2.1.4. Une partie U ⊂ Rn est dite ouverte si pour tout x ∈ U , il existe r > 0
pour les applications linéaires.
tel que B(x, r) ⊂ U .
Le résultat suivant n’est pas standard mais sera utilisé de nombreuses fois. Il est Théorème 2.1.8 Soit n et m deux entier. Toute application linéaire f : Rn → Rm est
donc raisonnable de le démontrer une fois pour toutes. La preuve est élémentaire, continue.
mais c’est un bon moyen de vérifier qu’on a compris les définitions.
Proposition 2.1.5. Soit x ∈ Rn et r > 0. On note x = (x1 , · · · , xn ). Alors, existe δ > 0 tel que Démonstration. On peut en fait dire beaucoup plus : toute application dont les coor-
pour tout 1 ⩽ i ⩽ n et pour tout t ∈]xi − δ; xi + δ[, données sont des polynômes en les variables est continue. Ceci résulte de la conjonc-
tion de deux faits :
(x1 , · · · , xi−1 , t, xi+1 , · · · , xn ) ∈ B(x, r).
1. Les applications (x1 , · · · , xn ) 7→ xi sont continues pour tout 1 ⩽ i ⩽ n ;
Démonstration. Il suffit de calculer
√ 2. Une somme ou un produit d’applications continue est encore une application
∥(x1 , · · · , xn ) − (x1 , · · · , xi−1 , t, xi+1 , · · · , xn )∥ = t 2
continue.
= |t|
pour constater que δ = r convient. ■ ■
La topologie, c’est avant tout du vocabulaire. Au point que, quand on donne un La continuité a de nombreux intérêts, notamment en lien avec les suites. Ceci pro-
nom à une partie, on en donne aussi un à son complémentaire : vient du résultat suivant dont nous ne rappellerons pas non plus la démonstration.
Définition 2.1.6. Une partie de Rn est dite fermée si son complémentaire est une partie
ouverte. Proposition 2.1.9 (Caractérisation séquentielle de la continuité). Soit f : U → Rm
une fonction et x ∈ U . Alors, f est continue en x si et seulement si pour toute suite (xk )k∈N
L’exemple le plus important est l’analogue de la boule ouverte définie plus haut. qui converge 1 vers x, la suite (f (xk ))k∈N converge vers f (x).
Pour x ∈ Rn et r > 0, la boule fermée de centre x et de rayon r est l’ensemble
À l’aide de cette caractérisation, il est facile de vérifier que la continuité jouit d’un
Bf (x, r) = {y ∈ Rn | ∥x − y∥ ⩽ r}.
certain nombre de propriétés de stabilité qui permettent de montrer facilement qu’une
Montrer que cette partie est effectivement fermée est un exercice profitable. fonction donnée est continue. En voici les principales :
Quand une partie n’est pas ouverte, on peut essayer de se ramener à la partie ou- 1. Une suite de Rn converge vers une limite si chaque coordonnée converge vers la coordonnée cor-
verte la plus “proche” : respondante de la limite.
– 21 – – 22 –
2.1. Existence Chapitre 2. À la recherche des extrema
• Les fonctions coordonnée x 7→ xi sont continues. cela, qui est de nature purement topologique. Aucun besoin de calcul différentiel, de
dérivation ou quoi que ce soit de ce genre. Il s’agit là d’un phénomène assez général
• Si f , g : U → Rm sont continues, alors leur somme f + g est également continue. en optimisation : les trois questions fondamentales se regroupent en deux parties en
• Si f , g : U → Rm sont continues, alors leur produit f g est également continu. fonction des outils utilisés.
• Si f : U → R est continue et ne s’annule pas, alors 1/f est également continue. 1. Démontrer l’existence d’extrema est un problème topologique ;
2. Trouver et identifier les extrema est un problème qui ne peut se résoudre de fa-
Il suit par exemple de ces propriétés que toute fonction polynomiale en les coef- çon purement topologique en général et nécessite des outils plus avancés (calcul
ficients (c’est-à-dire formée de sommes et de produits de fonctions coordonnées) est différentiel, analyse convexe, formes quadratiques).
continue.
Définition 2.1.10. Une partie K de Rn est compacte si pour toute suite (xk )k∈N d’élé-
ments de K, il existe une sous-suite (xφ(k) )k∈N qui converge vers un élément de K. Nous avons maintenant un critère permettant de savoir qu’il existe des extrema,
mais cela ne dit pas où les chercher. Pour aller plus loin, mettons-nous d’abord d’accord
La définition précédente n’est en fait pas conçue pour être vérifiée, mais pour être sur ce que nous entendons par extremum. Nous allons considérer des fonctions de la
utilisée. Mais alors, comment savoir qu’une partie est compacte ? C’est l’objet du pro- forme f : U → R, où U est une partie de Rn . Ainsi, si x = (x1 , · · · , xn ) ∈ U , on peut voir
chain résultat, qui donne un critère très simple utilisant la notion suivante : une partie f comme une fonctions possédant une variable vectorielle et on écrira dans ce cas f (x)
K de Rn est dite bornée s’il existe M > 0 tel que pour tout x ∈ K, ∥x∥ < M. pour la valeur de f en x. Ou bien, on peut voir f comme une fonction possédant n
Remarque 2.1.11. On vérifie sans peine qu’une partie est bornée si et seulement si elle variables scalaires, et on notera alors le même nombre f (x1 , · · · , xn ).
est contenue dans une boule (ouverte ou fermée). Mais pour parler d’extremum, encore va-t-il falloir définir proprement la notion.
Proposition 2.1.12. Une partie K de Rn est compacte si et seulement si elle est à la fois Bien sûr, un extremum global est facile à définir.
fermée et bornée. Définition 2.2.1. Soit f : U → R une fonction et x ∈ U . On dit que f admet
– 23 – – 24 –
2.2. Localisation Chapitre 2. À la recherche des extrema
2.2.1 Le premier théorème On obtient alors la dérivée directionnelle de f dans la direction v, une notion que
nous n’utiliserons pas.
Commençons par rappeler un résultat bien connu. Si f : I → R est une fonction
dérivable d’une variable qui admet un extremum local en un point x, alors f ′ (x) = 0. • Il existe dans la littérature plusieurs notations pour désigner les dérivées par-
Ainsi, pour trouver les extrema de f , il suffit de trouver les points auxquels la dérivée tielles. On peut par exemple rencontrer ∂xi f ou ∂i f . Nous nous efforcerons ici de
s’annule. Alors, pourquoi ne pas essayer de faire de même avec plusieurs variables ? garder la notation fractionnaire de la Définition 2.2.4.
La façon la plus naturelle d’étendre la notion de dérivation aux fonctions de plusieurs
variables est tout simplement de considérer chaque variable séparément. Il est tout Avant d’aller plus loin, remarquons que notre définition des dérivées partielles
à fait remarquable que, malgré quelques subtilités techniques que nous aborderons concerne des fonctions à valeurs vectorielles. On pourrait se demander pourquoi nous
ci-après, cette idée soit essentiellement la bonne et permette d’étendre tous les outils ne nous restreignons pas aux fonctions à valeurs dans R, puisque ce sont celles qui
d’optimisation de la dimension un. Commençons donc par donner une définition pour vont nous intéresser. Le fait est que, même en partant d’une telle fonction, nous al-
fixer les idées. lons être amenés à considérer à partir d’elle d’autres fonctions qui seront, cette fois, à
Définition 2.2.4. Soit f : U → Rm une fonction et x = (x1 , · · · , xn ) un point de U . La valeurs vectorielles. Il est donc indispensable de travailler dès maintenant dans cette
dérivée partielle de f par rapport à la i-ème coordonnée au point x est la dérivée de la généralité.
fonction
Notre objectif principal est, rappelons-le, d’être capable de détecter les extrema
fx,i : t 7→ f (x1 , · · · , xi−1 , t, xi+1 , · · · , xn )
d’une fonction par une propriété d’annulation de la dérivée. Or, nous avons déjà atteint
au point xi . On la note cet objectif ! Le tout est de s’en rendre compte ...
∂f ′
(x) = fx,i (xi ). Théorème 2.2.5 (Localisation des extrema) Soit f : U → R une fonction qui ad-
∂xi
met des dérivées partielles par rapport à toutes les coordonnées. Si x est un point
Si f admet une dérivée partielle par rapport à la i-ième coordonnée en tout point de auquel f admet un extremum, alors
U , on notera
∂f ∂f
: U → Rm (x) = 0
∂xi ∂xi
la fonction correspondante.
pour tout 1 ⩽ i ⩽ n.
Faisons quelques commentaires.
• Tout d’abord, comme U est ouvert, il existe r > 0 tel que la boule B(x, r) de centre Démonstration. Fixons une coordonnée 1 ⩽ i ⩽ n et soit, par la Proposition 2.1.5, δ > 0
x et de rayon r soit contenue dans U . La Proposition 2.1.5 donne donc δ > 0 tel tel que pour tout t ∈]xi −δ; xi +δ[, on ait (x1 , · · · , xi−1 , t, xi+1 , · · · , xn ) ∈ U . Alors, la fonction
que fx,i a, par hypothèse, une extremum local en t = xi . Donc, par le résultat dans le cas
(x1 , · · · , xi−1 , t, xi+1 , · · · , xn ) ∈ B(x, r) ⊂ U d’une variable, sa dérivée s’annule en xi . Autrement dit,
pour tout t ∈]xi − δ; xi + δ[. Ainsi, cela a bien un sens de considérer la dérivée de
la fonction fx,i au point xi . ∂f
(x) = 0,
∂xi
• On peut reformuler la définition comme suit : « la dérivée partielle par rapport
à la i-ième coordonnée est la dérivée de la fonction obtenue en fixant toutes les ce qu’il fallait démontrer. ■
coordonnées sauf la i-ième. »
• On peut également donner une expression plus explicite et littérale de la dérivée 2.2.2 Un exemple éclairant
partielle en utilisant la définition du nombre dérivé d’une fonction en un point :
∂f f (x1 , · · · xi−1 , t, xi+1 , · · · , xn ) − f (x) L’histoire de la physique a retenu le nom de Fermat comme celui de l’un des pre-
(x) = lim . miers à avoir formulé une loi physique sous forme de problème d’optimisation. S’in-
∂xi t→xi t − xi
téressant à l’optique géométrique, c’est-à-dire à l’étude de la propagation d’un rayon
• Notons (e1 , · · · , en ) la base canonique de Rn . Alors, lumineux dans différents milieux, il remarque que si l’on connait le point de départ et
le point d’arriver du rayon, alors la trajectoire est toujours celle qui minimise le temps
fx,i (t) = f (x + (t − xi )ei ) du trajet : c’est le Principe de moindre temps 2 .
et sa dérivée est xi coïncide avec la dérivée en 0 de la fonction t 7→ f (x + tei ). On 2. Comme le fait remarquer R. Feynman dans [4], le nom est trompeur, car il ne s’agit pas en général
pourrait donc plus généralement considérer un vecteur v ∈ Rn et s’intéresser à la du trajet prenant le moins de temps (penser au cas d’une réflexion) mais plutôt d’une trajectoire « telle
dérivée, si elle existe, de la fonction qu’il y a beaucoup d’autres trajectoires voisines qui prennent presque exactement le même temps », au
sens où la différence de temps sera nulle au premier ordre. Toutefois, dans notre cas, cela correspond
t 7→ f (x + tv). effectivement au trajet prenant le moins de temps.
– 25 – – 26 –
2.2. Localisation Chapitre 2. À la recherche des extrema
Nous allons regarder ce que ce principe nous dit dans le cas du phénomène de
réfraction. On considère une partie de l’espace formée de deux milieux homogènes sé-
parés par une vitre plane dont on néglige l’épaisseur. Un rayon lumineux part d’un
point P1 dans le premier milieu et arrive à un point P2 dans le second milieu. Quelle
est sa trajectoire ? Tant que le rayon est dans un milieu, le plus court chemin est un seg-
ment de droite. Par conséquent, la trajectoire du rayon sera formée de deux segments
[P1 Q] et [QP2 ], où Q est un point de la vitre. Le problème est simplement de trouver ce
point Q.
Nous allons commencer par définir un repère qui nous simplifiera la vie. Si P est
le plan de la vitre, on fixe un repère orthonormé de sorte que P soit le plan d’équa-
tion z = 0. On peut également choisir les axes de sorte que les coordonnées du point
d’arrivée P2 soient (x2 , 0, z2 ). Enfin, en fixant convenablement l’origine on peut faire
en sorte que les coordonnées du point de départ P1 soient (0, 0, z1 ). Quant au point Q,
ses coordonnées sont (x, y, 0) et nous aurons donc deux variables données par les deux
premières coordonnées.
Si v1 désigne la vitesse de la lumière dans le premier milieu (la vitesse est constante
puisque le milieu est homogène) et v2 la vitesse de la lumière dans le second milieu, le
temps de parcours global est On voit que les coordonnées de P1 dans le repère (Q, Qx, Qz) sont
Pour trouver un minimum de T , on calcule ses dérivées partielles : D’autre part, l’abscisse de P1 dans le repère (Q, Qx, Qz) est également égale à −x, tandis
que celle de P2 est égale à x2 − x. Ainsi,
Si le second terme s’annule, alors y = 0. Autrement dit, le rayon se déplace nécessaire- n1 sin(θ1 ) = n2 sin(θ2 ).
ment dans l’unique plan P ′ orthogonal à P contenant P1 et P2 ! Cela n’a rien d’évident
et faisait avant le Principe de Fermat partie des “lois de l’optique géométrique”.
On peut maintenant simplifier la première expression pour trouver 2.2.3 Les dérivées partielles
Le Théorème 2.2.5 montre que les dérivées partielles seront l’outil central de notre
étude des extrema. Il est donc utile de rassembler des informations et des résultats
∂T x x − x2 sur elles qui nous simplifieront le travail ultérieurement. Au vu de leur définition,
(x, 0) = q + q .
∂x les règles de calcul usuelles pour les dérivées s’appliquent également au dérivées par-
v1 x + z1 v2 (x2 − x)2 + z22
2 2
tielles, notamment
3. Willebrord Snell van Royen (1580–1626) : physicien et mathématicien néerlandais, il a développé
et raffiné plusieurs méthodes numériques, ce qui lui a permis de donner une approximation de π à 25
Pour interpréter cette équation, un dessin s’impose. Nous représentons ci-dessus la décimales près ou encore de donner le premier calcul du rayon terrestre par triangulation. Il n’a jamais
trajectoire du rayon dans le plan P ′ . publié la loi d’optique qui porte son nom, mais Huygens lui en a donné la paternité contre Descartes.
– 27 – – 28 –
2.2. Localisation Chapitre 2. À la recherche des extrema
• Si f et g admettent une dérivée partielle par rapport à la i-ième coordonnée, alors Ceci est l’une des manifestations d’un problème profond lié aux dérivées partielles,
leur somme également, et que nous réglerons en imposant systématiquement une hypothèse de régularité plus
forte sur les fonctions (voir le Paragraphe 2.3.2).
∂(f + g) ∂f ∂g
= + .
∂xi ∂xi ∂xi
2.2.4 Un exemple productif
• Si f et g sont à valeurs réelles et admettent une dérivée partielle par rapport à la
i-ième coordonnée, alors leur produit également, et Une des notions les plus importantes en économétrie est celle de fonction de pro-
∂(f × g) ∂f ∂g duction, introduite par Wicksteed 4 en 1894 pour décrire la production d’une entité
= g +f . économique en fonction de ses facteurs de production, c’est-à-dire ce qu’elle utilise dans
∂xi ∂xi ∂xi
le processus (ressources, argent, travail, ...). Un modèle empirique simple utilisé pour
• En particulier, toute fonction dont les coordonnées sont polynomiales en les va- décrire cette fonction est celui proposé par Cobb 5 et Douglas 6 . L’idée est de grou-
riables admet des dérivées partielles par rapport à chaque coordonnée. per tous les facteurs de production en deux variables : la capital K (pour Kapital en
allemand) et le travail L (pour Labour en anglais). En comparant avec les données dis-
• Si f est à valeurs réelles, ne s’annule pas et admet une dérivée partielle par rap- ponibles à l’époque 7 , on obtient par une méthode de moindre carrés la fonction de
port à la i-ème coordonnée, alors son inverse également, et Cobb-Douglas
∂(1/f ) 1 ∂f P (K, L) = 1, 01K 1/4 L3/4 .
=− 2 .
∂xi f ∂xi
Comme il s’agit d’un produit, on peut utiliser la formule bien connue pour calculer
La seule difficulté provient de la composition. En effet, il nous est maintenant pos- les dérivées partielles de P , ce qui donne
sible de composer des fonctions à valeurs vectorielles, et l’analogue de la formule 3/4 1/4
∂P L ∂P C
usuelle (f ◦g)′ = g ×f ′ ◦g n’est pas clair dans ce cadre. Et de fait, il n’y a tout simplement (K, L) = 0, 2525 & (K, L) = 0, 7575 .
pas de formule, car il n’est pas vrai que si f et g admettent des dérivées partielles, alors ∂K K ∂L L
g ◦ f également. Voici un exemple qui illustre ce phénomène quelque peu déroutant Ces dérivées partielles sont appelées en économie productivités marginales. Elles montrent
au premier abord. l’impact du changement de chacun des facteurs de production sur la production glo-
Exemple 2.2.6. Considérons la fonction f : R → R2 définie par bale de l’entité.
La notion de productivité marginale peut être raffinée par celle d’élasticité de pro-
f (x) = (x, x)
duction. Il s’agit de comparer la productivité marginale non pas à une variation absolue
et la fonction g : R2 → R définie par du paramètre, mais à une variation relative. De même que la dérivée partielle par rap-
port à L décrit la productivité marginale de L, c’est-à-dire l’impact d’une variation
xy infinitésimal de L, le rapport P /L décrit la productivité moyenne de L qui est une autre
si (x, y) , (0, 0)
x2 + y 2
(x, y) 7→
mesure du poids de L dans la production. L’élasticité de production est obtenue en
comparant ces deux quantités :
0 si (x, y) = (0, 0)
1 ∂P 1 1 ∂P 3
eK = (K, L) = & eL = (K, L) = .
Il est clair que f est dérivable en 0. La fonction g, quant à elle, admet des dérivées P /K ∂K 4 P /L ∂L 4
partielles en (0, 0). En effet, On voit ici l’un des points importants de ce modèle : l’élasticité de production se re-
g(0 + h, 0) − g(0, 0) trouve directement dans les exposants. Autrement dit, on peut ajuster les paramètres
= 0 −→ 0 de la fonction pour choisir les valeurs des élasticités de production.
h h→0
et
g(0, 0 + h) − g(0, 0)
h
= 0 −→ 0
h→0
2.3 Identification
donc
∂g ∂g L’œil : la fenêtre de l’âme ; le centre de la beauté du visage ;
(0, 0) = 0 = (0, 0).
∂x ∂y 4. Philip Wicksteed (1844–1927) : économiste anglais appartenant au courant dit marginaliste. Il a
De plus, (g ◦ f )(0) = 0, mais pour tout h , 0, introduit les fonctions de productions et les quantités “marginales” associées afin de décrire quantitati-
vement leur rôle dans les équilibres économiques.
h2 1 5. Charles Cobb (1875 – 1949) : économiste et mathématicien américain.
(g ◦ f )(h) = = . 6. Paul Howard Douglas (1892 – 1976) : économiste et homme politique américain, il a notamment
h2 + h2 2
été sénateur de l’Illinois sous la bannière du Parti Démocrate.
Ainsi g ◦ f : R → R est une fonction constante égale à 1/2 sauf en 0 où elle vaut 0. Une 7. Le travail de Cobb et Douglas exploite les statistiques de la production manufacturière américaine
telle fonction n’est pas dérivable en 0. au niveau macroéconomique, entre 1899 et 1922.
– 29 – – 30 –
2.3. Identification Chapitre 2. À la recherche des extrema
le point où se concentre l’identité d’un individu. Démonstration. La preuve la plus simple consiste à exploiter le tableau de variations
Milan Kundera, L’identité de f autour du point x. Malheureusement, cette notion ne s’étend pas à plusieurs va-
riables et nous allons donc donner une démonstration plus abstraite et généralisable.
Nous avons maintenant une méthode pour localiser les extrema d’une fonction. Le point de départ de la preuve est d’écrire le développement limité de f au second
Mais il ne s’agit que d’une condition nécessaire, rien ne garantit qu’elle soit suffisante. ordre en x grâce à la Formule de Taylor-Young, ce qui donne
D’ailleurs, elle ne l’est pas, et cela se voit déjà en dimension un.
h2 ′′
f (x + h) − f (x) = hf ′ (x) + f (x) + o(h2 )
Exemple 2.3.1. Soit f : R → R donnée par f (x) = x3 .
Alors, f ′ (0)
= 0, mais f n’a pas 2
d’extremum local en 0 puisque f (x) > 0 si x > 0 et f (x) < 0 si x < 0. h2 ′′
= f (x) + o(h2 ).
2
Afin de ne pas confondre extrema et points où les dérivées partielles s’annulent, Cette formule est valable pour tout h ∈] − δ; δ[ pour un certain δ > 0. La notation de
nous allons – une fois n’est pas coutume – donner un nom à ces derniers. Avant cela, in- Landau o(h2 ) désigne une fonction de la forme h2 ε(h), où ε(h) → 0 quand h → 0. On
troduisons une notation pratique. Si f : U → R est une fonction admettant des dérivées peut donc écrire l’égalité précédente sous la forme
partielles par rapport à chaque coordonnée, on peut regrouper ces dérivées partielles
f ′′ (x)
!
pour former un vecteur f (x + h) − f (x) = h2 + ε(h) .
∂f 2
(x)
∂x1
Supposons par exemple f ′′ (x) > 0, l’autre cas se traitant – mutatis mutandis – de la
. même façon. Le terme entre parenthèses dans le membre de droite tend vers f ′′ (x)/2
∇f (x) = ..
quand h tend vers 0, et il existe par conséquent δ′ > 0 tel qu’en posant δ′′ = min(δ, δ′ ),
on a pour tout h ∈] − δ′′ ; δ′′ [
∂f
(x)
∂xn f ′′ (x) f ′′ (x)
+ ε(h) > > 0.
Ce vecteur est appelé gradient de f au point x, et la fonction associée est aussi appelée 2 4
gradient de f . On constate que le gradient est non seulement une fonction de plusieurs
Ainsi, si y ∈]x − δ′′ ; x + δ′′ [∩I, on a
variables, mais également une fonction à valeurs vectorielles
f (y) − f (x) = f (x + (y − x)) − f (x)
∇f : U → Rn .
f ′′ (x)
!
= (y − x)2 + ε(h)
Ceci montre, comme nous l’évoquions plus haut, la nécessité de ne pas se restreindre 2
′′
à R pour l’espace d’arrivée. 2 f (x)
> (y − x)
Définition 2.3.2. Soit f : U → R une fonction qui admet des dérivées partielles par 4
rapport à chaque coordonnée. Un point critique de f est un point x ∈ U tel que > 0.
Autrement dit, f admet un minimum local strict en x. ■
∇f (x) = 0
L’outil crucial dans la démonstration précédente est le développement limité à
2.3.1 La stratégie l’ordre deux. Notre objectif est donc d’obtenir quelque chose d’analogue pour les fonc-
tions de plusieurs variables.
Comment donc identifier, parmi les points critiques, les extrema ? Et comment dé-
terminer leur nature (minimum ou maximum) ? Dans le cas d’une variable, cela se fait 2.3.2 Développement limité
en utilisant un développement limité. Pour plus de clarté, nous allons tout d’abord
rappeler ce résultat ainsi que sa preuve. Premier ordre
Proposition 2.3.3. Soit I un intervalle de R et f : I → R une fonction deux fois dérivables. Commençons – chi va piano, va sano – par nous intéresser au développement limité
Soit x ∈ I tel que f ′ (x) = 0. Alors, à l’ordre un. Il s’agit, pour une fonction f : I → R, de l’égalité
• Si f ′′ (x) < 0, f admet un maximum local strict en x. Ce qui est caché dans cette formule, c’est le fait que la dérivée de f donne une ap-
proximation de f par une fonction linéaire au voisinage du point x, à savoir la fonc-
Remarque 2.3.4. L’énoncé indique déjà que cette ce critère ne pourra pas toujours nous tion h 7→ hf ′ (x). Il y a un candidat naturel pour une telle application linéaire quand la
aider, puisqu’il ne peut détecter que des extrema stricts. fonction a plusieurs variables : il suffit d’utiliser les dérivées partielles !
– 31 – – 32 –
2.3. Identification Chapitre 2. À la recherche des extrema
Définition 2.3.5. Soit f : U → Rm et un point x ∈ U auquel f admet des dérivées Pour montrer que f n’admet pas de développement limité en (0, 0), observons que
partielles selon toutes les coordonnées. La différentielle de f au point x est l’application si un tel développement existe, alors f doit être continue en (0, 0). En effet, toute ap-
linéaire Dx f : Rn → Rm définie par plication linéaire sur un espace vectoriel de dimension finie est continue (Théorème
2.1.8), donc on aurait
n
X ∂f
Dx (f )(h1 , · · · , hn ) = hi . ∥f (x + h) − f (x)∥ ⩽ ∥Dx f (h)∥ + ∥o(h)∥
∂xi
i=1
−→ 0.
h→0
Remarque 2.3.6. Bien que f ne soit définie que sur une partie ouverte U de Rn , la
différentielle est une application linéaire qui est donc toujours définie sur tout l’espace Or, la fonction f n’est pas continue en (0, 0) puisque f (1/n, 1/n) = 1/2 ne tend pas vers
vectoriel Rn . Géométriquement, cela provient du fait que Rn est l’espace tangent à U au 0 = f (0, 0) quand n tend vers +∞, contredisant la Proposition 2.1.9.
point x. Nous reverrons cela en temps voulu au Paragraphe 3.1.3.
Heureusement, la situation n’est pas complètement désespérée. En effet, si l’on est
On sait bien que toute application linéaire peut se représenter, une fois des bases prêt à faire une hypothèse un peu plus forte sur les dérivées partielles, alors tout
fixées dans les espaces vectoriels de départ et d’arrivée, par une matrice. Si on note fi marche.
les fonctions coordonnées de f , pour 1 ⩽ i ⩽ m, alors la matrice de Dx f dans les bases
canoniques est Définition 2.3.8. Une fonction f : U → Rm est de classe C 1 si elle admet des dérivées
∂fi
! partielles par rapport à chaque variable, et si ces dernières sont des fonctions conti-
Jf (x) = . nues.
∂xj 1⩽i⩽m,1⩽j⩽n
Cette matrice permet facilement de représenter la différentielle de f et est donc pra- Proposition 2.3.9 (Développement limité au premier ordre). Soit f : U → Rm une
tique pour les calculs. On l’appelle matrice Jacobienne de f au point x. Si m = 1, cette fonction de classe C 1 et x ∈ U . Alors, pour tout h ∈ Rn tel que x + h ∈ U ,
matrice est une colonne, qui n’est autre que le gradient ∇f (x) de f au point x. Autre-
ment dit, pour une fonction à valeurs scalaires on a f (x + h) − f (x) = Dx f (h) + o(h) (2.1)
Nous voudrions donc maintenant obtenir une égalité de la forme Démonstration. La preuve n’est pas vraiment compliquée mais les notations sont un
peu lourdes. Inspirez profondément, on y va ! Tout d’abord, il faut comprendre qu’à
f (x + h) = f (x) + Dx f (h) + o(h), cause de la présence de o(h), cet énoncé ne donne ne fait que la valeur d’une limite
quand h tend vers 0. Ainsi, il suffit de démontrer l’égalité pour h dans une boule ou-
mais encore faut-il donner un sens au symbole o. Le problème est qu’on ne peut pas verte centrée en 0. Et de fait, comme U est ouvert il existe δ > 0 tel que B(x, δ) ⊂ U ,
supposer qu’il s’agit d’une fonction de la forme hε(h) car h est maintenant un vecteur donc x + h ∈ U dès que h ∈ B(0, δ).
et cette écriture n’a pas nécessairement de sens. La solution la plus élémentaire est de
Écrivons x = (x1 , · · · , xn ) et h = (h1 , · · · , hn ), et décomposons astucieusement la quan-
faire intervenir la norme : le symbole o(h) désignera une fonction de la forme
tité qui nous intéresse de la façon suivante :
h 7→ ∥h∥ε(∥h∥), n
X
f (x + h) − f (x) = f (x1 + h1 , · · · , xi + hi , xi+1 , · · · , xn )
où ε est une fonction qui tend vers 0 quand son argument tend vers 0.
i=1
Nous avons tous les outils en main, mais maintenant va apparaître l’une des spéci- − f (x1 + h1 , · · · , xi−1 + hi−1 , xi , · · · , xn )
ficités les plus notables du cas de plusieurs variables. En effet, l’existence des dérivées n Z hi
X ∂f
partielles ne garantit pas en général qu’on puisse écrire un développement limité au = (x1 + h1 , · · · , xi−1 + hi−1 , xi + t, xi+1 , · · · , xn ) dt
premier ordre ! Le problème est le même que pour la composition, comme le montre 0 ∂x i
i=1
l’exemple suivant.
– 33 – – 34 –
2.3. Identification Chapitre 2. À la recherche des extrema
Ainsi, la quantité qui nous intéresse, à savoir f (x + h) − f (x) − Dx f (h), est égale à Proposition 2.3.11. Soit f : U → Rm une fonction. On suppose que f admet un développe-
ment limité au premier ordre au sens suivant : il existe une application linéaire L : Rn → Rm
n Z hi !
X ∂f ∂f tel que pour tout h tel que x + h ∈ U ,
(x1 + h1 , · · · , xi−1 + hi−1 , xi + t, xi+1 , · · · , xn ) − (x1 , · · · , xn ) dt
0 ∂xi ∂xi
i=1 f (x + h) − f (x) = L(h) + o(h).
Soit ϵ > 0. Alors, pour tout 1 ⩽ i ⩽ n, il existe par continuité δi > 0 tel que ∥y − x∥ < δi Alors, f admet des dérivées partielles par rapport à toutes les coordonnées au point x, et si
implique (ei )1⩽i⩽n désigne la base canonique de Rn , on a
∂f ∂f
(y) − (x) < ϵ. ∂f
∂xi ∂xi (x) = L(ei ).
∂xi
Si l’on pose δ = mini (δi ), alors pour ∥h∥ < δ toutes les intégrandes sont plus petites que
ϵ. Autrement dit, Démonstration. Soit I un intervalle de R tel que x + tei ∈ U pour tout t ∈ I (qui existe
n par la Proposition 2.1.5). On a alors
X
∥f (x + h) − f (x) − Dx f (h)∥ < |hi |ϵ f (x + tei ) − f (x) 1 1
i=1 = L(tei ) + ∥tei ∥ε(tei )
n
t t t
X |t|
=ϵ |hi | = L(ei ) + ε(tei ).
t
i=1
n
v
t Comme ε tend vers 0 quand son argument tend vers 0, il suit que le taux d’accroisse-
√ X
⩽ϵ n h2i ment converge vers L(ei ), ce qu’il fallait démontrer. ■
i=1
√ Avant de poursuivre, nous allons faire un détour pour répondre à une question
= ϵ n∥h∥,
évoquée précédemment, à savoir celle du calcul des dérivées partielles d’une fonc-
où la dernière inégalité est une application 8 de l’Inégalité de Cauchy-Schwarz. tion composée. Pour y voir plus clair, commençons par fixer les notations. Nous allons
considérer une fonction f : U → Rm , où U est un ouvert de Rn , et g : V → Rp , où V
La preuve est maintenant terminée, mais nous allons prendre le temps de nous en est un ouvert de Rm . Pour que la composition ait un sens, nous allons supposer que
convaincre. Soit ϵ > 0 et ϵ′ = ϵ/n. Soit δ associé comme ci-dessus à ϵ′ . Alors, pour tout f (U ) ⊂ V .
h tel que ∥h∥ < δ, on a
1 Proposition 2.3.12 (Dérivées partielles composées). Supposons f et g de classe C 1 .
(f (x + h) − f (x) − Dx f (h)) < ϵ. Alors, avec les notations ci-dessus, g ◦ f est de classe C 1 , et sa différentielle en un point
∥h∥
x ∈ U est donnée par
Autrement dit, le membre de gauche est une fonction qui tend vers 0 quand ∥h∥ tend
Dx (g ◦ f ) = Df (x) g ◦ (Dx f ).
vers 0. Ceci signifie que f (x + h) − f (x) − Dx f (h) est le produit de ∥h∥ par une fonction
qui tend vers 0 quand ∥h∥ → 0, ce qui conclut. ■ Par conséquent, en notant (fj )1⩽j⩽m les fonctions coordonnées de f et (gk )1⩽k⩽p les fonctions
coordonnées de g, on a pour tout x ∈ U ,
Remarque 2.3.10. Si f : U → Rm
est une fonction, et si pour un point x ∈ U il existe 9
m
une application linéaire Dx f vérifiant l’Équation (2.1), alors f est dite différentiable en ∂(g ◦ f )k X ∂gk ∂fj
x. Il n’est pas nécessaire pour cela qu’elle soit de classe C 1 , mais cette condition est (x) = (f (x)) (x).
∂xi ∂xj ∂xi
très souvent valide et facile à vérifier dans la pratique. Nous nous y restreindrons donc j=1
dans la suite.
Démonstration. L’idée de la preuve est de composer les développements limités des
Le développement limité n’est pas qu’une propriété intéressante des fonctions de deux fonctions. Plus précisément, si r > 0 est tel que B(x, r) ⊂ U , alors pour tout h ∈
classe C 1 , c’est aussi un moyen utile d’en calculer les dérivées partielles. En effet, il est B(0, r),
parfois plus simple et plus naturel de calculer le développement limité d’une fonction
plutôt que de calculer des dérivées partielles. Nous allons expliciter ceci sous forme (g ◦ f )(x + h) = g (f (x + h))
d’une proposition. = g (f (x) + Dx f (h) + ∥h∥ε1 (∥h∥)) .
8. On peut en effet observer, en notant ξ le vecteur dont toutes les coordonnées sont égales à 1, que En posant h′ = Dx f (h) + ∥h∥ε1 (∥h∥), on a alors
pour tout vecteur k ∈ Rn ,
n
X √ g (f (x) + Dx f (h) + ∥h∥ε1 (∥h∥)) = g (f (x) + h′ )
ki = ⟨ξ, k⟩ ⩽ ∥ξ∥∥k∥ = n∥k∥.
= g (f (x)) + Df (x) g(h′ ) + ∥h′ ∥ε2 (∥h′ ∥)
i=1
Il suffit ensuite d’appliquer ce résultat au vecteur de coordonnées ki = |hi |. = (g ◦ f )(x) + Df (x) g ◦ (Dx f ) (h)
9. C’est un exercice simple mais profitable sur les développements limités vectoriels de vérifier
qu’une telle application, si elle existe, est nécessairement unique. + Df (x) g (∥h∥ε1 (∥h∥)) + ∥h∥ε2 (∥Dx f (h) + ∥h∥ε1 (∥h∥)∥) .
– 35 – – 36 –
2.3. Identification Chapitre 2. À la recherche des extrema
Pour conclure, il faut montrer que les deux derniers termes sont de la forme o(h). Pour • Si f , g : U → Rm sont de classe C k , alors f + g est de classe C k .
Df (x) g (∥h∥ε1 (∥h∥)) = ∥h∥Df (x) g (ε1 (∥h∥)) , • Si f , g : U → R sont de classe C k , alors f × g est de classe C k .
cela découle de la continuité 10 de Df (x) g. Pour • Si f : U → R ne s’annule pas et est de classe C k , alors 1/f est de classe C k .
∥h∥ε2 (∥Dx f (∥h∥) + ∥h∥ε1 (∥h∥)∥) , • Si f : U → Rm et g : V → Rp sont de classe C k et f (U ) ⊂ V , alors g ◦ f est de classe
Ck .
cela suit de la continuité de Dx f .
Pour en déduire la formule concernant les dérivées partielles, il suffit d’écrire l’éga- ∂f
lité avec des matrices. En effet, on a alors Les notations s’étendent facilement à ce cadre : la dérivée partielle de par rap-
∂xi
port à la variable xj sera notée
Jg◦f (x) = Jg (f (x))Jf (x) ∂2 f
.
et le résultat découle de la formule pour le produit de matrices. ■ ∂xj ∂xi
Ce résultat vient avec un bonus : il permet également de comprendre ce qui se passe Cela fait beaucoup de fonctions. Par exemple, dans le cas d’une fonction à valeurs
dans le cas de la réciproque d’une application bijective. scalaires f : U → R, on dispose de n dérivées partielles qui, étant chacune une fonction
définie sur U , auront n dérivées partielles. Cela nous donne un total de n2 fonctions
Corollaire 2.3.13. Soit f : U → Rn une application bijective sur son image f (U ), de classe pour décrire le comportement au second ordre. De même qu’il était commode d’orga-
C 1 et soit x ∈ U . Si Dx f est inversible, alors la réciproque f −1 de f admet des dérivées niser les dérivées partielles en une application linéaire – la différentielle – de même
partielles par rapport à toutes les coordonnées au point f (x), et sa matrice jacobienne est nous allons organiser les dérivées partielles secondes. Comme on dispose de deux fa-
donnée par milles d’indices, on peut utiliser deux vecteurs de Rn comme variables, ce qui donne
Jf −1 (f (x)) = Jf (x)−1 .
n X
n
X ∂2 f
(h, k) 7→ hi kj (x).
Démonstration. Il suffit de considérer la composée (f −1 ) ◦ f
= Id : U → U . En calculant ∂xj ∂xi
i=1 j=1
la différentielle au point x avec la formule de la Proposition 2.3.12, on trouve
On le voit, il est plus naturel de penser dans ce cadre à une application utilisant deux
Id = Dx Id vecteurs de Rn qu’à une application sur R2n . De plus, l’application ci-dessus est linéaire
= Df (x) (f −1 ) ◦ Dx f . en h quand k est fixé, et linéaire en k quand h est fixé. C’est donc une application
bilinéaire.
Ainsi, puisqu’on est en dimension finie, Dx f est inversible d’inverse Df (x) (f −1 ). ■ Définition 2.3.15. Soit f : U → Rm une fonction de classe C 2 . Sa différentielle seconde
au point x est l’application bilinéaire Dx2 f : Rn × Rn → Rm définie par
Il est bon de préciser un point qui est implicite dans l’énoncé précédent : comme la
différentielle Dx f : Rn → Rm est une application linéaire, elle ne peut être bijective que n
X ∂2 f
si les espaces vectoriels de départ et d’arrivée sont isomorphes, autrement dit si n = m. Dx2 f (h, k) = hi kj .
Il n’y a donc pas de faute de frappe ! ∂xj ∂xi
i,j=1
Second ordre Nous pouvons maintenant donner la forme du développement limité à l’ordre deux
pour les fonctions de plusieurs variables.
Maintenant que les développements limités sont pour nous un peu moins mysté-
rieux, nous pouvons nous attaquer à l’ordre deux. Pour cela, il faut tout d’abord définir Théorème 2.3.16 (Développement limité au second ordre) Soit f : U → R une
une notion de dérivée partielle d’ordre supérieur. Aucun souci : il suffit de prendre les fonction de classe C 2 et soit x ∈ U . Alors, pour tout h ∈ Rn tel que x + h ∈ U ,
dérivées partielles des dérivées partielles.
Définition 2.3.14. Une fonction f : U → Rm est dite de classe C k si elle admet des 1
f (x + h) − f (x) = Dx f (h) + Dx2 f (h, h) + o(∥h∥2 ). (2.2)
dérivées partielles et que ces dernières sont de classe C k−1 . 2
Toutes les propriétés de permanence usuelles sont encore valables ici. Résumons-
les : Démonstration. La preuve est très simple car elle repose sur une technique que nous
10. N’oublions pas qu’en dimension finie, toutes les applications linéaires sont continues par le Théo- utiliserons constamment : se ramener à une seule variable en prenant des segments.
rème 2.1.8. Bien sûr, comme dans la démonstration de la Proposition 2.3.9, il suffit de travailler
– 37 – – 38 –
2.3. Identification Chapitre 2. À la recherche des extrema
avec un h suffisamment petit. Concrètement, soit r > 0 tel que B(x, r) ⊂ U . Alors, pour En remplaçant on trouve alors
tout t ∈ [0; 1] et h ∈ B(0, r), on a 1 1
f (x + h) − f (x) − Dx f (h) − Dx2 f (h, h) = g(1) − g(0) − g ′ (0) − g ′′ (0)
2 2
∥x + th − x∥ = ∥th∥ Z1
2 1
= |t|∥h∥ = (1 − s)Dx+sh f (h, h)ds − Dx2 f (h, h)
0 2
< r. Z1 Z1
2
= (1 − s)Dx+sh f (h, h)ds − (1 − s)Dx2 f (h, h)ds
Ainsi, on peut considérer la fonction 0
Z1
0
2
= (1 − s) Dx+sh f (h, h) − Dx2 f (h, h) ds
φ : t ∈ [0; 1] 7→ f (x + th). 0
n 1
∂2 f ∂2 f
Z !
a 11
X
Si f est de classe C2, alors φ l’est également. Par conséquent, on = hi hj (1 − s) (x + sh) − (x) ds.
0 ∂xj ∂xi ∂xj ∂xi
i,j=1
Z 1
′ ′′
φ(1) − φ(0) = φ (0) + (1 − s)φ (s)ds. Soit ϵ > 0. Par continuité des dérivées partielles secondes, il existe pour tous 1 ⩽
0
i, j ⩽ n un réel δi,j > 0 tel que pour tout y ∈ B(x, δi,j ),
On a φ(1) = f (x +h) et φ(0) = f (x), donc pour conclure il nous faut maintenant calculer
φ′ (t) et φ′′ (t). On utilise pour cela la Proposition 2.3.12. En effet, φ est la composée de ∂2 f ∂2 f
(y) − (x) ⩽ ϵ.
f et de la fonction g : [0; 1] → Rn définie par ∂xj ∂xi ∂xj ∂xi
Si δ = mini,j δi,j > 0, alors pour ∥h∥ < min(δ, r) et s ∈ [0; 1], on a
g(t) = x + th,
x + sh ∈ B(x, δ) ⊂ B(x, δij ),
dont la dérivée n’est autre que la fonction (vectorielle) constante g ′ (t) = h. Ainsi,
donc
n
φ′ (t) = Dg(t) f (g ′ (t))
Z1
1 X
f (x + h) − f (x) − Dx f (h) − Dx2 f (h, h) ⩽ |hi ||hj | (1 − s)ϵds
= Dg(t) f (h). 2 0 i,j=1
X n
Écrivons les choses un peu plus explicitement pour ne pas nous perdre : = |hi ||hj |ϵ
i,j=1
n
X ∂f 2
φ′ (t) = hi (g(t)), ⩽ ∥h∥ ϵ,
∂xi
i=1
la dernière inégalité découlant de l’Inégalité de Cauchy-Schwarz. Autrement dit, le
donc membre de gauche est un o(∥h∥2 ), ce que nous voulions démontrer. ■
n
X ∂f ′ Dernier ordre
φ′′ (t) = hi Dg(t) (g (t))
∂xi
i=1
n À titre indicatif, nous allons conclure cette partie par une formule de développe-
X ∂f
= hi Dg(t) (h) ment limité à un ordre quelconque. Pour cela, il est clair qu’il faudra faire intervenir
∂xi les dérivées partielles d’ordre supérieur de la fonction f , ce qui ne pose pas vraiment
i=1
de problème. Pour alléger les formules, nous poserons
n n
X X ∂2 f
= hi hj (g(t))
n
i=1
∂xj ∂xi
j=1
(k)
X ∂k f
Dx f (h) = hi1 · · · hik .
n ∂xi1 · · · ∂xik
X ∂2 f i1 ,··· ,ik =1
= hi hj (g(t))
∂xj ∂xi On a alors :
i,j=1
2
= Dg(t) f (h, h) Proposition 2.3.17. Soit f : U → Rm une fonction de classe C k et soit x ∈ U . Alors, pour
2 tout h ∈ Rn tel que x + h ∈ U ,
= Dx+th f (h, h).
k
X 1 (j)
11. Il s’agit de la Formule de Taylor avec reste intégral à l’ordre deux, mais l’égalité peut aussi se f (x + h) − f (x) = Dx f (h) + o(∥h∥k ).
vérifier directement à l’aide d’une simple intégration par parties. j!
j=0
– 39 – – 40 –
2.3. Identification Chapitre 2. À la recherche des extrema
Démonstration. La preuve est la même que pour le Théorème 2.3.16. Soit donc r > 0 Définition 2.3.18. Une forme quadratique Q : Rn → R est dite définie positive 12 s’il
tel que B(x, r) ⊂ U et soit h ∈ B(0, r). Alors, x + h ∈ B(x, r) ⊂ U et de plus la fonction existe λ > 0 tel que
g : [0; 1] → Rm définie par Q(h) ⩾ λ∥h∥2
g(t) = f (x + th) pour tout h ∈ Rn . Elle est dite définie négative s’il existe µ > 0 tel que
est bien définie et de classe Ck . On peut donc lui appliquer la Formule de Taylor
Q(h) ⩽ −µ∥h∥2
intégrale :
k−1 1
(1 − s)k−1 (k)
Z
1 pour tout h ∈ Rn .
X
g(1) − g(0) = g (j) (0) + g (s)ds.
j! 0 (k − 1)!
j=1 Avec cette notion, la stratégie pour les fonctions d’une variable expliquée plus haut
Une récurrence simple permet de calculer les dérivées successives de g : s’étend sans difficulté.
Théorème 2.3.19 (Condition suffisante d’extrema) Soit f : U → R une fonction
j
g j (s) = Dx+sh f (h) de classe C 2 et soit x un point critique de f . Si la forme quadratique
C’est exactement la quantité qui apparaît dans le développement limité à l’ordre deux, Autrement dit, f admet un minimum local en x, ce qu’il fallait démontrer. ■
c’est donc cette forme quadratique qu’il faut comprendre. Dans certains cas, elle est 12. La définition que nous donnons ici est en fait celle d’une forme quadratique coercive. Cela dit, en
de signe constant, et l’on peut alors dire quelle est positive ou négative. Nous aurons dimension finie, les deux notions sont équivalentes et nous nous permettrons donc cet abus terminolo-
néanmoins besoin d’une notion légèrement plus forte, que nous rappelons. gique.
– 41 – – 42 –
2.3. Identification Chapitre 2. À la recherche des extrema
L’intérêt du résultat précédent est qu’il fournit une condition suffisante pour déter- Une question de symétrie
miner la nature d’un point critique : si la condition est vérifiée, alors c’est une extre-
mum local. Il existe également une condition nécessaire – mais non suffisante – uti- Nous avons vu qu’une forme quadratique est définie à partir d’une forme bilinéaire
lisant le développement limité à l’ordre deux. Bien qu’elle soit peu utile en pratique, B. Cette dernière peut se représenter à l’aide d’un matrice M(B) dont les coefficients
nous la donnons maintenant. Une forme quadratique Q : Rn → R est dite positive si sont, en notant (ei )1⩽i⩽n la base canonique de Rn ,
Q(h) ⩾ 0 pour tout h ∈ Rn et négative si Q(h) ⩽ 0 pour tout h ∈ Rn .
M(B)ij = B(ei , ej ).
Proposition 2.3.20. Soit f : U → R une fonction de classe C 2 et soit x un point critique
de f . Si f admet un minimum local en x, alors la forme quadratique Qx est positive. Si f Ceci permet bien de retrouver B puisque étant donnés deux vecteurs x et x′ on aura
admet un maximum local en x, alors la forme quadratique Qx est négative. par bilinéarité
Xn n
Démonstration. Le raisonnement commence comme dans la preuve du Théorème 2.3.19.
X
′
B(x, x ) = B xi ei , xj ej
Il existe r > 0 tel que pour tout h ∈ B(0, r),
i=1
j=1
! n
X
f (x + h) − f (x) = ∥h∥2
Qx (h, h)
+ ε(h) . = xi xj′ B(ei , ej )
∥h∥2 i,j=1
X n
Si x est un minimum local, cette quantité est positive, donc = M(B)ij xi xj′ .
i,j=1
Qx (h, h)
+ ε(h) ⩾ 0.
∥h∥2 Une autre façon d’écrire cette égalité est
Soit maintenant h′ ∈ B(0, r) et t ∈ [0; 1], de sorte que h = th′ ∈ B(0, r). L’inégalité précé- B(x, x′ ) = M(B)x, x′
dente devient
et par conséquent
Qx (th′ , th′ ) Q(x) = ⟨M(B)x, x⟩ .
0⩽ + ε(th′ )
∥th′ ∥2
Q (h′ , h′ ) Sous cette dernière forme, on voit que la condition d’être définie positive ou néga-
= x ′ 2 + ε(th′ ). tive pourrait être obtenue en comprenant les valeurs propres de M(B). En effet, admet-
∥h ∥
tons qu’il existe une base orthonormée B = (v1 , · · · , vn ) de Rn dont tous les vecteurs sont
En faisant tendre t vers 0, ε(th′ ) → 0 et on obtient donc propres pour M(B), c’est-à-dire qu’il existe λ1 , · · · , λn ∈ R tels que pour tout 1 ⩽ i ⩽ n,
Qx (h′ , h′ ) M(B)vi = λi vi .
⩾ 0,
∥h′ ∥2 P
Alors, pour tout x = i xi vi
d’où le résultat. ■
Q(x) = ⟨M(B)x, x⟩
* n n +
Entre les deux conditions que nous venons de présenter, il y a encore plusieurs X
= M(B)
X
xi vi , x i vi
possibilités. On peut parfois affirmer qu’il n’y a pas d’extremum local en un point
i=1 i=1
(voir la Proposition 2.3.25 ci-après), mais le plus souvent on ne peut déterminer la n
X D E
nature du point critique en considérant simplement les dérivées partielles secondes. = xi xj M(B)vi , vj
On parle alors de cas dégénéré, et il faudrait pousser le développement limité plus loin i,j=1
pour tâcher de comprendre ce qu’il se passe, mais il n’y a pas de critère général simple. X n D E
= xi xj λi vi , vj
i,j=1
2.3.4 Lien avec les dérivées partielles n
X
= xi2 λi .
Le Théorème 2.3.19 nous donne un critère pour vérifier qu’un point critique est i=1
un extremum. Cela dit, ce critère n’est pas très explicite puisqu’il faut déterminer une
propriété de la forme quadratique Qx , et qu’il n’est pas humainement possible de cal- En particulier, si toutes les valeurs propres de M(B) sont strictement négatives, alors
culer Qx (h) pour tous les h ∈ Rn afin d’en vérifier le signe. Comment s’y prendre alors ? Q est définie négative et si toutes ses valeurs propres sont strictement positives, alors
Il faut relier Qx aux dérivées partielles ! Q est définie positive.
– 43 – – 44 –
2.3. Identification Chapitre 2. À la recherche des extrema
Le raisonnement précédent n’a qu’une faiblesse : comment assurer que M(B) admet Posons
une base orthonormée de vecteurs propres ? L’algèbre linéaire nous fournit heureuse- ∂2 F ∂2 F
G : (s1 , s2 ) 7→ (s , s ) − (s , s )
ment une réponse : il suffit que la matrice M(B) soit symétrique. L’un des miracles du ∂t2 ∂t1 1 2 ∂t1 ∂t2 1 2
calcul différentiel est que c’est (presque) toujours le cas ! Ce résultat est généralement et supposons que G(xi , xj ) , 0. Si par exemple G(xi , xj ) > 0, alors il existe par continuité
connu sous le nom de Théorème de Schwarz 13 et nous allons maintenant l’énoncer et de G un réel δ > 0 tel que B((xi , xj ), r) ⊂ V et
le démontrer.
Théorème 2.3.21 (Théorème de Schwarz) Soit f : U → Rm une fonction de classe G(xi , xj )
C 2 et soit x ∈ U . Alors, pour tout 1 ⩽ i, j ⩽ n, G(t1 , t2 ) ⩾ >0
2
∂2 f ∂2 f pour tout (t1 , t2 ) ∈ B((xi , xj ), r). Comme B((xi , xj ), r) est ouverte, elle contient un rec-
(x) = (x). tangle [a; b] × [c; d] contenant (xi , xj ). Or, le calcul précédent montre que
∂xi ∂xj ∂xj ∂xi
Z dZ b
G(s1 , s2 )ds1 ds2 = 0.
Démonstration. Nous allons commencer par simplifier légèrement le problème en nous c a
ramenant à seulement deux variables. Fixons un point x ∈ U ainsi que deux indices
i < j compris entre 1 et n. Si r > 0 est tel que B(x, r) ⊂ U , et si Comme G est continue et de signe constant, cela implique G = 0 et donc en particulier
√ G(xi , xj ) = 0, ce qui donne enfin le résultat. ■
(t1 , t2 ) ∈ B((xi , xj ), r/2),
alors Remarque 2.3.22. On peut étendre par récurrence ce résultat aux dérivées partielles
q d’ordre supérieur de la façon suivante : pour tous 1 ⩽ i1 , · · · , ik ⩽ n et toute permutation
(x1 , · · · , xi−1 , t1 , xi+1 , · · · , xj−1 , t2 , xj+1 , · · · , xn ) − (x1 , · · · , xn ) = t12 + t22 < r σ ∈ Sk , on a
√ ∂k f ∂k f
Ainsi, en posant V = B((xi , xj ), r/2) ⊂ R2 , on peut considérer la fonction F : V → R = .
∂xi1 · · · ∂xik ∂xiσ (1) · · · ∂xiσ (k)
définie par
F : (t1 , t2 ) 7→ f (x1 , · · · , xi−1 , t1 , xi+1 , · · · , xj−1 , t2 , xj+1 , · · · , xn ). Armés de ce résultat, nous pouvons appliquer la méthode expliquée au début de
cette partie pour caractériser le fait que la différentielle seconde soit définie positive
Cette fonction est bien évidemment de classe C 2 .
ou négative. Profitons de l’occasion pour donner une définition supplémentaire.
On considère maintenant un rectangle [a; b] × [c; d] contenu dans V . Alors, Définition 2.3.23. Soit f : U → R une fonction de classe C 2 . La matrice de la forme
Zb Zd 2
∂ F
! Zb
∂F ∂F quadratique Dx2 f dans la base canonique est appelée matrice Hessienne de f au point x
(s1 , s2 )ds2 ds1 = (s1 , d) − (s1 , c)ds1 et notée Hf (x). Il s’agit d’une matrice symétrique dont les coefficients sont
a c ∂t 2 ∂t1 a ∂t1 ∂t1
= F(b, d) − F(a, d) − F(b, c) + F(a, c)
∂2 f
et Hf (x)ij = (x).
∂xi ∂xj
d b
∂2 F
Z Z !
(s1 , s2 )ds1 ds2 = F(b, d) − F(a, d) − F(b, c) + F(a, c)
c a ∂t1 ∂t2 Mentionnons pour l’anecdote que bien que le nom de “Hessienne” fasse référence
à Hesse 15 , il a en fait été introduit par Sylvester 16 . Bref, on a maintenant :
Zb Zd 2 !
∂ F
= (s1 , s2 )ds2 ds1 .
a c ∂t2 ∂t1
Proposition 2.3.24. Soit f : U → R une fonction de classe C 2 . Pour x ∈ U , la forme qua-
Pour poursuivre le calcul, il suffit de remarquer que les intégrales peuvent être échan- dratique Dx2 f est
gées : c’est une version élémentaire 14 du Théorème de Fubini. On obtient alors
• Définie positive si et seulement si toutes les valeurs propres de Hf (x) sont strictement
Zb Zd 2 ! Zd Zb 2 !
∂ F ∂ F
(s1 , s2 )ds2 ds1 = (s1 , s2 )ds1 ds2 positives.
a c ∂t2 ∂t1 c a ∂t1 ∂t2
Zb Zd 2 !
∂ F • Définie négative si et seulement si toutes les valeurs propres de Hf (x) sont strictement
= (s1 , s2 )ds2 ds1 .
a c ∂t1 ∂t2 négatives.
13. Hermann Schwarz (1843–1921) : mathématicien allemand, élève de Weierstrass, qui a contribué 15. Ludwig Hesse (1811–1874) : mathématicien allemand qui malgré l’objet qui lui est attaché en
notablement à l’analyse à une et plusieurs variables, réelles ou complexes, et à la géométrie différentielle. calcul différentiel a surtout travaillé en algèbre, notamment sur la théories des invariants.
On lui doit la version générale du l’inégalité dont il partage le nom avec Augustin-Louis Cauchy (1789– 16. James Sylvester (1814 - 1897) : mathématicien anglais qui a contribué de façon importante au
1857). développement de l’algèbre (linéaire) moderne et entre autres des formes quadratiques. On lui doit
14. On peut démontrer facilement ce résultat dans le cadre de l’intégrale de Riemann, voir l’Appen- l’introduction de plusieurs termes et notations des mathématiques modernes, et en particulier du mot
dice A. “matrice”.
– 45 – – 46 –
2.3. Identification Chapitre 2. À la recherche des extrema
Et si on n’est dans aucune de ces deux situations ? Il y a alors deux cas de figure
possibles. Si les valeurs propres sont toutes de même signe, mais que ce signe n’est pas
strict, alors on ne peut rien dire : c’est un cas dégénéré. S’il y a des valeurs propres
de signes opposés, alors le point critique n’est pas un extremum. Montrons ce dernier
point.
Démonstration. Soit λ > 0 une valeur propre de Hf (x) et soit v ∈ Rn un vecteur propre
associé, qu’on peut choisir de sorte que ∥v∥ = 1. Si r > 0 est tel que B(x, r) ⊂ U , alors
pour tout t ∈] − r; r[, x + tv ∈ U et
1
f (x + tv) − f (x) = Dx f (tv) + Dx2 f (tv, tv) + o(∥tv∥2 )
2
λt 2
= + o(t 2 )
2
λ
= t2 + ε(t) . Concluons par une remarque qui, bien qu’anodine en apparence, cache un phéno-
2 mène mathématique fascinant : pour vérifier qu’on a un extremum local, il suffit de
connaître le comportement de la fonction dans un nombre fini de directions. De plus,
Le même argument que dans la preuve du Théorème 2.3.19 montre alors qu’il existe
ces directions sont nécessairement orthogonales les unes aux autres, ce qui facilite le
r ′ > 0 tel que pour tout t ∈] − r ′ ; r ′ [,
travail !
f (x + tv) − f (x) > 0.
Le cas de deux variables
Si maintenant µ < 0 est une autre valeur propre et w un vecteur propre associé
de norme 1. Le même raisonnement montre qu’il existe r ′′ > 0 tel que pour tout t ∈ Pour conclure cette partie, nous allons traduire le critère précédente de façon plus
] − r ′′ ; r ′′ [, concrète pour des fonctions de deux variables. En effet, dans ce cas on peut facilement
f (x + tw) − f (x) < 0. déterminer la nature d’un point singulier à l’aide des dérivées partielles. Pour voir
comment, remarquons tout d’abord que la matrice Hessienne, étant symétrique, s’écrit
Ainsi, on peut trouver des points aussi proches qu’on veut de x auxquels f prend des simplement
valeurs plus grandes et plus petites que f (x). Autrement dit, f n’a pas d’extremum
!
a b
local au point x. ■ Hf (x) =
b a
Son polynôme caractéristique est
Ce cas mérite un nom, et donc un définition.
Définition 2.3.26. Soit f : U → R une fonction de classe C 2 et soit x ∈ U un point P (X) = X 2 − 2aX + a2 − b2 ,
critique de f . Si Hf (x) a au moins une valeur propre strictement positive et une valeur
dont les racines sont
propre strictement négative, alors x est appelé point selle 17 .
a ± |b|.
Exemple 2.3.27. On considère la fonction f : R2 → R définie par f (x) = x2 − y 2 . Un Comme les racines du polynôme caractéristique sont exactement les valeurs propres,
calcul immédiat donne on voit qu’il suffit de comparer les valeurs de a et |b|.
On peut également procéder autrement, en partant de l’observation – et c’est là un
! !
2x 2 0
∇f (x, y) = & Hf (x, y) = fait général pour les polynômes du second degré – que la somme des racines est égale
−2y 0 −2
à
On en déduit que (0, 0) est un point critique. De plus, Hf (0, 0) a pour valeurs propres 2 2a = Tr(Hf (x))
et −2, donc l’origine est un point selle. Si l’on dessine la surface d’équation z = f (x, y), et que leur produit est égal à
on voit apparaître un paraboloïde hyperbolique dont la forme en “selle de cheval” illustre
bien le concept : a2 − b2 = det(Hf (x)).
17. Il existe une terminologie concurrente, à savoir point col. Libre à chacun de choisir selon ses goûts Puisque seul le signe des valeurs propres nous intéresse, le signe de ces deux dernière
entre l’équitation et l’alpinisme. quantités doit suffire. Et en effet,
– 47 – – 48 –
2.3. Identification Chapitre 2. À la recherche des extrema
Proposition 2.3.28. Soit U un ouvert de R2 et f : U → R une fonction de classe C 2 . Soit Exemple 2.3.30. On considère la fonction f : R2 → R définie par
x ∈ U un point critique de f . Alors,
f (x, y) = x2 + y 2 .
1. Si det(Hf (x)) < 0, alors x est un point selle. Alors, l’unique point critique est (0, 0). De plus, la Hessienne Hf (0, 0) n’est autre que
2I2 . On a donc un minimum local en ce point. On peut alors vérifier directement que
2. Si det(Hf (x)) > 0 et Tr(Hf (x)) > 0, alors x est un minimum local. ce minimum est global.
3. Si det(Hf (x)) > 0 et Tr(Hf (x)) < 0, alors x est un maximum local. Nous poursuivons avec deux exemples de point critique dégénéré.
Exemple 2.3.31. On considère la fonction f : R2 → R définie par
Démonstration. Il suffit, comme expliqué plus haut, de rapprocher chaque information
f (x, y) = x4 + y 3 − 3y − 2.
du signe des valeurs propres.
On a !
4x3
1. Si le produit des valeurs propres est strictement négatif, alors elles sont de signes ∇f (x, y) =
3y 2 − 3
opposés.
qui s’annule en (0, 1) et en (0, −1). De plus,
2. Si le produit des valeurs propres est strictement positif, alors elles sont de même !
0 0
signe. Ce signe est le même que leur somme, d’où les deux derniers cas. Hf (0, ±1) =
0 ±6
3. Voir ci-dessus. qui a toujours une valeur propre nulle et on ne peut donc pas conclure. Néanmoins, il
est possible de déterminer la nature de ces points critiques en poussant le développe-
■ ment limité un peu plus loin. En effet, on a, pour (h, k) ∈ R2 ,
f (h, 1 + k) − f (0, 1) = h4 + 1 + 3k + 3k 2 + k 3 − 3 − 3k − 2 − (−4)
On peut même faire encore un peu plus simple, en utilisant ce que l’histoire a
= h4 + 3k 2 + k 3
retenu sous le nom de notations de Monge 18 . Il s’agit simplement de poser
= h4 + k 2 (3 + k) .
∂2 f ∂2 f ∂2 f
r= 2 ; s= ; t = 2. Pour |k| < 3, cette quantité est positive, donc on a bien un minimum local. Cependant,
∂x ∂y∂x ∂y comme f (0, −n) tend vers −∞, ce n’est pas un minimum global.
Alors, on peut donner une alternative à la Proposition 2.3.28 de la façon suivante : Exemple 2.3.32. On considère la fonction f : R2 → R définie par
f (x, y) = x2 + y 3 .
Proposition 2.3.29. Soit f : U → R une fonction de classe C 2 et soit x ∈ U un point
critique. Avec les notations ci-dessus, À nouveau, l’unique point critique est (0, 0). Cependant, on a maintenant
!
2 0
• Si rt − s2 < 0, alors on a un point selle ; Hf (0, 0) = .
0 0
• Si rt − s2 > 0 et r > 0 alors on a un minimum local ; Comme cette matrice a une valeur propre nulle, on ne peut pas conclure. De fait, en
observant que f (0, y) < 0 pour tout y < 0 tandis que f (x, 0) > 0 pour tout x, on voit que
• Si rt − s2 > 0 et r < 0 alors on a un maximum local. l’origine n’est ni un maximum local ni un minimum local.
Démonstration. Le premier cas a déjà été traité dans la Proposition 2.3.28. De plus, si
rt − s2 > 0, alors on sait déjà que Hf (x) est soit définie positive, soit définie négative. 2.4 La vraie vie
Comme
Qx (h1 , 0) = rh21 , One’s real life is so often the life that one does not lead.
O. Wilde, L’envoi in Rose leaf and apple leaf
le signe de r suffit à trancher. ■
Les résultats précédents sont satisfaisants mais restent très théoriques. En pratique,
Pour conclure, nous allons donner quelques exemples. Le cas d’un point selle a comment peut-on trouver les extrema d’une fonction ? Par exemple, pour trouver les
déjà été illustré dans l’Exemple 2.3.27, nous allons donc donner un exemple où les points critiques il faut résoudre l’équation ∇f (x) = 0, mais il s’agit d’un système de
deux valeurs propres sont de même signe strict. n équations qui ne sont en général pas linéaires, donc pour lesquelles il n’existe pas
18. Gaspard Monge (1746 – 1818) : mathématicien français qui fut l’un des plus importants de son
nécessairement de méthode de résolution exacte. Il faut par conséquent chercher des
époque. Il a beaucoup travaillé en analyse et en géométrie. Il est aussi l’un des fondateurs de l’École solutions approchées à l’aide de méthodes numériques. Nous allons en donner ici un
Polytechnique. exemple, dont nous discuterons la pertinence et les limites.
– 49 – – 50 –
2.4. La vraie vie Chapitre 2. À la recherche des extrema
2.4.1 Illustration avec une variable Si ce développement était exact, comme φ(e
x) = 0 on aurait alors e
x = x1 .
Remarquons que si φ′ (x0 ) = 0, alors la définition n’a guère de sens. Cela signifie que
Le problème numérique qui nous intéresse est de trouver la solution à une équation
la méthode ne fonctionnera que si l’on peut garantir que φ′ ne s’annule pas, au moins
de la forme φ(x) = 0, où φ : U → Rn est une fonction de n variables. En effet, il suffira
sur un voisinage de e
x. On construit alors par récurrence une suite (xk )k∈N en posant
ensuite d’appliquer la méthode à la fonction φ = ∇f .
Commençons par considérer une fonction φ : I → R, disons de classe C 2 , pour la- φ(xk )
xk+1 = xk −
quelle on veut résoudre l’équation φ(x) = 0. L’idée est de partir d’un point x0 ∈ I et de φ′ (xk )
“suivre la pente” de φ. Autrement dit, si φ(x0 ) > 0 et φ est croissante au voisinage de
x0 , alors son zéro devrait se trouver “à gauche” de x0 tandis que si φ est décroissante, Pour élémentaire que soit cette idée, elle est efficace en un certain sens que nous
son zéro devrait se trouver “à droite”. Plus précisément, l’équation de la tangente au allons maintenant préciser. Avant cela, remarquons que si la suite (xk )k∈N converge
point x0 est vers une limite e
x, cette limite est nécessairement un zéro de φ. En effet, en passant à la
y = φ′ (x0 ) + (x − x0 )φ′ (x0 ) limite dans la relation de récurrence on trouve
et nous pouvons donc suivre la tangente jusqu’à trouver son intersection x1 avec l’axe φ(e x)
x=e
x− ,
φ′ (e
e
des abscisses. Celui-ci sera alors “du bon côté” de x0 . Voici une illustration sur un x)
exemple utilisé par l’inventeur de cette méthode, qui n’est autre que Newton 19 :
ce qui donne bien φ(e
x) = 0.
Proposition 2.4.1 (Méthode de Newton à une variable). Soit φ : I → R une fonction
de classe C 2 et e
x ∈ I tel que φ(e x) = 0 et φ′ (e
x) , 0. Alors, il existe δ > 0 tel que pour tout
x0 ∈]e x + δ[, la suite (xk )k∈N converge vers e
x − δ; e x.
x − xk )2 ′′
(e
φ(e x − xk )φ′ (xk ) +
x) − φ(xk ) = (e φ (ck ).
2
On en déduit, comme φ(e
x) = 0, que
φ(xk ) φ′′ (ck )
x=
xk − e + x)2 .
(x − e
φ′ (xk ) 2φ′ (xk ) k
L’astuce pour poursuivre est de remarquer que
φ(xk )
= xk − xk+1 .
φ′ (xk )
En effet, il découle de cette égalité et de la précédente que
x| = |(xk+1 − xk ) + (xk − e
|xk+1 − e x)|
Formellement, il suffit de trouver x tel que y = 0 dans l’équation de la tangente, ce φ′′ (ck ) 2
qui donne = (x − e
x) .
2φ′ (xk ) k
φ(x )
x1 = x0 − ′ 0 .
φ (x0 ) La fonction φ′ est continue sur [e x +r] – qui est compact – et ne s’y annule pas, donc
x −r; e
elle a un minimum m > 0. De plus, la fonction φ′′ est continue sur ce même intervalle,
Un autre façon de comprendre la définition de x1 est la suivante : s’il existe e
x tel que
donc elle y admet un maximum M. Ainsi, si xk ∈ [e x + r], alors
x − r; e
x) = 0, alors le développement limité de φ au point x0 au premier ordre nous dit que
φ(e
x) est à peu près égal à
φ(e
2M
2
x)φ′ (x0 ).
φ(x0 ) + (x0 − e x| ⩽
|xk+1 − e x |2 .
|xk − e
m
19. Si la méthode que nous allons exposer est généralement appelée Méthode de Newton et a été
effectivement décrite par ce dernier dans un ouvrage publié en 1711 mais écrit en 1669, une version Pour conclure, posons
!
m m 2
simplifiée en avait déjà été donnée en 1690 par J. Raphson. On parle parfois pour cette raison de Mé-
δ = min , ,r
thode de Newton-Raphson. 2M 2M
– 51 – – 52 –
2.4. La vraie vie Chapitre 2. À la recherche des extrema
– 53 – – 54 –
2.4. La vraie vie Chapitre 2. À la recherche des extrema
Exemple 2.4.4. Considérons la fonction f : R → R définie par Posons h : x 7→ g(x)+x – en remarquant qu’il s’agit d’une fonction impaire – et étudions
son signe. On a
3 2
f (x) = −x + 4x − 2x + 2 h′ (x) = −2x arctan(x) + 1.
et partons de x0 = 0. On a f ′ (x) = −3x2 + 8x − 2, d’où L’étude du signe de cette fonction mène au tableau de variations suivant où 0 < α < 1
est un réel que nous n’aurons pas besoin de calculer explicitement :
2
x1 = 0 − =1
−2 x −∞ −α α +∞
puis
+∞ h(α)
3
= 0.
x2 = 1 − h(x)
3
Nous sommes retombés sur le point x0 . Autrement, dit la suite oscille entre deux va- h(−α) −∞
leurs : x2k = 0 et x2k+1 = 1 pour tout k ∈ N. En particulier, cette suite ne converge pas
vers l’unique solution de l’équation f (x) = 0, qui est 21
On en déduit par le Théorème des valeurs intermédiaires qu’il existe un unique
1 √ √
3
réel 22 z ∈]α, +∞[ tel que h(z) = −z (et comme h est impaire, on a également h(−z) = z).
x = 4 + 10 + 100 .
e
3 Si x ∈]z; +∞[, alors h(x) < h(z) par décroissance de h, donc g(x) < −x. Autrement dit,
|xk+1 | > |xk |. Le même résultat est vrai en supposant x ∈] − ∞; −z[ et on en déduit que
Voici une illustration :
si x0 > z, alors la suite (|xk |)k∈N est strictement croissante. Supposons qu’elle converge
vers un réel y. On aura alors par continuité |y| = |g(y)|, donc |y| = |z|. Or, par croissance
stricte de la suite,
|y| > |x0 | > |z|,
une contradiction. Ainsi, dans ce cas la suite (|xk |)k∈N tend vers +∞.
– 55 – – 56 –
2.4. La vraie vie Chapitre 2. À la recherche des extrema
– 57 – – 58 –
2.4. La vraie vie
– 59 –
Chapitre 3. Les contraintes
1. On cherche d’abord un extremum à l’intérieur du domaine (qui est un ouvert et de sorte que l’ensemble S des points où g s’annule est le cercle de centre 0 et de rayon
où l’on peut donc appliquer les méthodes du Chapitre 2). 1. Supposons qu’il existe une fonction ϕ : I → R telle que g(x, y) = 0 si et seulement si
y = ϕ(x). Alors, S serait le graphe de la fonction ϕ, et en particulier son intersection
2. On cherche ensuite les extrema sur le bord. avec une droite d’équation x = k contiendrait au
√ plus un point, pour tout k ∈ R.√ Or l’in-
√
√ de√S avec la droite d’équation x = 1/ 2 contient les deux points (1/ 2, 1/ 2)
tersection
Le but de ce chapitre est de développer des outils pour aborder le second point, ou les et (1/ 2, −1/ 2).
deux en même temps.
La bonne nouvelle, c’est qu’une telle fonction existe quand même toujours “loca-
lement”, et que cela est suffisant pour résoudre notre problème. Mais il s’agit d’un
3.1 Égalité résultat non-trivial qui va nécessiter un petit peu de travail. Avant de nous lancer,
regardons de plus près l’Exemple 3.1.3 ci-dessus.
On doit puiser avec une cuiller ce qui est égal dans les choses. Soit (x0 , y0 ) un point du cercle. On voudrait trouver un arc de cercle qui puisse être
W. Benjamin, Haschich à Marseille le graphe d’une fonction ϕ : I → R. On dispose déjà des fonctions ϕ+ , ϕ− :] − 1; 1[→ R
définies par
√
ϕ± (x) = ± 1 − x2 .
3.1.1 Motivation
Ces applications sont de classe C 1 et leurs dérivées ne s’annulent pas, ce sont donc
Considérons le second point ci-dessus. On recherche non pas le maximum de f sur des C 1 -difféomorphismes 1 . Leurs graphes sont des demi-cercles ouverts qui contiennent
U , mais son maximum sur un ensemble de la forme à eux deux tous les point du cercle excepté (−1, 0) et (1, 0). Ainsi, les autres points
appartiennent “localement” à des graphes de fonctions.
S = {x ∈ Rn | g(x) = 0} 1. Rappelons qu’un C 1 -difféomorphisme est une application bijective de classe C 1 dont la réciproque
est également de classe C 1 . Les propriétés de dérivation d’une fonction réciproque assurent qu’en effet,
pour une fonction g : Rn → R. Donnons pour plus de facilité une définition. une fonction de classe C 1 dont la dérivée ne s’annule pas est un C 1 -difféomorphisme.
– 62 –
3.1. Égalité Chapitre 3. Les contraintes
Qu’en est-il par exemple du point (1, 0) ? Il suffit en fait de tourner la figure ! En Proposition 3.1.4. Soit g : U → R une fonction de classe C k et e
x ∈ U tel que g(e
x) = 0 et
effet, après rotation d’angle π/4, ce point devient le point (0, 1), pour lequel on a une
description locale à l’aide d’un graphe. Plus concrètement, au lieu de considérer le x) , 0.
∇g(e
graphe de ϕ+ , à savoir {(x, ϕ+ (x)) | x ∈] − 1; 1[}, on peut considérer l’ensemble
Alors, quitte à permuter les coordonnées, il existe un ouvert V ⊂ Rn−1 contenant (e xn ),
x1 , · · · , e
{(ϕ+ (y), y) | y ∈] − 1; 1[}, un ouvert W ⊂ R contenant e xn et une fonction de classe C k
ϕ:V →W
qui contient bien (1, 0).
Ainsi, quitte à échanger les coordonnées, on peut “recouvrir” le cercle par des tels que pour tout x ∈ V × W ⊂ U ,
graphes de fonctions. En d’autres termes, le cercle est “localement” un graphe de fonc-
tion à permutation près des coordonnées. Les fonctions en questions sont alors des g(x) = 0 ⇐⇒ xn = ϕ(x1 , · · · , xn−1 ).
“paramétrages locaux” du cercle.
Démonstration. L’hypothèse sur le gradient de g signifie qu’il existe au moins une dé-
x. Quitte à changer la numérotation des coor-
rivée partielle qui est non-nulle au point e
3.1.2 Le théorème des fonctions implicites données, on peut supposer – ce que nous ferons – qu’il s’agit de la dernière. Autrement
dit, dans toute la preuve nous utiliserons le fait que
Notre objectif est maintenant de trouver des conditions – si possible simples à ex-
primer – sur une fonction g pour que l’ensemble S = {x | g(x) = 0} puisse être “recou- ∂g
(e
x) , 0.
vert” par des graphes de fonctions comme dans le cas du cercle. Il s’avère que quoique ∂xn
remarquable, un tel résultat n’est pas si difficile à obtenir, et peut se démontrer en
utilisant simplement des résultats sur les fonctions d’une variable. Si la démonstration n’est pas très ardue, elle n’est pas complètement intuitive pour
autant. Nous allons donc procéder par étapes pour plus de clarté. Remarquons avant
Cependant, pour y voir plus clair, nous allons commencer par traiter le cas d’une de commencer que l’hypothèse de l’énoncé nous dit que la dérivée partielle de g par
seule contrainte. Et dans ce cas, la condition nécessaire pour pouvoir exprimer une co- rapport à la n-ième coordonnée est soit strictement positive, soit strictement négative
ordonnée en fonction des autres est particulièrement simple. Pour avoir une intuition au point ex. Quitte à remplacer g par son opposée, on peut supposer sans perte de
de son origine, considérons une fonction g : U → R et imaginons que nous puissions la généralité que
remplacer par le début de son développement limité au premier ordre pour un certain ∂g
x ∈ U tel que g(e
x) = 0, c’est-à-dire qu’on ait, pour tout y ∈ U tel que g(y) = 0, (e
x) > 0.
∂xn
e
0 = g(y)
= g(e
x) + De x g(y − x)
▶ Existence de la fonction ϕ
= ⟨∇g(ex), y − x⟩
n
X ∂g Par continuité de la dérivée partielle de g par rapport à la n-ième coordonnée, il
= (yi − exi ) (e
x)
i=1
∂xi existe r > 0 tel que 2 pour tout x ∈ B(e
x, r) ⊂ U ,
∂g
(x) > 0.
Si par exemple la dérivée partielle de g par rapport à la dernière variabel ne s’annule ∂xn
pas, alors on peut écrire Nous allons maintenant “découper la boule en deux”. Plus précisément, posons
n−1 xn−1 ) ∈ Rn−1 .
!−1 X
∂g ∂g e = (e
χ x1 , · · · , e
yn = e
xn − (e
x) (yi − e
xi ) (e
x)
∂xn ∂xi
i=1 Alors, si χ ∈ B1 = B(e
χ, r/2) et y ∈]e xn +r/2[, on a en notant (χ, y) = (χ1 , · · · , χn−1 , y),
xn −r/2; e
= ϕ(y1 , · · · , yn−1 ).
∥(χ, y) − e e∥ + ∥y − e
x∥ ⩽ ∥χ − χ xn ∥ < r.
Autrement dit, on peut exprimer une des coordonnées de y en fonction des autres.
Par conséquent, pour χ ∈ B1 , la fonction y ∈]e xn − r/2; exn + r/2[7→ g(χ, y) est strictement
En général, on sait que g coïncide “presque” avec le début de son développement croissante. De plus, on sait que g(e χ, xen ) = 0, donc par croissance stricte,
limité si l’on est “suffisamment proche” de ex, et le calcul précédent a donc une chance
r r
d’être encore valable, à condition qu’au moins une des dérivées partielles de g soit non- g χ e, e
xn − <0 & g χ xn +
e, e > 0.
nulle. Cette dernière condition peut s’écrire de façon plus synthétique ∇g(e x) , 0, et 4 4
nous allons maintenant voir qu’elle est effectivement suffisante pour obtenir le résultat 2. On sait également qu’il existe r ′ > 0 tel que B(e
x, r ′ ) ⊂ U parce que U est un ouvert. En remplaçant
souhaité. r par min(r, r ′ ) on peut donc supposer comme nous le faisons que B(e x, r) ⊂ U .
– 63 – – 64 –
3.1. Égalité Chapitre 3. Les contraintes
Par continuité de g, il existe donc δ, δ′ > 0 tels que pour tout χ ∈ B(e
χ, δ) ⊂ U Nous allons d’abord montrer que ϕ est continue au point χ e. Pour ce faire, considé-
rons ϵ > 0. D’après ce qui précède, il existe δ > 0 tel que pour tout χ ∈ B(e
χ, δ),
r
xn − ) < 0
g(χ, e
4 ϕ(χ) ∈]e xn + ϵ[,
xn − ϵ; e
et pour tout χ χ, δ′ ),
∈ B(e donc ϕ est bien continue en χ e. Si maintenant on considère un point quelconque χ ∈ V ,
r x′ = (χ, ϕ(χ)). Alors, la fonction g vérifie
posons e
xn + ) > 0.
g(χ, e
4
∂g ′
Ainsi, en posant r ′ = min(r, δ, δ′ ), on a pour tout χ ∈ B′ = B(eχ, r ′ ) que x′ ) = 0
g(e & (e
x ) , 0,
∂xn
r r donc on peut appliquer la première partie de la preuve pour obtenir l’existence d’une
g χ, exn − < 0 & g χ, e xn − > 0.
4 4 fonction ϕ ′ : V ′ × W ′ → U qui est continue en χ. Il suffit maintenant de remarquer que
pour tout χ ∈ V ∩ V ′ , on a g(χ, ϕ ′ (χ)) = 0 donc ϕ ′ (χ) = ϕ(χ). Ainsi, ϕ et ϕ ′ coïncident
Alors, par le Théorème des valeurs intermédiaires appliqué à la fonction y 7→ g(χ, y), sur cet ouvert qui contient χ donc ϕ est continue en χ.
il existe un unique ϕ(χ) ∈]e xn + r/4[ tel que g(χ, ϕ(χ)) = 0. En posant V = B′ et
xn − r/4; e
W =]e xn + r/4[, on a bien l’existence de la fonction de l’énoncé.
xn − r/4; e
▶ Régularité de la fonction ϕ
Avant d’aller plus loin, nous allons tenter d’illustrer le raisonnement précédent
dans le cas de deux variables. On considère la fonction g : R2 → R définie par
Soit 1 ⩽ i ⩽ n − 1, soit χ ∈ V et soit (par la Proposition 2.1.5) δ > 0 tel que pour tout
g(x1 , x2 ) = x12 + x22 − 16. t ∈] − δ; δ[, χ + tei ∈ V . On pose, pour un tel t,
a = (χ, ϕ(χ)) & b = (χ + tei , ϕ(χ + tei )) .
Dans la figure ci-après, on a représenté le cercle d’équation g(x1 , x2 ) = 0, ainsi qu’un
point e
x vérifiant On remarque que ces deux points appartiennent à V × W ⊂ B(e x, r), donc que pour tout
∂g s ∈ [0; 1], a + s(b − a) ∈ B(e
x, r). On peut donc considérer la fonction
(e
x) > 0.
∂x2
h : s ∈ [0; 1] 7→ g (a + s(b − a)) .
On peut constater sur le dessin que si l’on se déplace horizontalement à l’intérieur du
rectangle, alors on pourra toujours ensuite atteindre le cercle en se déplaçant de r/4 Il s’agit d’une fonction de classe C 1 , et le Théorème des accroissements finis affirme
verticalement, soit vers le haut soit vers le bas. Ainsi, l’arc de cercle en gras est bien le l’existence d’un s0 ∈]0; 1[ tel que
graphe d’une fonction de la variable x1 . h(1) − h(0) = h′ (s0 ),
ce qui donne, avec c = a + s0 (b − a),
∂g ∂g
g(b) − g(a) = (c)t + (c) (ϕ(χ + tei ) − ϕ(χ)) .
∂xi ∂xn
Comme g(a) = 0 = g(b) par construction, on en déduit que
!−1
ϕ(χ + tei ) − ϕ(χ) ∂g ∂g
=− (c) (c).
t ∂xn ∂xi
Par continuité de ϕ, b → a quand t → 0, donc c → e x. Il suit que ϕ admet une dérivée
partielle par rapport à la i-ème coordonnée, et
!−1
∂ϕ ∂g ∂g
(χ) = − (χ, ϕ(χ)) (χ, ϕ(χ)).
∂xi ∂xn ∂xi
Si g est de classe C k , alors le membre de droite est de classe C k−1 , donc ϕ est de classe
C k , ce qui conclut la preuve. ■
Exemple 3.1.5. Illustrons ce résultat dans le cas du cercle. On pose g(x, y) = x2 + y 2 − 1.
Alors, ∇g(x, y) = (2x, 2y) et ce vecteur ne s’annule qu’au point (0, 0). Or g(0, 0) , 0, donc
on peut appliquer la Proposition 3.1.4 en tout point de l’ensemble {x ∈ Rn | g(x) = 0},
qui n’est autre que le cercle de centre 0 et de rayon 1. Nous avons déjà vu que tout
▶ Continuité de la fonction ϕ point du cercle est contenu dans un graphe de fonction lui-même contenu dans le
cercle, mais nous retrouvons ici ce résultat presque sans aucun calcul.
– 65 – – 66 –
3.1. Égalité Chapitre 3. Les contraintes
Le problème maintenant c’est qu’en général il n’y a pas de raison pour qu’il n’y ait Nous avons déjà démontré H1 : c’est exactement le contenu de la Proposition 3.1.4.
qu’une seule contrainte. Il faudrait donc considérer m fonctions Supposons donc Hm vraie, et considérons le cas m+1. Nous allons d’abord appliquer la
Proposition 3.1.4 à l’une des coordonnées pour la faire disparaître, de sorte qu’il suffira
g1 , · · · , gm : U → R, ensuite d’utiliser Hm . Pour ce faire, remarquons d’abord que ∇gm+1 (e x) , 0 puisqu’il
fait partie d’une famille libre, donc qu’au moins une de ses coordonnées est non nulle.
qui définissent une partie Quitte à permuter les coordonnées, on peut donc supposer que
∇g1 (e x ) ∈ Rn
x), · · · , ∇gm (e Nous savons maintenant exprimer une des variables en fonction des autres, ce qui
nous permet de nous ramener au cas de m variables. Pour ce faire, notons h la fonction
est libre, alors – quitte à permuter les coordonnées – il existe un ouvert V ⊂ de coordonnées (g1 , · · · , gm ) et H : V → Rm la fonction définie par
Rn−m contenant (e xn−m ), un ouvert W ⊂ Rm contenant (e
x1 , · · · , e xn ) et une
xn−m+1 , · · · , e
fonction de classe C k H(x1 , · · · , xn−(m+1) , y1 , · · · , ym ) = h x1 , · · · , xn−(m+1) , y1 , · · · , ym , ψ(x1 , · · · , xn−(m+1) , y1 , · · · , ym )
ϕ:V →W
On a H(e xn ) = 0 et il suffit de vérifier la condition sur les gradients des coordon-
x1 , · · · , e
tels que pour tout x ∈ V × W on ait nées de H. Or, on a pour 1 ⩽ i ⩽ m et 1 ⩽ j ⩽ n − m
g1 (x) = · · · = gm (x) = 0 ⇐⇒ (xn−m+1 , · · · , xn ) = ϕ(x1 , · · · , xn−m ). ∂Hi ∂g ∂ψ ∂g
(x) = i (x) + (x) i (x)
∂xj ∂xj ∂xj ∂xn
!−1
Les mots en gras dans l’énoncé sont importants. Ce que dit le théorème, c’est qu’on ∂gi ∂g ∂gm+1 ∂gi
= (x) − m+1 (x) (x) (x)
peut exprimer m coordonnées en fonction des n − m autres. Mais ces coordonnées ne ∂xj ∂xj ∂xn ∂xn
sont pas forcément les m dernières dans la base canonique, comme nous l’avons vu
dans l’exemple du cercle (il faut parfois exprimer x en fonction de y). Dans ce dernier Autrement dit,
!−1
cas, le changement de base était donné par une rotation d’angle π/2. ∂gm+1 ∂gi
∇Hi (e
x) = ∇gi (e
x) − (e
x) (e
x)∇gm+1 (e
x)
∂xn ∂xn
P
Démonstration. L’idée de la preuve est de procéder par récurrence à l’aide de la Propo- et ces vecteurs forment une famille libre. En effet, si λ1 , · · · , λm ∈ R vérifient i λi ∇Hi (e
x) =
sition 3.1.4. Ceci nécessite d’exprimer d’abord une variable en fonction des autres et 0, alors on a m
m !−1
nous allons donc diviser la démonstration en deux étapes pour plus de clarté. X X ∂gm+1 ∂gi
λi ∇gi (e
x) − λi ∇g (e
x) = 0.
∂xn+m ∂xn m+1
i=1 i=1
▶ Simplification d’une variable
La liberté de la famille ∇g1 (e
x), · · · , ∇gm+1 (e
x) implique alors λi = 0 pour tout 1 ⩽ i ⩽ m.
On peut donc appliquer l’hypothèse de récurrence au rang m pour obtenir des ouverts
Nous allons procéder par récurrence, avec l’hypothèse de récurrence suivante : V ⊂ Rn−m et W ⊂ Rm et une application φ : V → W de classe C k tels que pour tout
(χ, y) ∈ V × W ,
Hm : « Le Théorème est vrai quand le nombre de fonctions est exactement égal à m. » H(x, y) = 0 ⇐⇒ y = φ(x).
– 67 – – 68 –
3.1. Égalité Chapitre 3. Les contraintes
Ces application sont appelées différentielles partielles puisqu’elles se définissent comme ∂fe ∂f ∂ϕ ∂f
(e
x) = (e
x) + (e xn−1 )
x ,··· ,e (e
x)
la différentielle mais en se restreignant à certaines coordonnées ∂xi ∂xi ∂xi 1 ∂xn
∂f ∂g/∂xi (e
x) ∂f
Proposition 3.1.8. Sous les hypothèses du Théorème 3.1.6, on a = (e
x) − (e
x).
∂xi ∂g/∂xn (e
x) ∂xn
!
∂ϕ −1 ∂g Si cette quantité est nulle, alors on a
(e xn−m ) = − De
x1 , · · · , e x,2 g (e
x) ,
∂xj ∂xj
∂g ∂f ∂g ∂f
où g = (g1 , · · · , gm ). (e
x) (e
x) = (e
x) (e
x).
∂xn ∂xi ∂xi ∂xn
– 69 – – 70 –
3.1. Égalité Chapitre 3. Les contraintes
Nous avons donc une condition suffisante d’extremum sous contrainte d’égalité !
où ∇1 f (e
x) est le vecteur formé des n − m première coordonnées de ∇f (e x) et ∇2 f (e
x)
Tout cela est bien beau, mais comme nous l’avons vu dans l’exemple de la Section le vecteur formé des m dernières. Comme ceci doit être valable pour tout h, les deux
1.1.2, les contraintes peuvent être données par plusieurs fonctions g1 , · · · , gm . Dans ce vecteurs à gauche des produits scalaires sont égaux. Autrement dit, ∇f (e x) appartient à
cas, l’analogue naturel de l’égalité ci-dessus serait que ∇f (x) soit une combinaison li- l’espace vectoriel
néaire des ∇gi (x). De fait, c’est le cas et il s’agit d’un résultat très important du à La-
grange 3 .
t
V = ξ ∈ Rn | (ξ1 , · · · , ξn−m ) = De
x,2 g
−1
x,1 (g) (ξn−m+1 , · · · , ξn ) .
◦ De
Théorème 3.1.9 (Condition nécessaire d’extremum sous contrainte) Soit f : U →
R une fonction de classe C 1 , soient g1 , · · · , gm : U → R des fonctions également de Les coordonnées d’un élément de V sont déterminées par les m dernières, donc c’est
classe C 1 . Supposons que la restriction de f à l’ensemble un espace vectoriel de dimension au plus m. Par ailleurs, pour 1 ⩽ i ⩽ m, on a gi ◦ Φ =
0, donc cette fonction a en particulier un extremum local en e x, ce qui par le calcul
S = {x ∈ U | gi (x) = 0 pour tout 1 ⩽ i ⩽ m}. précédent montre que ∇gi (e
x) ∈ V . Comme
∇g1 (e
x), · · · , ∇gm (e
x) est une famille libre, il suit que dim(V ) ⩾ m. Ainsi, dim(V ) = m et les vecteurs précé-
dents forment une base de V . Par conséquent, ∇f (e x) ∈ E est combinaison linéaire de
est libre, alors il existe λ1 , · · · , λm ∈ R tels que ces derniers, ce qu’il fallait démontrer. ■
m
X Donnons un petit exemple pour illustrer la méthode et son utilité.
∇f (e
x) = λi ∇gi (e
x).
i=1 Exemple 3.1.10. On considère un consommateur qui veut posséder deux biens x1 et
x2 . Sa satisfaction vis-à-vis des quantités de chaque bien qu’il possède est donnée par
une fonction d’utilité u que nous prendrons de type Cobb-Douglas :
Les scalaires λ1 , · · · , λm sont appelés multiplicateurs de Lagrange.
u(x1 , x2 ) = x1α x21−α .
Démonstration. Le Théorème 3.1.6 nous donne une fonction implicite ϕ : V → W telle
Si les prix p1 et p2 des biens sont fixés, et si le consommateur veut atteindre une valeur
que la fonction
d’utilité u0 fixée (qu’on peut interpréter comme son niveau de vie idéal), quel est le
fe : (x1 , · · · , xn−m ) 7→ f (x1 , · · · , xn−m , ϕ(x1 , · · · , xn−m )) . moyen le plus économique de réaliser son objectif ?
Il s’agit de minimiser la fonction
a un extremum local au point e x. Nous allons maintenant différentier cette expression,
et pour rendre les calculs plus clairs nous allons poser p(x1 , x2 ) = p1 x1 + p2 x2
Φ(x1 , · · · , xn−m ) = (x1 , · · · , xn−m , ϕ(x1 , · · · , xn−m )), sous la contrainte u(x1 , x2 ) = u0 . Une façon pratique d’utiliser le Théorème 3.1.9 est de
considérer la fonction
3. Joseph-Louis Lagrange (1736–1813) : mathématicien et physicien d’origine italienne et naturalisé
français. Il est l’un des plus important scientifiques du XVIIIe siècle. Ses travaux mathématiques portent L(x1 , x2 , λ) = p(x1 , x2 ) − λ (u(x1 , x2 ) − u0 )
sur tous les domaines de l’algèbre et de l’analyse, des plus théoriques au plus appliqués. Ses travaux
physiques, quant à eux, ont eu une important cruciale, notamment sa mécanique analytique. = p1 x1 + p2 x2 − λx1α x21−α
– 71 – – 72 –
3.1. Égalité Chapitre 3. Les contraintes
et de chercher ses points critiques. On obtient alors le système Pour le démontrer, on ne peut recourir à un argument de compacité car
= λαx1α−1 x21−α
p1 {(x1 , x2 ) ∈ R2+ | u(x1 , x2 ) = u0 }
= λ(1 − α)x1α x2−α
p
2
xα x1−α =
u
1 2 0 n’est pas borné. D’ailleurs, il n’y a qu’un seul point critique sous contrainte, donc f n’a
pas de maximum. On peut néanmoins observer que f (x) → +∞ quand ∥x∥ → +∞, et
En divisant la première équation par la dernière, on trouve
ceci suffit à assurer l’existence d’un minimum.
p1
= λαx1−1
u0
Une interprétation géométrique
tandis qu’en divisant la seconde équation par la dernière on trouve
p2 Nous avons maintenant un critère relativement simple pour détecter les points cri-
= λ(1 − α)x2−1 . tiques sous contraintes d’égalité d’une fonction. Mais que signifie-t-il ? On pourrait
u0
bien sûr se contenter de le considérer comme une condition algébrique utile bien que
On voit donc que pour que λ existe, on doit avoir mystérieuse, mais il y a en fait plus : il y a derrière une interprétation géométrique
p1 x1 p2 x2 riche. Pour l’expliquer, revenons à l’idée de recouvrement par des graphes que nous
= . avons évoquée au début de ce chapitre. Pour ce faire, précisons d’abord notre vocabu-
α 1−α
laire.
En réinjectant dans u on trouve alors Définition 3.1.11. Soit ϕ : U ⊂ Rn−p → Rp une fonction. Son graphe est l’ensemble
1−α !1−α
α p1
x1α x11−α = u0 Sϕ = {(x, ϕ(x)) | x ∈ U } ⊂ Rn .
1−α p2
et donc !1−α !α Le Théorème des fonctions implicites 3.1.6 nous dit précisément que si les gra-
1−α α
1−α p2 1−α p1 dients des fonctions gi sont linéairement indépendants en un point x, alors il existe
x1 = u0 & x2 = u0 .
α p1 α p2 un ouvert V ⊂ Rn contenant x tel que S ∩ V , = Sϕ , où ϕ est la fonction implicite. Ceci
suggère que ces conditions sont en général les bonnes pour avoir un objet géométrique
Bien sûr, nous n’avons trouvé ici qu’un point critique sous contraintes, et rien de sur lequel on peut travailler, et mène ainsi à la définition suivante :
garantit a priori qu’il s’agisse d’un maximum local et encore moins global. C’est néan- Définition 3.1.12. Une sous-variété de Rn de codimension p et de classe C k est une partie
moins bien le cas, comme le suggère l’allure de la fonction obtenue en exprimant x2 en S ⊂ Rn telle que pour tout x ∈ S, quitte à permuter les coordonnées, il existe
fonction de x1 grâce à la contrainte :
• Un ouvert V de Rn−p ;
• Un ouvert W de Rp ;
S ∩ (V × W ) = Sϕ .
Autrement dit, une sous-variété est localement le graphe d’une fonction à permu-
tation près des coordonnées. Tout l’enjeu de la géométrie différentielle est de com-
prendre la structure globale des sous-variétés alors que la définition ne donne que des
informations locales. Pour ce qui nous concerne, nous voyons donc que trouver les
extrema d’une fonction f sous des contraintes d’égalité revient à trouver les extrema
d’une fonction f quand elle parcourt les points d’une sous-variété. Quand, dans un
problème de géométrie, on se restreint à des points appartenant à un objet particulier
(droite, cercle) on dit parfois que les points sont liés à l’objet. Ceci explique pourquoi
un extremum sous contrainte est parfois appelé extremum lié. On parlera de même de
point critique lié.
Le Théorème des fonctions implicites 3.1.6 peut alors s’exprimer géométrique-
ment.
– 73 – – 74 –
3.1. Égalité Chapitre 3. Les contraintes
la famille de vecteurs
Exemple 3.1.14 (Coniques). Tout d’abord, si on a une seule fonction g et deux va-
riables, on obtient alors une courbe plane. Dans le cas d’une fonction polynomiale du
second degré (qui est l’exemple le plus simple puisque dans le cas du premier degré
on obtient un point), les courbes obtenues seront des coniques. Il en existe trois types
x2 y 2
que nous listons ci-dessous. Elles sont accompagnées d’un dessin les représentant avec • L’hyperbole d’équation − = 1,
leur foyer et leur directrice, qui permettent de les définir de manière purement géomé- a2 b2
trique 4 .
x2 y 2
• L’ellipse d’équation + = 1,
a2 b2
4. Étant donnés une droite D, un point F extérieur à cette droite et une réel e > 0, la conique de foyer x2 y 2 z2
F, de directrice D et d’excentricité e est l’ensemble des points M du plan tels que d(M, F) = ed(M, D). • L’ellipsoïde d’équation + + = 1,
a2 b2 c2
– 75 – – 76 –
3.1. Égalité Chapitre 3. Les contraintes
La i-ème coordonnée de ∇g(x) n’est autre que 2xi , donc en tout point distinct de l’ori-
gine, ∇g(x) , 0. Ainsi, S est une sous-variété, et l’on aura reconnu la sphère de rayon r
centrée sur l’origine.
Exemple 3.1.17. On considère l’ensemble SLn (R) des matrices carrées de taille n et
x2 y 2 de déterminant 1. Pour le décrire à l’aide d’une fonction, il semble naturel de définir
• Le paraboloïde elliptique d’équation + = z,
a2 b2 g : Mn (R) → R par
g(M) = det(M) − 1.
La différentielle de g est donnée par 5
En particulier, pour H = Eij – la matrice dont le coefficient (ij) vaut 1 et tous les autres
0 – on trouve
∂g
(M) = DM g(Eij ) = Com(M)ji .
∂Mij
Or, ce dernier terme est un multiple du déterminant d’une matrice extraite de taille n−
1 de M. Comme M est inversible si elle est dans SLn , au moins l’un de ces déterminants
est non nul. Autrement dit, ∇g(M) , 0 et SLn est donc bien une sous-variété.
Nous avons donc notre intuition géométrique, mais quid de la condition du Théo-
rème 3.1.9 ? Pour l’expliquer, il nous faut comprendre le lien entre la géométrie de S
x2 y 2 z2 et les gradients des fonctions gi . Nous allons pour cela faire appel à la notion d’espace
• L’hyperboloïde à une nappe d’équation + − = 1,
a2 b2 c2 tangent.
Qu’est-ce que la tangente au graphe d’une fonction ? C’est, en un point donné e x, la
droite qui “approche” le mieux la courbe, au sens où si y = ax + b est l’équation de cette
droite, alors
f (x) − (ax + b) = o(x − e
x).
Le développement limité au premier ordre de f au point e
x pouvant s’écrire
x) + f ′ (e
f (x) − [f (e x)(x − e
x)] = o(x − e
x),
d
X
ψ : (t1 , · · · , td ) ∈ Rd 7→ ti vi ,
i=1
Comme dans le cas des coniques, on vérifie facilement que ce sont des sous-variétés. 5. Ceci a été vu en TD.
– 77 – – 78 –
3.1. Égalité Chapitre 3. Les contraintes
où (vi )1⩽i⩽d est une base du sous-espace. Or, le développement limité de ϕ au premier Exemple 3.1.21. Reprenons l’Exemple 3.1.16 de la sphère. Comme ∇g(x) = 2x, l’es-
ordre au point e x s’écrit pace tangent en x est le sous-espace affine passant par x et dirigé par x⊥ . Dans le cas
du cercle (n = 2), on retrouve bien la caractérisation de la tangente comme droite or-
n−p
X ∂ϕ thogonale au rayon (qui est dirigé par le vecteur x).
x) −
ϕ(x) − ϕ(e (xi − e
xi ) (e
x) = o(x − e
x).
∂xi
i=1
Le critère du Théorème 3.1.9 peut alors se reformuler de la façon suivante : si f a
Le sous-espace que nous recherchons est donc engendré par les dérivées partielles de un extremum sous contrainte au point e x, alors le gradient de f en e
x est orthogonal à
ϕ. Nous sommes maintenant prêts à donner une définition, en n’oubliant pas que dans l’espace tangent. Remarquons que s’il n’y a aucune contrainte, S = U est un ouvert et
le cas d’une variable par exemple, la tangente est un objet géométrique, c’est-à-dire son espace tangent est Rn . Comme seul le vecteur nul est orthogonal à Rn , on retrouve
le graphe de la fonction x 7→ ax + b. Pour simplifier, la notation, nous utiliserons la alors la condition du Théorème 2.2.5.
différentielle de ϕ au lieu des dérivées partielles, en se souvenant que Exemple 3.1.22. Soit A ∈ Mn (R) une matrice symétrique, et considérons la fonction
n−p f : Rn → R définie par
X ∂ϕ f (x) = ⟨Ax, x⟩.
De x) =
x ϕ(x − e (xi − e
xi ) (e
x).
∂xi
i=1 Un calcul élémentaire permet d’obtenir le gradient de f :
Définition 3.1.18. Sois S une sous-variété, e x ∈ S et ϕ tel que S coïncide au voisinage f (x + h) = ⟨Ax, x⟩ + ⟨Ax, h⟩ + ⟨Ah, x⟩ + ⟨Ah, h⟩
x avec le graphe de ϕ à permutation des coordonnées près. Alors, l’espace tangent à
de e
= f (x) + ⟨Ax, h⟩ + ⟨h, Ax⟩ + o(∥h∥)
S au point e x est le sous-espace affine de Rn passant par (x, ϕ(x)) et dirigé par le graphe
de De ϕ, c’est-à-dire par le sous-espace vectoriel = f (x) + 2⟨Ax, h⟩ + o(∥h∥)
x
donc ∇f (x) = 2Ax. On s’intéresse maintenant à la restriction de cette fonction à la
Tx S = Rn−p × De
x ϕ(R
n−p
)
sphère de l’Exemple 3.1.16. Comme elle est compacte, f y admet des extrema globaux,
Il s’agit d’un sous-espace affine de dimension n − p. donc locaux. En particulier, f a au moins un point critique. D’après l’Exemple 3.1.21,
en un tel point e
x, ∇f (e
x) doit être orthogonal à l’espace tangent, donc colinéaire au
Dans la suite, nous oublierons l’aspect affine et appellerons par abus Tx S l’espace vecteur e
x. Autrement dit, il existe λ ∈ R tel que
tangent à S au point x.
Remarque 3.1.19. On sera peut-être gêné de ce que la définition précédente dépend de 2Ae
x = λe
x.
ϕ, alors qu’elle est sensée décrire un objet géométrique associé à la sous-variété. Évi- Ainsi, nous venons de prouver que toute matrice symétrique a un vecteur propre, ce
demment, il s’agit d’un faux problème dans la mesure où l’espace tangent ne dépend qui par récurrence montre que toute matrice symétrique est diagonalisable.
pas vraiment du choix de ϕ, mais encore faut-il le démontrer. Ceci est fait dans l’Ap-
pendice C, mais le résultat ci-dessous montre déjà que dans le cas d’une sous-variété
définie par des fonctions g1 , · · · , gp , l’espace tangent ne dépend que des gradients de ces Condition du second ordre
fonctions au point considéré.
Nous avons maintenant à notre disposition un analogue du Théorème 2.2.5 qui
Proposition 3.1.20. L’espace tangent est l’orthogonal de l’espace engendré par les gradients nous permet de localiser les extrema potentiels, mais qu’en est-il du Théorème 2.3.19
des fonctions gi . qui permet de déterminer la nature des points critiques liés ? Il s’avère qu’on a aussi un
résultat analogue et, bien que l’énoncé soit long, il s’agit de la façon la plus naturelle
Démonstration. Considérons le sous-espace vectoriel d’étendre le résultat du Théorème 2.3.19.
Théorème 3.1.23 (Condition suffisante d’extremum sous contrainte) Soit f :
t
V = ξ ∈ Rn | (ξ1 , · · · , ξn−m ) = De
x,2 g
−1
x,1 (g) (ξn−m+1 , · · · , ξn ) .
◦ De
U → R une fonction de classe C 2 , soient g1 , · · · , gm : U → R des fonctions également
de classe C 2 . Soit e
x un point de l’ensemble
introduit dans la démonstration du Théorème 3.1.9. Il est engendré par les gradients
x, donc il suffit 6 de montrer que E est orthogonal à Tx S. Soit
des fonctions gi au point e S = {x ∈ U | gi (x) = 0 pour tout 1 ⩽ i ⩽ m}
n−p
donc ξ ∈ E et χ ∈ R . Alors,
pour lequel il existe λ1 , · · · , λm ∈ R tels que
ξ, (χ, De
x ϕ(χ)) = ⟨(ξ1 , · · · , ξn−m ), χ⟩ + (ξn−m+1 , · · · , ξn ), De
x ϕ(χ)
t m
−1
X
= ⟨(ξ1 , · · · , ξn−m ), χ⟩ − De x,2 g ◦ De x,1 (g) (ξn−m+1 , · · · , ξn ), χ ∇f (e
x) = λi ∇gi (e
x).
i=1
= 0.
Si la famille de vecteurs
■ ∇g1 (e
x), · · · , ∇gn (e
x)
6. Pour des raisons de dimension.
– 79 – – 80 –
3.1. Égalité Chapitre 3. Les contraintes
est libre et si la forme quadratique En évaluant cette égalité au point e x et en factorisant on conclut alors que
m
n m n
2
X
2 ∂2 fe X ∂2 f X X ∂2 gp ∂Φ
ℓ ∂Φ
Q = De
xf − λi De
x gi = (e
x) − λp (e
x) x) k (e
(e x).
∂xj ∂xi
i=1
∂xℓ ∂xk ∂xℓ ∂xk ∂xj ∂xi
k,ℓ=1 p=1 k,ℓ=1
∂2 fe
n
X ∂2 f
! n
∂Φℓ ∂Φk X ∂f
! 2
∂ Φk Or, puisque V est engendré par les gradients des fonctions gi , on a 9
= ◦Φ + ◦Φ .
∂xj ∂xi ∂xℓ ∂xk ∂xj ∂xi ∂xk ∂xj ∂xi m
\
k,ℓ=1 k=1
V⊥ = x)⊥
∇gi (e
Considérons maintenant, pour 1 ⩽ p ⩽ m, la fonction gp ◦ Φ. La même formule que i=1
m
ci-dessus est valable pour les dérivées partielles secondes de gp ◦Φ, mais cette fonction \
est identiquement nulle par définition de Φ. Par conséquent, on a = ker(De
x gi )
i=1
n n
∂2 gp
! 2
X ∂gp ∂ Φk X ∂Φℓ ∂Φk = E,
◦Φ =− ◦ Φ .
∂xk ∂xj ∂xi ∂xℓ ∂xk ∂xj ∂xi
k=1 k,ℓ=1 ce qui conclut la preuve. ■
Nous pouvons maintenant faire appel à nouveau au lien entre le gradient de f et ceux Remarque 3.1.24. On peut également démontrer un analogue de la Proposition 2.3.20 :
des contraintes pour écrire s’il y a un maximum local sous contrainte, alors la forme quadratique Q doit être posi-
n n X m
tive sur E, et s’il s’agit d’un minimum alors elle doit être négative. Adapter la démons-
X ∂f ∂2 Φk X ∂gp ∂2 Φk tration est un bon exercice dont nous ne voudrions priver personne en en donnant la
◦Φ × = λp ◦Φ ×
∂xk ∂xj ∂xi ∂xk ∂xj ∂xi solution.
k=1 k=1 p=1
m n
∂gp
! 2 7. En effet, si A est un matrice symétrique et M une matrice quelconque, et si ⟨Aξ, ξ⟩ > 0 pour tout
X X ∂ Φk ξ ∈ Im(M), alors pour tout ξ ∈ Rn on a ⟨M t AMξ, ξ⟩ = ⟨AMξ, Mξ⟩ > 0.
= λp ◦Φ
∂xk ∂xj ∂xi 8. Rappelons que pour toute application linéaire T : Rn1 → Rn2 , on a Im(T ) = Ker(T t )⊥ . En effet, si
p=1 k=1
x ∈ Im(T ) et y ∈ Ker(T t )⊥ , alors x = T (z) et donc ⟨x, y⟩ = ⟨T (z), y⟩ = ⟨z, T t (y)⟩ = 0. Réciproquement, si
m n
∂2 gp
X X ∂Φℓ ∂Φk y ∈ Im(T )⊥ , alors pour tout z ∈ Rn1 on a ⟨z, T t (y)⟩ = ⟨T (z), y⟩ = 0, donc T t (y) = 0.
=− λp ∂x ∂x ◦ Φ ∂x ∂x
9. Nous utilisons ici le résultat suivant d’algèbre linéaire : Si un sous-espace vectoriel V ⊂ Rn est
ℓ k j i
p=1 engendré par des vecteurs v1 , · · · , vd , alors V ⊥ = di=1 vi⊥ . En effet, si x ∈ V ⊥ , alors en particulier ⟨x, vi ⟩ = 0
T
k,ℓ=1
pour tout 1 ⩽ i ⩽ d. Réciproquement si x ∈ i=1 vi et y ∈ V , alors y = di=1 λi vi , donc
Td P
qui donne finalement
d
X
n m n
∂2 gp
∂2 fe ∂2 f ⟨x, y⟩ = λi ⟨x, vi ⟩ = 0.
!
X ∂Φℓ ∂Φk X X ∂Φℓ ∂Φk
= ◦Φ − λp ◦ Φ ∂x ∂x .
i=1
∂xj ∂xi ∂xℓ ∂xk ∂xj ∂xi ∂x ∂x
ℓ k j i
k,ℓ=1 p=1 k,ℓ=1
– 81 – – 82 –
3.2. Inégalités Chapitre 3. Les contraintes
Le Théorème 3.1.23 n’est pas d’un emploi aisé, puisqu’il faut réussir à comprendre • Sinon il est atteint sur le bord et on peut essayer d’utiliser le Théorème 3.1.9.
la forme quadratique donnée par les multiplicateurs de Lagrange sur l’espace ker(Dex g)
qui peut être ardu à décrire. Nous ne donnerons qu’un exemple, dans lequel les choses Cette stratégie fonctionne dans certains cas, mais peut se heurter à plusieurs pro-
se passent sympathiquement, et qui est le prolongement de l’Exemple 3.1.22. blèmes. En particulier, décrire le bord par des contraintes d’égalité n’est pas toujours
une bonne idée. En effet, imaginons par exemple que nous ayons trois contraintes
Exemple 3.1.25. Soit A ∈ Mn (R) une matrice symétrique et f : Rn → R la fonction
définie par • h1 (x, y) = x ⩽ 0 ;
f (x) = ⟨Ax, x⟩.
• h2 (x, y) = y ⩽ 0 ;
Nous avons vu à l’Exemple 3.1.22 que tout extremum local de f sur la sphère
• h3 (x, y) = x + y + 1 ⩽ 0.
S = {x ∈ Rn | ∥x∥ = 1}
et qu’un extremum local est atteint en un point e x tel que h1 (e
x) = 0 = h2 (e
x) mais h3 (e
x) <
correspond à un vecteur propre. Soit donc e x un tel vecteur propre et λ la valeur propre 0. Les vecteurs ∇h1 (x, y) = (1, 0) et ∇h2 (x, y) = (0, 1) sont biens libres en tout point, mais
associée, qui n’est autre que le multiplicateur de Lagrange correspondant. En posant
g(x) = ∥x∥2 , on a ∇h3 (x, y) = ∇h1 (x, y) + ∇h2 (x, y)
2 2
Dex g(h, h) = 2∥h∥ . donc si l’on cherche simplement les points critiques liées sous les conditions h1 , h2 , h3 =
2
D’autre part, puisque ∇f (x) = 2Ax, on a De 0, on ne peut appliquer le Théorème 3.1.9 et à raison puisqu’il n’y aura même pas
x f (h, h) = ⟨2Ah, h⟩. Ainsi,
nécessairement de solution. Nous avons par conséquent besoin d’une façon efficace
2 2 de “tester” les différentes combinaisons de contraintes qui s’annulent ou non en un
x f (h, h) − λDe
De x g(h, h) = 2⟨(A − λIn )h, h⟩.
potentiel extremum, et c’est ce que nous allons maintenant développer.
La matrice A′ = A − λIn est symétrique – donc diagonalisable en base orthonormée – et
ses valeurs propres sont les nombres de la forme µ−λ, où µ est une valeur propre de A.
3.2.1 Plus fort que Lagrange
On constate ici que A′ n’est jamais définie positive, puisque λ − λ = 0 est valeur propre.
C’est pourquoi la restriction à E dans l’énoncé du Théorème 3.1.23 est essentielle.
Pour ce faire, il va nous falloir introduire un peu de vocabulaire. On considère
Ainsi, pour que le Théorème 3.1.23 s’applique, il faut que tous les vecteurs propres toutjours une fonction f : U → R, mais cette fois-ci on cherche ses extrema dans une
orthogonaux à x correspondent à une valeur propre µ telle que µ − λ > 0. Autrement partie de Rn de la forme 10
dit, il faut λ soit la plus petite valeur propre de A et soit de multiplicité 1. Alors, f a un
minimum local strict en x et on peut montrer que réciproquement, si f a un minimum D = {x ∈ U | hi (x) ⩽ 0 pour tout 1 ⩽ i ⩽ p} ,
local en x alors λ doit être la plus petite valeur propre. On établit de même que f a un pour des fonctions h1 , · · · , hp : U → R. Ces conditions sont plus larges que celles des
maximum local strict si λ est la plus grande valeur propre et est de multiplicité 1. contraintes d’égalité, donc il est a priori “plus difficile” d’être un extremum dans ce
cas. Cela signifie que s’il existe un analogue du Théorème 3.1.9 pour les contraintes
d’inégalité, il doit y avoir des conditions supplémentaires sur les multiplicateurs. Et
3.2 Inégalités de fait, il existe une condition assez simple pour cela, que nous allons maintenant
donner. Pour plus de simplicité, nous l’exprimons dans le cas d’un minimum. Pour un
Tous les animaux sont égaux maximum, il suffira bien sûr de l’appliquer à la fonction −f .
mais certains sont plus égaux que d’autres.
G. Orwell, La ferme des animaux
Avant de commencer néanmoins, nous allons avoir besoin d’une notion pratique.
Comme nous l’avons évoqué, l’un des enjeux des contraintes d’égalités est de détermi-
ner quelles inégalités sont strictement vérifiées ou non aux extrema. Pour en parler, un
Le problème évoqué au paragraphe 1.1.2 du Chapitre 1 ne comportait pas que des peu de vocabulaire s’impose.
contraintes d’égalité. De fait, ces dernières étaient linéaires et pouvaient donc directe-
Définition 3.2.1. Soient h1 , · · · , hp : U → R des fonctions et x ∈ U . On dit que la
ment être utilisées pour réduire le nombre de variables. Les autres contraintes étaient
contrainte hi est active au point x si hi (x) = 0. Autrement, on dit que la contrainte
données par des inégalités. Il serait donc utile pour nous d’avoir un résultat similaire
hi est inactive.
au Théorème 3.1.9 permettant de détecter les extrema sous contraintes d’inégalité.
Une stratégie possible pour aborder des contraintes d’inégalité est la suivante : le Intuitivement, si une fonction f admet un extremum en un point e x, seules les
domaine défini par les inégalités est la réunion disjointe de son intérieur - qui est contraintes qui sont actives en e
x devraient être prises en compte. En effet, si hj (e
x) < 0,
ouvert - et de son bord. En admettant qu’une fonction admette un extremum local sur alors la même inégalité est vraie dans un voisinage de e x, et par conséquent f a tou-
ce domaine, nous avons donc deux possibilités : jours un extremum local si l’on retire la j-ième contrainte. Montrons cela proprement,
en remarquant que quitte à renuméroter les fonctions, on peut supposer que c’est la
première contrainte qui est inactive.
• S’il est atteint sur l’intérieur, on peut l’étudier à l’aide des résultats des Para-
graphes 2.2 et 2.3 du Chapitre 2 ; 10. Il est clair que toute inégalité est équivalente à une inégalité de la forme h(x) ⩽ 0.
– 83 – – 84 –
3.2. Inégalités Chapitre 3. Les contraintes
que f (y) ⩾ f (e
x). Autrement dit, f a un minimum local en e
x sous les contraintes hj (x) ⩽ 0 Si p = 1, u , 0 puisque sinon il serait égal à 0 × v1 . Donc, il existe x ∈ Rn (par
pour tout 2 ⩽ j ⩽ p. ■ exemple x = −u) tel que ⟨u, x⟩ < 0. Si ⟨v1 , x⟩ ⩾ 0, la preuve est terminée. Supposons
donc ⟨v1 , x⟩ < 0 et posons
Nous pouvons maintenant établir notre critère de localisation des extrema sous ⟨u, x⟩
u′ = u − v .
contraintes d’inégalité. Pour alléger la présentation, nous n’énoncerons le résultat que ⟨v1 , x⟩ 1
dans le cas d’un minimum. Pour un maximum, il suffira de se souvenir qu’un maxi- On a u ′ , 0, sinon u serait un multiple positif de v1 . Il existe donc x′ tel que ⟨u ′ , x′ ⟩ < 0.
mum de f n’est autre qu’un minimum de −f . Pour conclure, il suffit de poser
Proposition 3.2.3. Soit f : U → R une fonction de classe C 1 , h1 , · · · , hp : U → R des fonc- ⟨v1 , x′ ⟩
y = x′ − x.
tions également de classes C 1 et e
x ∈ U . On suppose qu’il existe ξ0 ∈ Rn tel que pour tout ⟨v1 , x⟩
x,
1 ⩽ j ⩽ p tel que la contrainte hj est active au point e
En effet, on a alors d’une part
D E
∇hj (e
x), ξ0 < 0. ⟨v1 , x′ ⟩
⟨u, y⟩ = ⟨u, x′ ⟩ − ⟨u, x⟩
⟨v1 , x⟩
Si la restriction de f à D admet un minimum local en e x, alors il existe µ1 , · · · , µp ⩽ 0 tels
⟨u, x⟩
que = ⟨u ′ , x′ ⟩ + ⟨v , x′ ⟩
p
X ⟨v1 , x⟩ 1
∇f (e
x) = µj ∇hj (e
x). ⟨v , x′ ⟩
− 1 ⟨u, x⟩
j=1 ⟨v1 , x⟩
De plus, on a µj = 0 si la contrainte hj est inactive au point e
x. = ⟨u ′ , x′ ⟩
<0
La condition sur les produits scalaires est cruciale. On dit que les contraintes sont
x si un tel vecteur ξ0 existe. Quant au fait que le résultat requiert des
qualifiées en e et d’autre part
coefficients négatifs, cela provient du résultat suivant, qui est une forme simplifiée –
⟨v1 , x′ ⟩
mais suffisante pour nous – d’un résultat fondamental d’analyse convexe appelé Lemme ⟨v1 , y⟩ = ⟨v1 , x′ ⟩ − ⟨v , x⟩
⟨v1 , x⟩ 1
de Farkas 11 .
= 0.
Lemme 3.2.4. Soit u, v1 , · · · , vp ∈ Rn . Alors, une et une seule des deux propositions suivante
est vérifiée : Nous avons donc montré H1 .
– 85 – – 86 –
3.2. Inégalités Chapitre 3. Les contraintes
⟨vi , x⟩ Nous sommes maintenant armés pour démontrer notre résultat d’optimisation sous
vi′ = vi − v
⟨vp+1 , x⟩ p+1 contraintes d’inégalité.
⟨u, x⟩
u′ = u − v Démonstration de la Proposition 3.2.3. D’après le Lemme 3.2.2, on peut supposer 12 que
⟨vp+1 , x⟩ p+1
hj (e
x) = 0 pour tout 1 ⩽ j ⩽ p ou – avec la terminologie introduite plus haut – supposer
S’il existait µ1 , · · · , µp ∈ R+ tels que que toutes les contraintes sont actives. C’est la raison pour laquelle les hypothèses ne
font intervenir que les contraintes actives.
p
X Soit maintenant ϵ > 0 et ξ0 ∈ Rn tel que ⟨∇hi , ξ0 ⟩ < 0 pour tout 1 ⩽ i ⩽ p. Pour un
u′ = µi vi′ , vecteur ξ1 ∈ Rn vérifiant
i=1 ⟨∇hi , ξ1 ⟩ ⩽ 0
⟨vp+1 , x′ ⟩ Revenons maintenant à notre problème d’origine. Pour tout t ∈]0; δ[, on a
⟨vp+1 , y⟩ = ⟨vp+1 , x′ ⟩ − ⟨vp+1 , x⟩
⟨vp+1 , x⟩ f (ξ(t)) − f (e
x)
⩾ 0.
=0 t
12. On dit alors que les contraintes sont saturées en e
x.
– 87 – – 88 –
3.2. Inégalités Chapitre 3. Les contraintes
En faisant tendre t vers 0, on en déduit que Kuhn 14 et Tucker 15 en 1951 et porte donc le nom de Condition de Karush-Kuhn-
Tucker, que nous abrégerons en KKT.
∇f (e
x), ξ1 + ϵξ0 ⩾ 0.
Cette inégalité est valable pour tout ϵ > 0, donc en faisant tendre ϵ vers 0 on en déduit Théorème 3.2.6 (Condition KKT) Soit f : U → R une fonction de classe C 1 , soient
que g1 , · · · , gm , h1 , · · · , hp : U → R des fonctions également de classes C 1 et e
x ∈ D. On
∇f (e
x), ξ1 ⩾ 0. suppose que les vecteurs
∇g1 (e
x), · · · , ∇gm (e
x)
Nous pouvons maintenant appliquer le Lemme 3.2.4 à ∇f (e
x) et à la famille de vecteurs
−∇h1 (e
x), · · · , −∇hp (e
x) pour conclure. ■ forment une famille libre et qu’il existe
m
Ce résultat appelle plusieurs commentaires importants. \
ξ0 ∈ E = ker De
x gi
• La condition de qualification est plus “souple” que la condition d’indépendance i=1
linéaire des gradients du Théorème 3.1.9. En effet, elles sont vérifiées par exemple tel que pour tout 1 ⩽ j ⩽ p tel que la contrainte hj est active au point e
x,
pour deux fonctions h1 et h2 telles que ∇h1 (x) = ∇h2 (x).
D E
• La condition µj ⩽ 0 peut s’interpréter géométriquement dans le cadre des sous- ∇hj (e
x), ξ0 < 0.
variétés. Par exemple, si on a une seule contrainte d’inégalité hj (x) ⩽ 0 et que
∇hj (x) , 0 pour tout x, le signe de µj signifie que non seulement le gradient de Si f admet un minimum local en e
x sous les contraintes
f doit être orthogonal au plan tangent, mais qu’il doit de plus “entrer” dans le
domaine {x ∈ U | hj (x) ⩽ 0}. Ceci permet donc d’éliminer certains points critiques • gi = 0 pour tout 1 ⩽ i ⩽ m ;
liés qui ne peuvent correspondre à des extrema. On peut donner une interpréta-
• hj ⩽ 0 pour tout 1 ⩽ j ⩽ p ;
tion similaire avec plusieurs contraintes.
• La dernière ligne de l’énoncé peut s’écrire de façon plus concise alors il existe λ1 , · · · , λm ∈ R et µ1 , · · · , µp ⩽ 0 tels que
µj hj (e
x) = 0. m
X p
X
Cette condition est parfois dite de complémentarité et elle est essentielle pour ∇f (e
x) = λi ∇gi (e
x) + µj ∇hj (e
x).
l’utilisation du résultat. En effet, elle permet de “tester” la nullité ou non des i=1 j=1
multiplicateurs pour voir quelles contraintes peuvent être actives et donc quels
gradients peuvent apparaître avec un coefficient non nul (un exemple est donné De plus, µj = 0 si la contrainte hj est inactive au point e
x.
au Paragraphe 3.2.2 ci-dessous).
Remarque 3.2.5. Nous pourrions être tentés de jouer les malins et d’utiliser la Pro- Démonstration. En nous inspirant des notations de la preuve de la Proposition 3.2.3,
position 3.2.3 pour obtenir une preuve plus simple du Théorème 3.1.9. En effet, une posons χ
e = (e xn−m ) et pour ξ1 ∈ E et t > 0,
x1 , · · · , e
contrainte d’égalité g = 0 est équivalente à deux contraintes d’inégalité, à savoir g ⩽ 0
et g ⩾ 0. Néanmoins, de telles contraintes ne seront jamais qualifiées. En effet, si ξ(t) = χ
e + t(ξe1 + ϵξe0 ),
ξ0 ∈ Rn , on ne peut avoir à la fois ⟨∇g(e
x), ξ0 ⟩ < 0 et ⟨∇(−g)(e
x), ξ0 ⟩ < 0 puisque ces deux où ξei∈ Rnest le vecteur formé des n−m premières coordonnées de ξi pour i = 0, 1. Pour
nombres sont opposés. Ainsi, la qualification des contraintes est essentielle et restreint construire maintenant une fonction dont les valeurs sont des vecteurs satisfaisant les
l’utilisation du résultat à des contraintes d’inégalité non-triviales. contraintes d’égalité, il suffit de poser
Pour remarquable qu’il soit, le résultat précédent est insuffisant. En effet, idéale-
ζ(t) = (ξ(t), ϕ(ξ(t)) ∈ Rn .
ment nous voulons pouvoir gérer à la fois des contraintes d’égalité et d’inégalité, ce
qu’on appelle parfois – dans un grand élan d’imagination – des contraintes générales. Attention cependant : cette expression n’a pas de sens pour tout t. Néanmoins, comme
Pour cela, on ne peut juxtaposer le Théorème 3.1.9 et la Proposition 3.2.3, il faut com- ξ(0) = ex et que t 7→ ξ(t) est continue car linéaire, il existe δ > 0 tel que pour t ∈ [0; δ[,
prendre comment ils interagissent. Heureusement, le Théorème 3.1.23 nous donne une ξ(t) ∈ V et la fonction ζ est alors bien définie sur [0; δ[.
idée : la bonne solution devrait être d’exprimer les conditions de la Proposition 3.2.3
Il nous faut maintenant vérifier que pour t suffisamment petit, ζ(t) vérifie les con-
non pas sur tout l’espace mais sur le sous-espace vectoriel E1 qui est le noyau de la
traintes d’inégalité. Nous allons pour cela distinguer suivant qu’elles sont actives ou
différentielle de la fonction g encodant les contraintes d’égalité.
non. Si hj (e
x) < 0, alors il existe δj tel que hj (x) < 0 pour tout x ∈ B(e
x, δj ). Par continuité
De fait, cette solution est la bonne. Elle fut exprimée pour la première fois par
Karush 13 en 1939, mais son résultat ne fut pas très remarqué. Il fut redécouvert par 14. Harold W. Kuhn (1925–2014) : mathématicien canadien, spécialiste entre autres de théorie des
jeux. On lui doit une étude détaillée d’une version simplifiée du jeu de Poker, appelé Poker de Kuhn.
13. William Karush (1917–1997) : mathématicien américain, il a obtenu les conditions d’extrema sous 15. Albert W. Tucker (1905–1995) : mathématicien canadien au multiples centres d’intérêts (géomé-
contrainte d’inégalités dans son mémoire de Master, qu’il n’a pas publié. Il a travaillé plus tard pour le trie différentielle, théorie des jeux, optimisation). La Mathematical Optimisation Society décerne tous les
Projet Manhattan avant de devenir un militant pacifiste. trois ans un prix en son honneur.
– 89 – – 90 –
3.2. Inégalités Chapitre 3. Les contraintes
= t⟨∇hj (e
x), ξ1 + ϵξ0 ⟩ + o(t). ∂R
!
∂R
!
ξ1 C ′ (e
x) − (e a ) + ξ2 1 −
x,e (e a) < 0
x,e
Le même raisonnement que dans la démonstration de la Proposition 3.2.3 montre alors ∂x ∂a
que si ⟨∇hj (e
x), ξ1 ⟩ ⩽ 0, pour t assez petit on aura hj (ζ(t)) ⩽ 0. −ξ2 < 0
Nous pouvons maintenant reprendre exactement le même raisonnement que dans
la démonstration de la Proposition 3.2.3 pour conclure que La première équation peut s’écrire
! !
⟨∇f (e
x), ξ1 ⟩ ⩾ 0. ∂R ∂R
ξ1 C ′ (e
x) − (e a) < ξ2
x,e (e a) − 1
x,e
∂x ∂a
Soit PE la projection orthogonale sur E. On a alors
D E D E
x), ξ1 = PE ∇hj (e
∇hj (e x ) , ξ1 & x), ξ1 = PE (∇f (e
∇f (e x)) , ξ1 , qui donne en divisant (puisque ξ2 , 0)
– 91 – – 92 –
3.2. Inégalités Chapitre 3. Les contraintes
tion qui nous intéresse, c’es-à-dire la fonction −R. Alors, il existe µ1 , µ2 ⩽ 0 tels que est libre, où \
E= ker(Dx gi )
∂R ∂R
− (e a) = −µ1 (e
x,e a) + µ1 C ′ (x)
x,e 1⩽i⩽m
∂x ∂x
∂R ∂R Si l’on oublie les projections sur l’espace E, il s’agit en fait de la condition du Théo-
− (e a) = −µ1 (e
x,e a) + µ1 − µ2
x,e
∂a ∂a rème 3.1.9. Comme nous l’avions évoqué plus haut, les conditions de la Proposition
µ1 (p0 − R(e a) + C(e
x,e a) = 0
x) + e 3.2.3 sont moins fortes que la qualification linéaire des contraintes. Néanmoins, il ar-
−µ2 a = 0 rive souvent que les contraintes vérifient les conditions de qualification linéaire, qui
sont plus simple à établir. Pour le démontrer, nous allons nous appuyer sur un résultat
classique d’algèbre linéaire dû à Gram 16 , que nous allons d’abord démontrer au cas où
Considérons tout d’abord la seconde égalité. Elle peut s’écrire vous n’auriez pas eu le plaisir de le rencontrer sur le chemin de vos études.
µ2 − µ1 = (1 − µ1 )
∂R
(e a).
x,e Proposition 3.2.8. Soient v1 , · · · , vp des vecteurs de Rn . On pose Mij = ⟨vi , vj ⟩ et on note
∂a M ∈ Mp (R) la matrice donnée par ces coefficients. Si la famille de vecteurs est libre, alors M
Supposons que la dérivée partielle de R par rapport à a est toujours strictement posi- est inversible.
tive, ce qui paraît raisonnable (plus de publicité augmente les ventes). Alors, comme
1 − µ1 > 0, on a µ2 − µ1 > 0 et puisque µ1 , µ2 ⩽ 0 on doit finalement avoir µ1 < 0. Mais Démonstration. Notons
alors, la troisième condition donne A= v1 · · · vp ∈ Mpn (R)
R(e a) − C(e
x,e x) − e
a = p0 . la matrice dont les colonnes sont les vecteurs. On a alors l’égalité M = At A :
n
Autrement dit, s’il y a un maximum il est atteint quand le profit est minimal ! X
(At A)ij = Aki Akj
On peut même dire un peu plus. En effet, le coût doit être une fonction strictement k=1
croissante (plus on produit plus ça coûte) de x, donc C ′ (e
x) > 0. Comme µ1 < 0, on Xn
conclut de la première équation que = (vi )k (vj )k
k=1
∂R µ1
(e a) =
x,e C ′ (x) > 0. = ⟨vi , vj ⟩
∂x µ1 − 1
= Mij .
Ainsi, le revenu marginal est strictement positif à l’optimum, ce qui signifie que pro-
duire un peu plus que e x augmenterait le revenu. Ceci peut paraître surprenant puis- Il suffit donc de montrer que si la famille est libre, alors ker(M) = ker(At A) = {0}. Et de
qu’on est sensé être à un maximum. Néanmoins, si on note P (x, a) le profit, on a fait, si x ∈ ker(At A), alors
!
∂P ∂R 0 = ⟨At Ax, x⟩
(1 + µ1 ) (e a) = (1 + µ1 )
x,e (e a) − C ′ (x)
x,e
∂x ∂x = ⟨Ax, Ax⟩
= µ1 C ′ (x) − (1 + µ1 )C ′ (x)
= ∥Ax∥2 ,
= −C ′ (x)
< 0. donc x ∈ ker(A). Cela signifie que
Ainsi, produire plus réduirait le profit, le faisant passer sous le seuil imposé. C’est pour n
X
cela qu’on a bien un maximum quand les contraintes sont prises en compte. xi vi = 0,
i=1
3.2.3 Qualification linéaire des contraintes donc que x = 0. Ainsi, ker(At A) = 0, ce qu’il fallait démontrer. ■
L’exemple précédent montre que vérifier la qualification des contraintes n’est pas Nous pouvons maintenant montrer que la qualification linéaire des contraintes im-
toujours chose aisée. Souvent, il est possible d’aller plus vite en vérifiant une condition plique la qualification au sens de la Proposition 3.2.3.
plus forte, dite de Qualification linéaire des contraintes.
Définition 3.2.7. Soient g1 , · · · , gm , h1 , · · · , hp : U → R des fonctions de classes C 1 et x ∈ Proposition 3.2.9. Si la qualification linéaire des contraintes est vérifiée en un point x,
U tel que gi (x) = 0 pour tout 1 ⩽ i ⩽ m et hj (x) ⩽ 0 pour tout 1 ⩽ j ⩽ p. On dit que la alors les contraintes sont qualifiées en x au sens de la Proposition 3.2.3.
qualification linéaire des contraintes est vérifiée au point x si la famille de vecteurs 16. Jorgen Pedersen Gram (1850–1916) : mathématicien danois qui, en plus de ses contributions im-
portantes à l’algèbre linéaire comme le procédé d’orthonormalisation qui porte son nom, a travaillé la
PE (∇h1 (x)), · · · , PE (∇hp (x)) majeure partie de sa vie dans des compagnies d’assurance.
– 93 – – 94 –
3.3. Le cas linéaire Chapitre 3. Les contraintes
Démonstration. Posons, pour 1 ⩽ j ⩽ p, wj = PE (∇hj (x)). Il suffit maintenant de trouver de sorte que les contraintes peuvent s’écrire Gx − c = 0 et Hx − d ⩽ 0, l’inégalité étant
un vecteur ξ0 ∈ E tel que ⟨wi , ξ0 ⟩ = −1. Pour ce faire, nous allons le chercher sous la comprise coordonnée par coordonnée. La condition ci-dessus devient alors
forme particulière
p
X u = Gt λ + H t µ.
ξ0 = αj wj .
j=1
Cette condition, réunie aux contraintes, s’avère être en fait suffisante pour l’exis-
La condition s’écrit alors, pour tout 1 ⩽ j ⩽ p, tence d’un extremum. Autrement dit, le Théorème 3.2.6 devient non plus un critère
p
X mais une équivalence dans le cas linéaire.
αj ′ ⟨wj ′ , wj ⟩ = −1.
j ′ =1
Théorème 3.3.1 (KKT pour les problèmes linéaires) Un point e x ∈ Rn réalise un
minimum global d’une fonction linéaire f sous les contraintes linéaires gi = 0 et
Si M ∈ Mp (R) est la matrice de coefficients Mjj ′ = ⟨wj ′ , wj ⟩ et si η ∈ Rp est le vecteur hj ⩽ 0 si et seulement s’il existe λ ∈ Rm et µ ∈ Rp− tels que pour tout 1 ⩽ j ⩽ p,
dont toutes les coordonnées sont égales à −1, alors l’équation devient Mα = ξ. Or,
= Gt λ + H t µ
M est la matrice de Gram de la famille de vecteurs (w1 , · · · , wp ). Comme la matrice de
u
Gram d’une famille libre est inversible, on conclut qu’un tel ξ0 existe, ce qu’il fallait
Ge
x = c
démontrer. ■
He
x ⩽ d
µ ⟨w , e
j x⟩ = µj dj
j
– 95 – – 96 –
3.3. Le cas linéaire Chapitre 3. Les contraintes
on a que hj (x) < 0 pour tout j < J et donc en particulier hj (ξ(t)) < 0 pour t ∈ [0; r[. De on a pour tout x ∈ D,
plus, pour les mêmes t, on a pour tout 1 ⩽ i ⩽ m
f (x) − f (e
x) = ⟨u, x − e
x⟩
Xm p
X
gi (ξ(t)) = ⟨vi , e
x + tξ0 ⟩ − ci = x⟩ +
λi ⟨vi , x − e µj ⟨wj , x − e
x⟩
i=1 j=1
= ⟨vi , e
x⟩ − ci + t⟨vi , ξ0 ⟩
m m p
= gi (e
x) + t⟨vi , ξ0 ⟩
X X X
= λi ⟨vi , x⟩ − x⟩ +
λi ⟨vi , e µj ⟨wj , x − e
x⟩
=0 i=1 i=1 j=1
m
X m
X p
X
= λi c i − λi ci + µj ⟨wj , x − e
x⟩
et pour tout j ∈ J, i=1 i=1 j=1
Xp
= µj ⟨wj , x − e
x⟩
hj (ξ(t)) = ⟨wj , e
x + tξ0 ⟩ − dj j=1
p p
= ⟨wj , e
x⟩ − dj + t⟨wj , ξ0 ⟩ X X
= µj ⟨wj , x⟩ − µj ⟨wj , e
x⟩
= hj (e
x) + t⟨wj , ξ0 ⟩
j=1 j=1
= t⟨wj , ξ0 ⟩ Xp
⩽ 0. = µj ⟨wj , x⟩ − µj dj
j=1
⩾ 0,
Ainsi, ξ(t) ∈ D pour tout t ∈ [0; r[.
donc f a un minimum global sous contraintes au point e
x. ■
Nous sommes maintenant proches du but. En effet, supposons que ⟨u, ξ0 ⟩ < 0. Alors,
pour t ∈ [0; r[,
3.3.2 La méthode du simplexe
f (ξ(t)) = ⟨u, e
x + tξ0 ⟩ + b Le Théorème 3.3.1 ramène le problème d’optimisation à un problème matriciel qui
= ⟨u, e
x⟩ + b + t⟨u, ξ0 ⟩ reste à résoudre, ce qui n’est pas nécessairement facile. Ceci sort du cadre de ce texte
et nous n’en parlerons pas, mais il existe des méthodes pour aborder ce genre de pro-
= f (e
x) + t⟨u, ξ0 ⟩ blème. Notons cependant qu’il était plus ou moins intuitif dès le début qu’il s’agissait
< f (e
x), d’un problème d’algèbre linéaire. Plus précisément, les contraintes d’inégalité défi-
nissent des demi-plans et on cherche donc à optimiser f sur une intersection de demi-
espaces. S’il y en a suffisamment, cette intersection est une partie bornée (et donc com-
ce qui contredit le fait que f admet un minimum local en e x. Ainsi, on doit avoir pacte) de l’espace appelée polytope. Dans ce cas, la méthode esquissée au Paragraphe
⟨u, ξ0 ⟩ ⩾ 0. Pour résumer, nous avons montrer que pour tout vecteur 1.1.2 fonctionne :
– 97 – – 98 –
3.3. Le cas linéaire Chapitre 3. Les contraintes
Le troisième point ci-dessus revient à affirmer que le bord de P , qui est l’ensemble polytope, parce que leur nombre a tendance à croître exponentiellement avec les di-
de tous les points de P qui ne sont pas dans l’intérieur de P , est la réunion des faces. mensions n et m du problème. On part donc d’un sommet arbitraire, et l’on se déplace
Puisque ce n’est pas très difficile, nous allons le démontrer. selon une arête (un segment joignant deux sommets) de façon à faire diminuer f . Ceci
est beaucoup plus facile car on n’a besoin de calculer qu’un petit nombre de valeurs.
Proposition 3.3.3. Soit P un polytope définit par des formes linéaires h1 , · · · , hp et soit ∂P Mais ce faisant, nous avons déjà éliminé une partie des sommets. Il suffit ensuite de
son bord. Alors, répéter l’opération.
[p
∂P = Fj . Sans en dire plus, revenons simplement à l’exemple du Paragraphe 1.1.2 du Cha-
j=1 pitre 1. le polytope définit par les contraintes est ici un polygone qui possède cinq som-
mets que nous noterons S1 , · · · , S5 en les numérotant en sens direct 17 depuis S1 = (0, 7).
Démonstration. Si on note F l’union des faces, on peut écrire P = Q ∪ F, où On calcule les valeurs correspondantes de F :
Alors, par continuité de hj , il existe δj > 0 tel que pour tout y ∈ B(x, δj ),
hj (x) On trouve que le minimum est atteint au point S3 = (4, 1), ce qui donne
hj (y) ⩽ hj (x) + ϵ = < 0.
2
(x1 , x2 , x3 , x4 ) = (4, 1, 0, 6)
En posant δ = minj δj , on a B(x, δ) ⊂ Q et Q est bien un ouvert.
Si maintenant x ∈ F et si j est tel que hj (x) = 0, on a par définition ⟨wj , x⟩ − dj = 0. et fmin = 62, comme affirmé.
Mais alors, pour tout δ > 0, on a
Concluons en ajoutant que le calcul différentiel nous apprend comment approcher
wj une fonction donnée par une fonction linéaire (sa différentielle). On peut donc imagi-
y = x+δ ∈ B(x, δ)
∥wj ∥2 ner, dans un problème général d’optimisation sous contraintes, d’approcher à la fois f
et ses contraintes par des fonctions linéaires afin de se ramener à un problème affine.
et Il s’agit de la technique de ... linéarisation !
⟨wj , y⟩ − dj = ⟨wj , x⟩ − dj + δ
> 0.
3.4 Dualité
Autrement dit, B(x, δ) n’est jamais contenue dans P , ce qui signifie que x n’est pas inté-
rieur à P . ■
Le pathétique de l’amour consiste dans une dualité insurmontable des êtres.
E. Levinas, Le temps et l’autre
Expliquons maintenant comment ces notions élémentaires permettent de dévelop-
per une méthode efficace de recherche d’extremum. Il suffit de remarquer qu’une face
d’un polytope est à nouveau un polytope. De plus, on peut voir Fj comme un poly-
tope de l’espace ker(hj ), qui est de dimension n − 1. Ainsi, en itérant le raisonnement Avant de poursuivre notre étude, faisons une pause pour reformuler ce que nous
présenté un peu plus haut, on voit que tout extremum doit être atteint sur une face de avons démontré. Nous avons vu que pour étudier les points critiques sous contraintes,
dimension 0 ... ce qu’on appelle un sommet du polytope. Résumons ceci : il fallait faire intervenir des scalaire λ1 , · · · , λm et µ1 , · · · , µp , appelés multiplicateurs de
Lagrange. On peut synthétiser cela à l’aide d’une seule fonction, ce qui permet d’expri-
Théorème 3.3.4 (Solution-sommet) Étant donné un problème d’optimisation li- mer les résultats de façon plus compacte. Nous appellerons dans cette partie problème
néaire, s’il existe une extremum alors il est atteint sur un sommet. d’optimisation sous contraintes la donnée d’une fonction f : U → R qu’on cherche à mi-
nimiser sous des contraintes d’égalité données par des fonctions g1 , · · · , gm : U → R et
Ceci ramène le problème à un ensemble fini, et nous voilà donc dans le giron des contraintes d’inégalité données par des fonctions h1 , · · · , hp : U → R.
de l’optimisation combinatoire. En particulier, on dispose de la Méthode du simplexe.
L’idée est la suivante : on ne peut pas calculer la valeur de f sur tous les sommets du 17. Le sens trigonométrique direct est le sens inverse des aiguilles d’une montre.
– 99 – – 100 –
3.4. Dualité Chapitre 3. Les contraintes
Définition 3.4.1. Le Lagrangien d’un problème d’optimisation sous contraintes est la f ∗ (λ, µ) = inf L(x, λ, µ)
x∈U
fonction L : U × Rm × Rp− → R définie par
qu’on va chercher à maximiser.
L(x1 , · · · , xn , λ1 , · · · , λm , µ1 , · · · , µp ) = f (x1 , · · · , xn ) Définition 3.4.2. Le problème ci-dessus est appelé problème dual du problème d’ori-
Xm p
X gine. Réciproquement, le problème d’origine est appelé problème primal.
− λi g(x1 , · · · , xn ) − µj hj (x1 , · · · , xn ).
i=1 j=1
Nous n’avons a priori pas fait grand chose. En fait, l’espoir dans la définition du pro-
blème dual est que sa résolution puisse nous donner des informations sur le problème
primal. Il s’avère – et c’est tout à fait remarquable – que c’est le cas ! La manifestation
On peut alors reformuler le Théorème 3.1.9 de la façon suivante : si f admet un
la plus simple de ce phénomène est la suivante :
minimum local sous contraintes au point e
x, alors il existe (λ1 , · · · , λm ) et (µ1 , · · · , µp ) tels
que L a un point critique au point Proposition 3.4.3 (Dualité de Lagrange faible). Pour tous x, λ et µ satisfaisant les
contraintes, on a
(e xn , λ1 , · · · , λm , µ1 , · · · , µp ).
x1 , · · · , e f (x) ⩾ f ∗ (λ, µ).
On remarquera qu’être un point critique pour L correspond à n + m + p équations don- x, et si f ∗ admet un
En particulier, si f admet un minimum local sous contraintes au point e
nées par chaque dérivée partielle, ce qui semble surdéterminer le problème. Il n’en est maximum local sous contraintes en (λ,
eµ e), alors
en fait rien, car
x) ⩾ f ∗ (λ,
f (e eµ e).
∂L
= gi De plus, s’il y a égalité alors les deux extrema sont globaux.
∂λi
∂L
= hj Démonstration. Comme x satisfait les contraintes, on a gi (x) = 0 pour tout 1 ⩽ i ⩽ m,
∂µj hj (x) ⩽ 0 pour tout 1 ⩽ j ⩽ p. Comme de plus µj ⩽ 0 on a
Ainsi, l’annulation des dérivées partielles par rapport aux coordonnées λi et µj traduit m
X p
X
simplement les contraintes du problème (n’oublions pas que hj (e x) = 0 si µj , 0). f (x) = L(x, λ, µ) + λi gi (x) + µj hj (x)
La formulation à l’aide du Lagrangien présente un avantage : elle met en lumière i=1 j=1
p
un nouveau problème d’optimisation lié au précédent. Pour le voir remarquons que X
pour tout x ∈ U , = L(x, λ, µ) + µj hj (x)
j=1
m p
X X ⩾ L(x, λ, µ)
sup L(x, λ, µ) = f (x) − inf p λi g(x) + µj hj (x) .
m p
λ∈R ,µ∈R− λ∈Rm ,µ∈R− ⩾ f ∗ (λ, µ).
i=1 j=1
La seconde partie de l’énoncé suit immédiatement.
La borne inférieure vaut souvent −∞. Cependant, si x ∈ D, alors gi (x) = 0 et hj (x) ⩽ 0,
donc comme µj ⩽ 0, la borne inférieur vaut tout simplement 0. Autrement dit, pour Quant à la troisième, s’il existait e
x′ tel que f (e
x′ ) < f (e
x), alors on aurait
tout x ∈ U et en notant comme précédemment D l’ensemble des points vérifiant les
contraintes, f ∗ (λ,
eµ e) ⩽ f (ex′ )
(
f (x) si x ∈ D < f (e
x)
sup L(x, λ, µ) =
m p +∞ si x < D = f ∗ (λ,
eµ e),
λ∈R ,µ∈R−
– 101 – – 102 –
3.4. Dualité Chapitre 3. Les contraintes
3.4.2 Dualité linéaire Proposition 3.4.4 (Bidualité pour les problèmes linéaires). Si b = 0, alors le problème
dual du problème dual d’un problème linéaire est le problème primal.
Tout ceci est bien beau, mais pour être utile il faut que le problème dual soit plus
facile à résoudre que le problème primal. Et c’est bien le cas ! En effet, le problème dual Pour conclure, nous allons utiliser la caractérisation des solutions d’un problème
est toujours un problème de maximisation concave ou de façon équivalente – en chan- linéaire donnée dans le Théorème 3.3.1 pour améliorer la Proposition 3.4.3.
geant tous les signes – de minimisation convexe, et il existe pour ce type de problème
des méthodes très efficaces. Ceci fera l’objet du prochain chapitre, mais en attendant, Théorème 3.4.5 (Dualité de Lagrange forte pour les problèmes linéaires) Le
nous allons regarder d’un peu plus près le cas où le problème d’origine est linéaire. saut de dualité d’un problème linéaire est nul. Autrement dit, si le problème pri-
Considérons donc une fonction linéaire f : x 7→ ⟨u, x⟩ + b que l’on cherche à minimiser mal a une solution, alors il existe e
x, λ,
eµ e tels que
sous les contraintes Gx = c et Hx ⩽ d, où G ∈ Mmn (R) et H ∈ Mpn (R) et l’inégalité est
comprise coordonnée par coordonnée. Le Lagrangien du problème est x) = f ∗ (λ,
f (e eµ e).
L(x, λ, µ) = f (x) + b − ⟨λ, Gx − c⟩ − ⟨µ, Hx − d⟩ De plus, on peut prendre pour λ,
eµ e les multiplicateurs associés à e
x.
= ⟨λ, c⟩ + ⟨µ, d⟩ + ⟨u − Gt λ − H t µ, x⟩ + b
Il faut maintenant minimiser cette quantité sur x. Or, si u − Gt λ − H t µ , 0, alors le Démonstration. Soit e x ∈ D un point auquel f admet un minimum (nécessairement glo-
minimum vaut −∞. Ainsi, la fonction duale ne sera bien définie que si u = Gt λ + H t µ. bal). Alors, on sait par le Théorème 3.3.1 qu’il existe λ
e et µ
e tels que
Dans ce cas, le terme en x vaut 0. On conclut que le problème dual consiste à maximiser
la fonction f ∗ : (λ, µ) 7→ ⟨λ, c⟩ + ⟨µ, d⟩ + b sous les contraintes u = Gt λ
e+ H tµ
e
t t
u = G λ+H µ
et ⟨e x⟩ = ⟨e
µ, He µ, d⟩ par complémentarité. On calcule alors
µ⩽0
D E
Autrement dit : le dual d’un problème linéaire est encore un problème linéaire ! x) = Gt λ
f (e e+ H tµ x +b
e, e
Mais alors, il est légitime de s’interroger sur son rapport au problème initial. Pour = ⟨λ,
e Gex⟩ + ⟨e
µ, Hex⟩ + b
cela, ramenons-nous à un problème de minimisation en gardant les contraintes mais = ⟨λ,
e c⟩ + ⟨e
µ, Hex⟩ + b
en considérant la fonction −f ∗ . Le nouveau Lagrangien s’écrit (avec une barre pour le
distinguer du premier et en notant α et β les multiplicateurs) = ⟨λ,
e c⟩ + ⟨e µ, d⟩ + b
t t
L(λ, µ, α, β) = −⟨λ, c⟩ − ⟨µ, d⟩ − b − ⟨α, G λ + H µ − u⟩ − ⟨β, µ⟩ = f ∗ (λ,
eµ e) + b,
= ⟨u, α⟩ − b − ⟨λ, c + Gα⟩ − ⟨µ, d + β + Hα⟩. où pour passer de la deuxième à la troisième ligne on a utilisé le fait que e x vérifie les
Pour que cette quantité ait une borne inférieure différente de −∞, il faut tout d’abord contraintes d’égalité. On conclut alors par la dernière partie de la Proposition 3.4.3. ■
que c + Gα = 0. De plus, comme µ ⩽ 0, il faut que d + β + Hα ⩽ 0 également, sinon le
produit scalaire ne sera pas borné inférieurement. Cette dernière inégalité peut s’écrire
Hα ⩽ d + β
On conclut donc que le problème dual revient à maximiser f ∗∗ : (α, β) 7→ ⟨u, α⟩ − b sous
les contraintes
Gα = −c
Hα ⩾ −d − β
β⩽0
Les deux dernière inégalités donnent Hα ⩾ −d. Réciproquement, si α réalise le mini-
mum de α 7→ ⟨u, α⟩ − b sous les contraintes Gα = −c et Hα ⩽ −d, alors en prenant β = 0
on a une solution du problème. Par conséquent, on peut prendre β = 0. Pour compa-
rer ce problème au problème primal, nous allons une fois de plus prendre l’opposé
de la fonction f ∗∗ afin d’avoir un problème de minimisation. Il s’agit donc de minimi-
ser α 7→ −⟨u, α⟩ + b, et en posant x = −α on trouve donc que −f ∗∗ (α) = f (x) et que les
contraintes sont
Gx = c
Hx ⩽ d.
Ainsi, nous avons démontré la Proposition suivante :
– 103 – – 104 –
Chapitre 4. Convexité
Nous avons vu à la fin du Chapitre 2 une méthode numérique pour chercher les
extrema d’une fonction : la Méthode de Newton. Elle présentait cependant plusieurs
inconvénients. L’un d’entre eux est qu’elle nécessite d’abord de calculer le gradient ∇f
de f , puis sa différentielle, – c’est-à-dire la Hessienne Hf de f – puisque c’est en fait
à cette fonction que la méthode s’applique. On peut donc se demander s’il n’existerait
pas une procédure plus directe qui puisse s’appliquer directement à f .
Une famille de méthodes de ce type est donnée par les méthodes dites de descente
CHAPITRE 4
de gradient. L’idée est la suivante : on part d’un point x0 et on se déplace en suivant la
pente donnée par le gradient, ce qui donne un point
x1 = x0 − t1 ∇f (x0 ).
CONVEXITÉ
On définit ainsi une suite par une formule de récurrence de la forme
Sur le troisième point, on peut par exemple mentionner les problèmes dits de moindre
carrés, et plus généralement d’optimisation quadratique, dont nous parlerons au Para-
graphe 4.3.
Avant de nous lancer, indiquons que la convexité est une propriété extrêmement
riche, même en l’absence de régularité. Par cela, nous voulons dire que beaucoup de
résultats d’optimisation sont valables pour des fonctions convexes qui ne sont pas dif-
férentiables, ce qui est parfois utile en pratique dans des situations où il ne serait pas
naturel de supposer certaines données lisses. Toutefois, quand les fonctions considé-
rées sont de classe C 1 , alors le travail que nous avons déjà accompli permet relative-
On voit donc que si x ∈ [e x + δ], alors on a deux possibilités :
x − δ; e
ment facilement d’obtenir des théorèmes puissants pour l’optimisation des fonctions
convexes.
x, f ′ (x) > 0 donc x − tf ′ (x) < x ;
• Si x > e
– 106 –
4.2. La théorie Chapitre 4. Convexité
Si on oublie le second terme o(∥x − e x∥), alors pour que l’écart entre f (x − tv) et f (x)
soit le plus petit possible, il faut que le produit scalaire ⟨∇f (x), v⟩ soit le plus grand
possible, et l’Inégalité de Cauchy-Schwarz nous dit que ceci se produit exactement
quand v est positivement colinéaire à ∇f (x). Ainsi, le gradient de f indique ce qu’on
appelle la direction de plus grande pente.
La suite donnée par la relation (4.1) converge-t-elle vers ex ? En général non, mais Un exemple fondamental de partie convexe de Rn est donné par les boules.
comme le suggère la figure ci-dessus, il y a une chance que cela fonctionne si la fonction Proposition 4.2.2. Les boules ouvertes et fermées sont convexes.
a une allure suffisamment sympathique. C’est ici que la notion de convexité s’avère
utile. En effet, une fonction convexe d’une variable est une fonction qui ressemble à
Démonstration. C’est un résultat que nous avons déjà établi sans le dire au cours de
celle de la figure. Pour une telle fonction, on devine que la méthode fonctionne, pour
certaines démonstrations. Soit x ∈ Rn et r > 0. Si y, y ′ ∈ B(x, r) et t ∈ [0; 1], alors
peu qu’on choisisse habilement le nombre tk à chaque étape. Ceci suggère donc de
développer une notion de convexité pour les fonctions de plusieurs variables, ce que
∥y + t(y ′ − y) − x∥ = ∥(1 − t)(y − x) + t(y ′ − x)∥
nous allons faire de ce pas.
⩽ (1 − t)∥y − x∥ + t∥y ′ − x∥
< (1 − t)r + tr
=r
4.2 La théorie donc y + t(y ′ − y) ∈ B(x, r). Si y, y ′ ∈ Bf (x, r), le même calcul est valable excepté qu’à
l’avant-dernière ligne on a une inégalité large, ce qui montre précisément que
4.2.1 Définition y + t(y ′ − y) ∈ Bf (x, r).
– 107 – – 108 –
4.2. La théorie Chapitre 4. Convexité
qui a un sens précisément parce que U est convexe. La dérivation des fonctions com- Proposition 4.2.6 (Inégalité de Jensen). Soit f : U → R une fonction convexe. Alors,
posées (Proposition 2.3.12) donne pour tous points x1 , · · · , xn ∈ U et tous 0 < t1 , · · · , tn < 1 tels que
on a
|g ′ (t)| = ⟨∇f (x + t(y − x)) , y − x⟩ n n
X X
⩽ ∇f (x + t(y − x)) ∥y − x∥ f ti xi ⩽ ti f (xi ).
i=1 i=1
⩽ M∥y − x∥.
Il ne reste plus qu’à appliquer l’Inégalité des accroissements finis à g pour obtenir Démonstration. Nous allons démontrer ce résultat par récurrence, en notant Hn l’in-
égalité pour n points. Comme H1 est triviale, nous allons commencer par montrer H2 ,
|f (y) − f (x)| = |g(1) − g(0)| qui n’est pas exactement la définition de la convexité que nous avons donnée dans la
⩽ M∥y − x∥ × |1 − 0| Définition 4.2.4. Pour cela, remarquons que comme t1 + t2 = 1, on a t1 = 1 − t2 . Par
= M∥x − y∥. conséquent,
t1 x1 + t2 x2 = x1 + t2 (x2 − x1 )
■
et donc par définition de la convexité
Nous pouvons maintenant définir la convexité pour les fonctions de plusieurs va- f (t1 x1 + t2 x2 ) ⩽ f (x1 ) + t2 (f (x2 ) − f (x1 ))
riables.
= (1 − t2 )f (x1 ) + t2 f (x2 )
Définition 4.2.4. Soit U une partie convexe de Rn . Une fonction f : U → R est dite
= t1 f (x1 ) + t2 f (x2 ).
convexe si pour tous x, y ∈ U et t ∈ [0; 1],
f (x + t(y − x)) ⩽ f (x) + t (f (y) − f (x)) . Supposons maintenant Hn vraie pour un n ⩾ 2, et considérons n + 1 points. L’idée
est de regrouper partiellement 1 les points pour n’en avoir plus que deux et pouvoir
Si l’inégalité précédente est stricte dès que x , y et t ∈]0; 1[, alors f sera dite strictement appliquer H2 . Ceci se fait comme suit : on pose t2′ = tn+1
convexe.
n
Remarque 4.2.5. L’épigraphe d’une fonction f : U → R est l’ensemble
X
t1′ = ti = 1 − tn+1 .
i=1
E(f ) = {(λ, x) ∈ R × U | λ ⩾ f (x)} .
En posant x2′ = xn et
On voit aisément que f est convexe si et seulement si son épigraphe est une partie n
convexe de R×Rn ≃ Rn+1 . En effet, si f est convexe et (λ, x), (µ, y) ∈ E(f ), alors pour tout
X t i
x1′ = xi ,
t ∈ [0; 1], t1′
i=1
on a
λ + t(µ − λ) = (1 − t)λ + tµ
⩾ (1 − t)f (x) + tf (y)
n+1
X
= f (x) + t(f (y) − f (x)) f ti xi = f (t1′ x1′ + t2′ x2′ )
i=1
⩾ f (x + t(y − x)),
⩽ t1′ f (x1′ ) + t2′ f (x2′ )
donc (λ + t(µ − λ), x + t(y − x)) ∈ E(f ). Réciproquement, si E(f ) est convexe et x, y ∈ U , = t1′ f (x1′ ) + tn+1 f (xn+1 ).
alors pour tout t ∈ [0; 1] on a (f (x) + t(f (y) − f (x)), x + t(y − x)) ∈ E(f ), donc
Si l’on pose maintenant, pour 1 ⩽ i ⩽ n, si = ti /t1′ , on a
f (x) + t(f (y) − f (x)) ⩾ x + t(y − x)
n
X
et f est convexe. si = 1.
i=1
La Définition 4.2.4 n’utilise que deux points, mais on pourrait vouloir faire des
combinaisons de trois points ou plus. Cela ne change en fait pas la notion considérée. 1. Les amateurs de géométrie affine y reconnaitront la notion de barycentre partiel.
– 109 – – 110 –
4.2. La théorie Chapitre 4. Convexité
On peut donc appliquer Hn pour conclure que 3. On a f (x + t(y − x)) ⩽ f (x) + t(f (y) − f (x)) par convexité de f , donc par croissance
n de g
X
t1′ f (x1′ ) = t1′ f si xi
[g ◦ f ](x + t(y − x)) ⩽ g (f (x) + t(f (y) − f (x)))
i=1
n
X ⩽ g(f (x)) + t (g(f (y)) − g(f (x)))
⩽ t1′ si f (xi ) = [g ◦ f ](x) + t ([g ◦ f ](y) − [g ◦ f ](x)) .
i=1
n
4. On peut écrire g(x) = Ax + b pour une matrice A ∈ Mn (R) et b ∈ Rn . On a alors
X
= ti f (xi ).
i=1
[f ◦ g](x + t(y − x)) = f (A(x + t(y − x)) + b)
■
= f (Ax + b + t(Ax − Ay)) = f (Ax + b + t((Ay + b) − (Ax + b))
Le terme “convexe” va rarement sans son alter ego “concave”. Une petite précaution = f (g(x) + t(g(y) − g(x)))
s’impose néanmoins : il n’existe pas de notion de partie concave d’un espace vectoriel. ⩽ f (g(x)) + t (f (g(y)) − f (g(x)))
Quant aux fonctions, il s’agit d’un simple changement de signe : = [f ◦ g](x) + t ([f ◦ g](y) − [f ◦ g](x))
Définition 4.2.7. Soit U ⊂ Rn une partie convexe. Une fonction f : U → R est dite
(strictement) concave si la fonction −f est (strictement) convexe. ■
Il est clair que toute énoncé sur les fonctions convexes se traduit sans peine en un
énoncé sur les fonctions concaves. Nous ne mentionnerons donc pas ce dernier afin de Nous avons vu que pour faire de l’optimisation, il faut en général des propriétés
ne pas alourdir le texte ou les énoncés. de régularité sur les fonctions considérées telles que la continuité ou le caractère C 1 .
Comme nous l’avons déjà mentionné, certaines de ces propriétés sont “presque” auto-
matiques pour les fonctions convexes. Même si nous n’en aurons pas besoin ultérieu-
4.2.2 Propriétés des fonctions convexes rement, nous allons donner un exemple concernant la continuité.
Les fonctions convexes sont importantes parce qu’elle jouissent de propriétés re- Proposition 4.2.9. Soit U ⊂ Rn une partie convexe et f : U → R une fonction convexe. Si
marquable. Par conséquent, il est important d’être capable de reconnaître rapidement x est à l’intérieur de U , alors f est continue en x.
une telle fonction. Pour cela, quelques propriétés de permanence peuvent s’avérer
utiles. Démonstration. La preuve recèle quelques subtilités et nous allons donc procéder par
étapes. Pour commencer, fixons un point x à l’intérieur de U et ϵ > 0.
Proposition 4.2.8. Soit U ⊂ Rn une partie convexe.
– 111 – – 112 –
4.2. La théorie Chapitre 4. Convexité
S = {a1 , · · · , a2n } cet ensemble fini. Pour borner f , nous allons poser M = maxS f . Alors, si y ∈ C, il existe 0 ⩽ t1 ⩽ · · · ⩽
t2n ⩽ 1 tels que, par la Proposition 4.2.6,
▶ Hypercube et points extrémaux n
X
f (y) = f
ti ai
L’étape suivante est de montrer que f est bornée sur l’hypercube C. Pour cela, il
i=1
nous faut établir un fait important sur ce dernier : tout point de C est une combi- n
X
naison convexe de ses sommets. Ceci peut aisément se démontrer par récurrence sur ⩽ ti f (ai )
la dimension n. En effet, pour n = 1, C est un segment et tout point d’un segment i=1
est combinaison convexe des extrémités. Si le résultat est vrai pour un certain n ⩾ 1, Xn
considérons un point y de C. Il existe t ∈ [0; 1] tel que ⩽ ti M
! ! i=1
r r = M.
y1 = t x1 − √ + (1 − t) x1 + √ .
2n 2n
√ √
Les deux points y + et y − obtenus en remplaçant y1 par x1 ± r/ 2n vérifient donc y = Ainsi, f (y) ⩽ M pour tout y ∈ C. Si on pose r ′ = r/ 2n, alors B(x, r ′ ) ⊂ C donc f est
′
bornée sur B(x, r ), ce que nous voulions prouver.
ty − + (1 − t)y + . De plus,
n+1 " #
Y r r ▶ La fonction f est continue
y ′ = (y2 , · · · , yn ) ∈ C ′ = xi − √ ; xi + √ ,
i=2 2n 2n
Considérons maintenant un point y ∈ B(x, r ′ /2) et recourons à une astuce : il s’agit
donc par l’hypothèse de récurrence, il existe des réels 0 ⩽ s1 , · · · s2n−1 ⩽ 1 dont la somme de construire un élément de B(x, r ′ ) dont la bornitude nous permettra de majorer f (x)−
fait 1 et tels que – en utilisant l’Inégalité de Jensen de la Proposition 4.2.6 – f (y). La solution la plus simple pour cela est de poser
2n−1
X
y′ = sj bj , r′
z=y+ (y − x).
j=1 2∥y − x∥
où (bj )1⩽j⩽2n−1 désigne l’ensemble des sommets de C ′ . Pour conclure, il suffit d’observer,
en notant bj+ (respectivement bj− ) le vecteur de Rn obtenu à partir de bj en ajoutant Géométriquement, z est obtenu en partant de y et en se déplaçant dans la direction
opposée à x, mais pas trop de façon à rester dans la boule B(x, r ′ ). Voici une illustration
comme première coordonnée xi − √r (respectivement xi + √r ), que
2n 2n en deux dimensions :
− +
y = ty + (1 − t)y
2 n−1 2 n−1
X X
=t sj bj− + (1 − t) sj bj+
j=1 j=1
2n
X
= ti ai
i=1
2n
X 2
X n−1 2
X n−1
ti = t sj + (1 − t) sj
i=1 j=1 j=1
= t + (1 − t)
= 1.
– 113 – – 114 –
4.2. La théorie Chapitre 4. Convexité
En effet, on a bien Proposition 4.2.11. Soit U un ouvert convexe de Rn et f : U → R une fonction de classe
r′ C 1 . Alors, f est convexe si et seulement si pour tous x, y ∈ U ,
∥z − x∥ ⩽ ∥y − x∥ + ∥y − x∥
2∥y − x∥
f (y) − f (x) ⩾ ∇f (x), y − x .
r′ r′
< +
2 2 De plus, f est strictement convexe si et seulement si cette inégalité est stricte dès que x , y.
= r′.
De plus, en posant α = r ′ /2∥y − x∥, on peut écrire u = y + α(y − x) et donc Démonstration. Il s’agit en fait simplement d’une version “infinitésimale” de la défi-
nition de la convexité, c’est-à-dire une version obtenue en faisant habilement tendre
1 α t vers 0 dans la définition. Voici comment procéder. Si f est convexe on a, pour tout
y= z+ x.
α+1 α+1 t ∈ [0; 1],
Comme α > 0, les deux coefficients ci-dessus sont positifs et leur somme fait 1. On f (x) + t (f (y) − f (x)) ⩾ f (x + t(y − x)) ,
peut donc appliquer la convexité de f pour obtenir
ce qui peut s’écrire
1 α t (f (y) − f (x)) ⩾ f (x + t(y − x)) − f (x).
f (y) ⩽ f (z) + f (x).
α+1 α+1
En divisant par t, cette inégalité devient
En soustrayant f (x) aux deux membres on trouve finalement
1 f (x + t(y − x)) − f (x)
f (y) − f (x) ⩽ (f (z) − f (x)) f (y) − f (x) ⩾ .
α+1 t
2M
⩽ Posons g : t ∈ [0; 1] 7→ f (x+t(y −x)). Il s’agit d’une fonction de classe C 1 et le membre
α+1
2∥y − x∥ de droite ci-dessus en est un taux d’accroissement en 0. Si on peut la prolonger en une
= 2M ′ fonction de classe C 1 sur ] − δ; 1] pour un δ > 0, alors on pourra passer à la limite et
r + 2∥y − x∥
obtenir g ′ (0). Pour ce faire, remarquons que U est ouvert, donc qu’il existe r > 0 tel que
4M
⩽ ′ ∥y − x∥. B(x, r) ⊂ U . Alors, en posant δ = r/∥y − x∥, on a bien
r
En echangeant les rôles de x et y, on obtient la même majoration pour f (x) − f (y), ce x + t(y − x) − x < r
qui permet de conclure que
pour t ∈] − δ; δ[ et on peut donc prolonger g. Quand t → 0, le membre de droite tend
4M
f (y) − f (x) ⩽ ∥y − x∥. donc vers g ′ (0) qui par dérivation des fonctions composées (Proposition 2.3.12) est égal
r′ à ⟨∇f (x), y − x)⟩, et le résultat suit.
Nous pouvons maintenant montrer la continuité : pour tout ϵ > 0, si Réciproquement, nous allons utiliser l’inégalité de l’énoncé entre les points x et
4Mϵ
x + t(y − x) d’une part, et x + t(y − x) et y d’autre part. Cela donne pour les premiers
y ∈ B x, min r ′ , ′ , points
r
alors |f (y) − f (x)| ⩽ ϵ d’après ce qui précède, ce qu’il fallait démontrer. ■ f (x) ⩾ f (x + t(y − x)) + ∇f (x + t(y − x)) , x − (x + t(y − x))
Remarque 4.2.10. On pourra noter que nous avons montré un résultat un peu plus = f (x + t(y − x)) − t ∇f (x + t(y − x)) , y − x
fort : une fonction convexe est localement lipschitzienne sur l’intérieur de son domaine
de définition. et de même pour les seconds
Le grand intérêt des fonctions convexes, c’est qu’en s’y restreignant on obtient des Notre objectif étant de faire disparaître les gradients, nous allons multiplier la pre-
version améliorés des théorèmes généraux sur les extrema de fonctions différentiables. mière inégalité par (1 − t), la seconde par t, et additionner pour trouver
Par exemple, les points critiques – qui sont faciles à détecter – ne sont pas toujours des
extrema. Eh bien pour les fonctions convexes, si ! Cela dit, la preuve nécessite d’abord (1 − t)f (x) + tf (y) ⩾ f (x + t(y − x)) .
de mieux comprendre le lien entre convexité et dérivées partielles.
■
Pour une fonction d’une variable f : I → R dérivable, on sait bien que la convexité
est équivalente à la croissance de la fonction dérivée f ′ . Dans le cas de plusieurs va- Avec ce résultat, on peut facilement montrer que points critiques et extrema coïn-
riables, un résultat analogue est valable, à condition de comprendre ce que la crois- cident.
sance signifie.
– 115 – – 116 –
4.2. La théorie Chapitre 4. Convexité
Théorème 4.2.12 (Points critiques des fonctions convexes) Soit U un ouvert Le Théorème 4.2.12 affirme que la condition d’annulation du gradient, qui n’est que
convexe de Rn et f : U → R une fonction convexe de classe C 1 . Si x est un point nécessaire pour l’existence d’un extremum, est également suffisante. Ce résultat reste
critique de f , alors f a un minimum global en x. encore vrai sous contraintes, fournissant ainsi une réciproque au Théorème 3.2.6. De
fait, nous avons déjà vu cela dans le cas particulier des fonctions affines, qui sont bien
évidemment convexes. Nous donnons ici un résultat plus général, en avertissant néan-
Démonstration. Il suffit d’appliquer la Proposition 4.2.11 : comme x est un point cri- moins qu’il contient, outre la convexité de la fonction f à minimiser, des hypothèses
tique, on a pour tout y ∈ U , fortes sur les fonctions définissant les contraintes. En effet, si l’on veut pouvoir exploi-
f (y) − f (x) ⩾ ∇f (x), y − x ter la convexité de f , alors il faut que l’ensemble D sur lequel on cherche à l’optimiser
soit lui-même convexe. Pour les contraintes d’inégalité, cela se traduit facilement :
= 0,
donc f (y) ⩾ f (x). ■ Lemme 4.2.15. Soient h1 , · · · , hp : U → R des fonctions convexes. Alors, l’ensemble
Il n’y a bien sûr pas unicité en général – il suffit de penser à une fonction constante D = {x ∈ U | hj (x) ⩽ 0 pour tout 1 ⩽ j ⩽ p}
sur R – mais on peut l’obtenir en renforçant un peu l’hypothèse sur f :
Lemme 4.2.13. Soit f : U → R une fonction strictement convexe. Alors, si f admet un est convexe.
minimum global en un point x, ce minimum est unique.
Démonstration. Soit y un point tel que f (y) = f (x). Alors, en prenant par exemple t = Démonstration. Il suffit de le faire pour une seule fonction, puisqu’une intersection de
1/2 dans la définition de la convexité on a parties convexes est convexe 2 . Or, si h(x), h(y) ⩽ 0, alors on a pour tout t ∈ [0; 1]
x+y f (x) + f (y)
f ⩽ = f (x). h(x + t(y − x)) ⩽ f (x) + t(f (y) − f (x))
2 2
= (1 − t)f (x) + tf (y)
Comme l’inégalité ne peut être stricte, on doit donc avoir x = y par stricte convexité de
f. ■ ⩽ 0.
Une conséquence du résultat précédent est que tout minimum local d’une fonction ■
convexe est en fait global ! Il se trouve que l’on n’a pas besoin de supposer la fonction de
classe C 1 ni d’utiliser le calcul différentiel pour montrer ce résultat. À titre de curiosité,
et pour montrer la force et l’intérêt de l’analyse convexe non différentiable, nous en Pour les contraintes d’égalité, par contre, les choses se compliquent. En effet, il est
donnons une démonstration. très rare qu’un ensemble de la forme {x ∈ U | g(x) = 0} soit convexe. Le seul cas où il
est facile de s’assurer que c’est le cas est celui des fonctions affines. En effet, l’ensemble
Proposition 4.2.14. Soit U ⊂ Rn une partie convexe et soit f : U → R une fonction
considéré est alors un sous-espace affine, donc une partie convexe. Nous supposerons
convexe. Si f a un minimum local en un point x ∈ U , alors c’est un minimum global.
donc désormais que les contraintes d’égalité sont toutes de cette forme.
Démonstration. Par définition d’un minimum local, il existe δ > 0 tel que si y ∈ U véri-
fie ∥x −y∥ < δ, alors f (x) ⩽ f (y). Si maintenant on considère un point z ∈ U quelconque, Théorème 4.2.16 (Points critiques sous contraintes des fonctions convexes)
posons, pour t ∈ [0; 1], Soit U un ouvert convexe de Rn et f : U → R une fonction convexe de classe C 1 .
zt = x + t(z − x). Soient également g1 , · · · , gm : U → R des fonctions affines et h1 , · · · , hp : U → R
des fonction convexes de classe C 1 . Soit e x ∈ D tel qu’il existe λ1 , · · · , λm ∈ R et
Alors,
µ1 , · · · , µp ∈ R− vérifiant
∥zt − x∥ = ∥t(z − x)∥ p
m
X X
= t∥z − x∥. ∇f (e
x) = λi ∇gi (e
x) + µj ∇hj (e
x).
i=1 j=1
Ainsi, pour t0 = δ/2∥z−x∥, on a f (zt0 ) ⩾ f (x). On conclut ensuite en utilisant la convexité :
Alors, f admet en e
x un minimum global sous contraintes.
t0 f (z) = f (x) + t0 (f (z) − f (x)) − (1 − t0 )f (x)
⩾ f (zt0 ) − (1 − t0 )f (x)
⩾ f (x) − (1 − t0 )f (x)
= t0 f (x). Démonstration. L’idée est la même que pour la seconde partie de la démonstration du
■ 2. Vérifiez-le !
– 117 – – 118 –
4.2. La théorie Chapitre 4. Convexité
Théorème 3.3.1. En effet, pour tout x ∈ D on a En particulier, f admet un minimum global sous contraintes et les multiplicateurs
correspondants donnent un maximum global sous contrainte du problème dual.
f (x) − f (e
x) ⩾ ⟨∇f (e
x), x − e
x⟩
m p
X X La démonstration de ce théorème nécessite un résultat général sur les parties convexes
= λi ⟨∇gi (ex), x − e
x⟩ + µj ⟨∇hj (e
x), x − e
x⟩ de Rn que nous allons d’abord énoncer et démontrer. On pourra noter sa ressemblance
i=1 j=1
avec le Lemme de Farkas (Lemme 3.2.4) qui était crucial pour la démonstration du
m m p
X X X Théorème KKT (Théorème 3.2.6).
= λi ⟨vi , x⟩ + x⟩ +
λi ⟨vi , e µj ⟨∇hj (e
x), x − e
x⟩
i=1 i=1 j=1 Lemme 4.2.19. Soit C ⊂ Rn une partie convexe ne contenant pas 0. Alors, il existe un
m
X m
X p
X vecteur u , 0 tel que
= λi ci − λi c i + µj ⟨∇hj (e
x), x − e
x⟩ ⟨u, x⟩ ⩾ 0
i=1 i=1 j=1 pour tout x ∈ C.
Xp
= µj ⟨∇hj (e
x), x − e
x⟩ Démonstration. La preuve, quoique simple recèle une subtilité. En effet, nous allons
j=1 avoir besoin de travailler avec l’adhérence C de C, et bien que 0 < C, il se pourrait
qu’il soit dans l’adhérence. Néanmoins, même dans ce cas il existe une suite (xk )k∈N
d’éléments de Rn telle que xk → 0 et xk < C pour tout k ∈ N.
La convexité de hj donne alors
Posons Fk : x ∈ C 7→ ∥x − xk ∥. Si C est bornée, il en est de même pour son adhérence
⟨∇hj (e
x), x − e
x⟩ ⩽ hj (x) − hj (e
x). qui est alors compacte. Dans ce cas, Fk étant continue elle admet un minimum global.
Si hj (e
x) , 0, alors la contrainte est inactive et µj = 0. Sinon, on a Si C n’est pas bornée, alors Fk tend vers +∞ quand ∥x∥ → +∞, donc une fois encore Fk
admet un minimum global. Ainsi, dans tous les cas on dispose d’un point e xk qui réalise
hj (x) − hj (e
x) = hj (x) ⩽ 0. le minimum.
Comme ce terme est multiplié par µj ⩽ 0, on trouve finalement Nous allons maintenant montrer que pour tout x ∈ C,
f (x) − f (e
x) ⩾ 0, xk − xk ⟩ ⩾ 0.
xk , e
⟨x − e
ce qu’il fallait démontrer. ■ Pour ce faire, posons, pour t ∈ [0; 1], xt = e
xk +t(x −exk ). Alors, xt ∈ C donc par minimalité
Remarque 4.2.17. Cet énoncé, quoique proche de celui du Théorème 3.3.1, n’est pas on a ∥xt − xk ∥ ⩾ ∥e
xk − xk ∥. En élevant au carré cette égalité on obtient
tout à fait du même ordre. En effet, nous n’affirmons pas ici que les conditions KKT xk − xk ∥2 + 2t⟨x − e
∥e xk − xk ⟩ + t 2 ∥x − e
xk , e xk ∥2 ⩾ ∥e
xk − xk ∥2 ,
sont valables indépendamment de toute qualification des contraintes. Par contre, il est
bien vrai que les conditions KKT sont suffisantes et que tout minimum local est global. ce qui en simplifiant donne
Ce dernier résultat suggère de regarder de plus près le comportement du Lagran- 2⟨x − e xk − xk ⟩ ⩾ −t 2 ∥x − e
xk , e xk ∥2 .
gien sous les mêmes hypothèses. Et en effet, on peut alors améliorer la dualité faible
donnée par la Proposition 3.4.3 en un résultat de dualité forte. Il s’agit d’un résultat En divisant par t puis en faisant tendre ce dernier vers 0, on obtient l’inégalité annon-
important pour l’optimisation convexe, du à Slater 3 . cée.
Théorème 4.2.18 (Dualité forte de Lagrange pour les problèmes convexes) Soit Pour conclure, posons
xk − xk
U un ouvert convexe de Rn et f : U → R une fonction convexe de classe C 1 . Soient
e
uk = .
également g1 , · · · , gm : U → R des fonctions affines et h1 , · · · , hp : U → R des fonction xk − xk ∥
∥e
convexes de classe C 1 . On suppose que La suite (uk )k∈N est bornée car tous ses éléments sont de norme 1. Par conséquent, il
existe une sous-suite (uφ(k) )k∈N qui converge vers un vecteur u qui vérifier ∥u∥ = 1 et
• Il existe b
x ∈ D tel que hj (b
x) < 0 pour tout 1 ⩽ j ⩽ p ; donc en particulier u , 0. De plus,
f (e
x) = L(e
x, λ,
eµ e) = f ∗ (λ,
eµ e). Comme ⟨xk , uk ⟩ → ⟨0, u⟩ = 0, on en passant à la limite que
⟨x, u⟩ ⩾ 0
3. Morton L. Slater (1921–2002) : mathématicien américain ayant en particulier travaillé sur l’opti-
misation convexe. pour tout x ∈ C, et donc en particulier pour tout x ∈ C. ■
– 119 – – 120 –
4.2. La théorie Chapitre 4. Convexité
Remarque 4.2.20. Ce résultat admet une interprétation géométrique intéressante : l’hy- et que par conséquent
perplan (sous-espace de codimension 1) formé de tous les vecteurs orthogonaux à u
m p
“sépare” C de l’origine. En effet, tous les points de C sont dans le même demi-espace dé- X X
limité par cet hyperplan, tandis que l’origine appartient, elle, à l’hyperplan lui-même. f (e
x) = f (e
x) − ei gi (e
λ x) − ej hj (e
µ x) = L(e
x, λ,
eµ e).
i=1 j=1
Il existe de nombreux résultats de séparation de convexes reposant sur les mêmes
idées, et qui peuvent s’avérer utiles en optimisation.
Néanmoins, il nous reste à vérifier que α, γ1 , · · · , γp ⩾ 0 et α , 0. Supposons pour
Nous sommes maintenant prêts à démontrer la dualité forte pour les problèmes
commencer α < 0. Alors, comme (fe(x) + N , g(x), h(x)) ∈ C pour tout N ∈ N, on a
convexes.
m
X p
X
Démonstration du Théorème 4.2.18. Commençons par quelques notations pour alléger α fe(x) + N α + βi gi (x) + γj hj (x) ⩾ 0,
un peu les formules : nous allons maintenant utiliser les fonctions fe : x 7→ f (x) − f (e x) i=1 j=1
ainsi qu’aux fonctions g = (g1 , · · · , gm ) : U → Rm et h = (h1 , · · · , hp ) : U → Rp . Nous allons
nous intéresser à l’ensemble ce qui donne une contradiction quand N → +∞. Ainsi, α ⩽ 0 et le même raisonnement
montre que γj ⩽ 0 pour tout 1 ⩽ j ⩽ p. Supposons maintenant que α = 0. Par hypothèse,
m p
C = {(X, Y , Z) ∈ R × R × R | X > fe(x), Y = g(x), Z =⩾ h(x) pour un x ∈ U }. il existe b
x ∈ U tel que g(b
x) = 0 et h(b
x) < 0. Or, si α = 0 on a
Faisons deux observations : m
X p
X
0 ⩽ αf (b
x) − αf (e
x) + βi gi (b
x) + γj hj (b
x)
• Parce que f et h sont convexes et que g est affine, l’ensemble C est lui-même i=1 j=1
convexe ; p
X
• On a (0, 0, 0) < C. En effet, on aurait sinon un point x ∈ U tel que f (x) < f (e
x) et = γj hj (b
x)
h(x) ⩽ 0, ce qui contredit la minimalité de ex sous contraintes. j=1
D’après le Lemme 4.2.19, il existe donc u ∈ R×Rm ×Rp non nul tel que ⟨u, (X, Y , Z)⟩ ⩾ Comme hj (bx) < 0 et γj ⩾ 0 pour tout 1 ⩽ j ⩽ p, on doit donc avoir γj = 0. Mais alors, on
a pour tout x ∈ U que
0 pour tout (X, Y , Z) ∈ C. Pour x ∈ U , on a (fe(x) + 1/N , g(x), h(x)) ∈ C, donc en passant à Xm
la limite quand N → +∞ on conclut que βi gi (x) ⩾ 0.
i=1
⟨u, (fe(x), g(x), h(x))⟩ ⩾ 0.
Mais comme par hypothèse 0 est intérieur à g(U ), il existe t > 0 tel que −tβ ∈ g(U ), où
Ainsi, en notant α, β1 , · · · , βm , γ1 , · · · , γp les coefficients de u ∈ R1+m+p . β = (β1 , · · · , βm ). Si x est un antécédent, on a
m p
X X m
X
αf (x) + βi gi (x) + γj hj (x) ⩾ αf (e
x). −t∥β∥2 = βi gi (x) ⩾ 0,
i=1 j=1 i=1
Supposons pour l’instant α > 0 et γ1 , · · · , γp ⩾ 0. Alors, en divisant par α et en posant qui implique β = 0 et donc u = 0, une contradiction. Ainsi, α > 0 et la preuve est
ei = −βi /α et µ
λ ej = −γj /α on a terminée. ■
m p
Rappelons qu’en général, la dualité faible de la Proposition 3.4.3 nous dit qu’on
X X
f (x) − ei gi (x) −
λ ej hj (x) ⩾ f (e
µ x).
i=1 j=1 peut minorer les extrema de f par les maxima de f ∗ . L’espoir que nous avions évoqué
était que f ∗ soit dans certains cas plus simple à étudier que f . De fait, f ∗ est en un sens
En prenant la borne inférieure du membre de droite sur x, on en déduit toujours plus facile, parce qu’elle est toujours concave.
f ∗ (λ,
eµ e) ⩾ f (e
x). Proposition 4.2.21. Pour tout problème d’optimisation, la fonction duale f ∗ est concave.
Comme l’inégalité opposée est vraie par la Proposition 3.4.3, on conclut qu’il y a éga-
lité, ce qui donne la dualité forte. Pour voir que cette valeur coïncide avec celle du Démonstration. La fonction f ∗ est définie comme la borne inférieure des fonctions
Lagrangien, remarquons que comme µ ej , hj (x) ⩽ 0, leur produit est positif et par consé-
m p
quent leur somme également. Or, prenant x = e x dans l’égalité ci-dessus et en se souve-
X X
fx : (λ, µ) 7→ f (x) − λi gi (x) − µj hj (x).
nant que gi (e
x) = 0 pour tout 1 ⩽ i ⩽ m, on voit que
i=1 j=1
p
X
ej hj (e
µ x) = 0 Chacune de ces fonctions, étant linéaire, est en particulier concave (et également convexe,
j=1 mais cela ne nous est d’aucune utilité ici). Or, une borne inférieure de fonctions concaves
– 121 – – 122 –
4.2. La théorie Chapitre 4. Convexité
p
est toujours concave. En effet, pour λ, λ′ ∈ Rm et µ, µ′ ∈ R+ (on remarquera que Rp− est On peut alors appliquer l’Égalité de Taylor-Lagrange pour conclure qu’il existe c ∈
convexe) et t ∈ [0; 1], on a [0; 1] tel que
1
f ∗ ((λ, µ) + t(λ′ − λ, µ′ − µ)) ⩽ fx ((λ, µ) + t(λ′ − λ, µ′ − µ)) g(1) = g(0) + g ′ (0) + g ′′ (c).
2
⩽ fx (λ, µ) + t (fx (λ′ , µ′ ) − fx (λ, µ)) Par dérivation des fonctions composées, on a g ′ (0) = ⟨∇f (x), y − x⟩ et
D E
et en passant à la borne inférieure dans le membre de droite, on obtient le résultat g ′′ (x) = Hf (x + c(y − x))(y − x), y − x ⩾ 0.
souhaité. ■
Par conséquent,
En particulier, maximiser f ∗ revient à minimiser −f ∗ , et nous savons que si un
minimum local existe, alors il est global. f (y) = g(1)
⩾ g(0) + g ′ (0)
= f (x) + ∇f (x), y − x .
4.2.4 Une autre caractérisation de la convexité
D’après la Proposition 4.2.11, ceci implique que f est convexe. ■
Nous avons donné dans la propriété 4.2.11 une caractérisation des fonctions convexes
de classe C 1 utilisant le gradient. Dans le cas d’une variable, s’il est vrai que les fonc-
tions dérivables qui sont convexes sont celles dont la dérivée est croissante, il est sou-
vent plus facile de vérifier que la dérivée seconde – pour peu qu’elle existe – est posi-
4.3 Optimisation quadratique
tive. Cela est également possible dans le cas de plusieurs variables.
Le carré est un triangle qui a réussi,
Proposition 4.2.22. Soit U un ouvert convexe de Rn et f : U → R une fonction de classe ou une circonférence qui a mal tourné.
C 2 . Alors, f est convexe si et seulement si sa matrice Hessienne Hf (x) est positive pour tout P. Dac, L’os à Moelle
En appliquant maintenant cette inégalité à y = x + th, on voit que Avant d’aller plus loin, donnons un exemple de première importance : la fonction
ce qui en divisant par t donne pour y ∈ Rn fixé. Il suffit en effet de développer la norme au carré pour trouver
– 123 – – 124 –
4.3. Optimisation quadratique Chapitre 4. Convexité
mais en plaçant les vecteurs x(m)i les uns sous les autres pour former un vecteur X(m) Partant de ce constat, nous écrirons désormais toujours une fonction quadratique sous
et en procédant de même pour former un vecteur Y , la somme ci-dessus est bien égale à la forme
∥Y − X(m)∥2 . Ainsi, l’optimisation quadratique contient en particulier ce qu’on appelle 1
f : x 7→ ⟨Ax, x⟩ + ⟨b, x⟩,
les méthodes de moindre carré. 2
Allons maintenant plus loin en essayant d’utiliser les résultats que nous avons pour avec A ∈ Mn (R) une matrice symétrique. Attention ! Le facteur 1/2 fait que l’on a désor-
étudier les problèmes d’optimisation quadratiques. Pour cela, il paraît raisonnable de mais
commencer par calculer le gradient et la Hessienne de la fonction f (étant polynomiale, ∇f (x) = Ax + b & Hf (x) = A.
elle est de classe C ∞ donc ces objets ont un sens).
Proposition 4.3.3. Soit f une fonction quadratique donnée par une matrice A et un vecteur En particulier nous pouvons maintenant aisément caractériser la convexité d’une
b. On a alors fonction quadratique.
∇f (x) = (A + At )x + b & Hf (x) = A + At .
Corollaire 4.3.4. Soit f une fonction quadratique. Alors,
Démonstration. Il suffit de calculer, pour x, h ∈ Rn ,
f (x + h) = ⟨Ax + Ah, x + h⟩ + ⟨b, x + h⟩ • Elle est convexe si et seulement si A est positive ;
= ⟨Ax, x⟩ + ⟨b, x⟩ + ⟨Ax, h⟩ + ⟨Ah, x⟩ + ⟨b, h⟩ + ⟨Ah, h⟩
= f (x) + ⟨Ax, h⟩ + ⟨h, At x⟩ + ⟨b, h⟩ + ⟨Ah, h⟩ • Elle est concave si et seulement si A est négative.
t
= f (x) + ⟨(A + A )x + b, h⟩ + ⟨Ah, h⟩
De plus, si le signe des valeurs propres de A est strict, alors la convexité (respectivement
concavité) de f est stricte également.
En observant que l’application
Remarque 4.3.5. Si A admet des valeurs propres strictement positives et strictement
h 7→ ⟨(A + At )x + b, h⟩
négatives, il est aisé en considérant les vecteurs propres associés et en s’inspirant de la
est linéaire tandis que démonstration de la Proposition 2.3.25, de voir que f n’a pas d’extremum global. Ce
sont donc essentiellement les cas convexe et concave qui sont intéressant du point de
|⟨Ah, h⟩| ⩽ ∥Ah∥ × ∥h∥ vue de l’optimisation quand il n’y a pas de contraintes.
⩽ ∥A∥ × ∥h∥2
Avant d’aller plus loin, écrivons explicitement ce que nos résultats précédents nous
de sorte que ce dernier terme est négligeable devant ∥h∥, on conclut que nous avons un disent dans le cadre d’une optimisation sans contrainte. Si A est positive, alors la fonc-
développement limité au premier ordre, et que par conséquent ∇f (x) = (A + At )x + b. tion quadratique f possède un minimum global si et seulement si l’équation Ax = b
admet une solution. En effet, Ax = b si et seulement si ∇f (x) = 0, et le Théorème 4.2.12
Le gradient étant linéaire, sa différentielle – qui n’est autre que la Hessienne de f –
assure que cette condition est suffisante pour avoir un extremum global. On remarque
se calcule aisément :
en particulier que le minimum est unique si A est inversible. Par contre, si A n’est pas
f (x + h) − f (x) = (A + At )(x + h) + b − ((A + At )x + b) surjective il peut ne pas exister, et si A n’est pas injective il y aura soit aucun minimum
soit une infinité. Résumons ceci dans le cas le plus favorable.
= (A + At )h
donc Hf (x) = A + At . ■ Proposition 4.3.6. Soit A ∈ Mn (R) une matrice définie positive, soit b ∈ Rn et soit c ∈ R.
Alors, la fonction quadratique f : Rn → R définie par
La remarque importante à faire sur ce résultat, c’est que les quantités qui nous
intéressent ne dépendent pas vraiment de A mais plutôt de A + At . Or, cette matrice a 1
f (x) = ⟨Ax, x⟩ + ⟨b, x⟩ + c
la propriété intéressante d’être toujours symétrique ! Peut-on donc toujours supposer 2
A symétrique ? La réponse est oui, en remarquant simplement que pour tout x ∈ Rn ,
x = −A−1 b, dont la valeur est
admet un unique minimum global au point e
1 1
⟨Ax, x⟩ = ⟨Ax, x⟩ + ⟨Ax, x⟩
2 2 1D E
1 1 f (e
x) = c − b, A−1 b .
= ⟨Ax, x⟩ + ⟨x, At x⟩ 2
2 2
1 1
= ⟨Ax, x⟩ + ⟨At x, x⟩
2 2 Démonstration. Comme ∇f (x) = Ax+b et que A est inversible, on voit que e
x est l’unique
1 point critique. Par convexité, c’est donc un minimum global, qui est nécessairement
= ⟨(A + At )x, x⟩.
2 unique. La valeur de f (e
x) se calcule sans difficulté. ■
– 125 – – 126 –
4.3. Optimisation quadratique Chapitre 4. Convexité
4.3.2 La méthode d’Uzawa Telles qu’exprimées ci-dessus, les conditions de complémentarité ne sont pas vrai-
ment plus simples. Mais cette écriture suggère une façon plus compacte de les présen-
Nous avons vu au Paragraphe 3.3 que la forme particulière des fonctions linéaires ter, grâce à une application que nous allons maintenant introduire.
rendait leur optimisation sous contraintes linéaire abordable à l’aide d’algorithmes Définition 4.3.8. Pour un réel x, on pose x− = min(x, 0). Si µ ∈ Rp , on définit alors
spécialement conçus, comme l’algorithme du simplexe. Dans le cas quadratique, il P (µ) ∈ Rp− comme étant le vecteur de coordonnées (µ−j )1⩽j⩽p .
est également possible de donner des algorithmes très efficaces en exploitant la forme
particulière de la fonction et nous allons en donner un exemple ci-dessous. La fonction Le Lemme 4.3.7 peut alors s’exprimer comme suit :
quadratique f est comme toujours donnée par
µ = P (µ − (He
x − d))
1
f : x 7→ ⟨Ax, x⟩ + ⟨b, x⟩,
2
L’application P est appelée projection sur Rp− (attention, il ne s’agit pas d’une appli-
avec A une matrice symétrique que nous supposerons définie positive. De plus, nous
cation linéaire) et elle vérifie des propriétés fort sympathiques, dont voici un échan-
avons vu que pour garantir la convexité de l’ensemble D, il fallait en général suppo-
tillon.
ser les contraintes d’égalité affines. D’un point de vue théorique, de telles contraintes
peuvent être enlevées puisqu’elles consistent simplement en une restriction à un sous- Proposition 4.3.9. Pour tout µ, µ′ ∈ Rp− , on a
espace affine. Par conséquent, nous supposerons pour simplifier qu’il n’y a pas de
contraintes d’égalité. ⟨µ − P (µ), µ′ − P (µ)⟩ ⩽ 0. (4.2)
Quant aux contraintes d’inégalité, elles doivent être convexes pour que la convexité
de f puisse être utilisée. Mais pour alléger un peu la démonstration de la convergence De plus, la projection P est contractante au sens où
de la méthode, nous allons nous restreindre au cas de contraintes affines. Ainsi, notre
∥P (µ) − P (µ′ )∥ ⩽ ∥µ − µ′ ∥.
cadre sera le suivant : nous considérerons des vecteurs w1 , · · · , wp ∈ Rn et les contraintes
correspondantes hj (x) = ⟨wj , x⟩ − dj ⩽ 0. Comme dans le cas linéaire, ces contraintes
peuvent être regroupées dans une matrice H pour s’écrire Hx ⩽ d, où l’inégalité est Démonstration. Nous allons d’abord montrer que l’inégalité (4.2) est bien vérifiée. Pour
comprise coefficient par coefficient. Avec ces notations, les conditions KKT deviennent cela, il faut calculer
x + b − Htµ = 0 n
Ae X
⟨µ − P (µ), µ′ − P (µ)⟩ = (µi − µ−i )(µ′i − µ−i )
He x ⩽ d
µ ⩽ 0 i=1
µj hj (e
x) = 0
L’idée de la méthode que nous allons présenter est que, comme A est inversible, Or, par définition, µi − µ−i = 0 si µi ⩽ 0 et µi sinon. Par conséquent, les seuls termes non
on peut aussi bien chercher à approcher µ que e x. Cela revient en un sens à essayer nuls dans la somme sont ceux pour lesquels µi ⩾ 0, c’est-à-dire µ−i = 0. Ainsi, en posant
de résoudre numériquement le problème dual, ce qui est équivalent à la résolution µ+i = µi − µ−i ,
du problème primal grâce à la dualité forte donnée par le Théorème 4.2.18. Nous ne n
sommes donc pas très avancés, à moins de tenter de jouer les équilibristes en appro-
X
⟨µ − P (µ), µ′ − P (µ)⟩ = µ+i µ′i
chant simultanément e x et µ ! En effet, la première équation des conditions KKT nous
i=1
donne le moyen de calculer xk en fonction de µk , puisque A est inversible. Mais com-
⩽ 0.
ment calculer ensuite l’approximation suivante µk+1 de µ en fonction de xk ? Pour le
voir, il nous faut reformuler les conditions de complémentarité. Elles nous disent que
pour tout 1 ⩽ j ⩽ p, le coefficient µj est nul dès que le coefficient (Hx − d)j ne l’est Montrons maintenant la seconde propriété. On a
pas. On peut reformuler cette condition au niveau du vecteur µ − (He x − d) de la façon
suivante : ⟨µ − µ′ , P (µ) − P (µ′ )⟩ = ⟨µ − P (µ) + P (µ) − P (µ′ ) + P (µ′ ) − µ′ , P (µ) − P (µ′ )⟩
= ⟨µ − P (µ), P (µ) − P (µ′ )⟩ + ⟨P (µ) − P (µ′ ), P (µ) − P (µ′ )⟩
Lemme 4.3.7. Les conditions µj hj (e
x) = 0 sont équivalentes aux conditions suivantes pour
tout 1 ⩽ j ⩽ p : + ⟨P (µ′ ) − µ′ , P (µ) − P (µ′ )⟩
= ⟨µ − P (µ), P (µ) − P (µ′ )⟩ + ∥P (µ) − P (µ′ )∥2
• Si (µ − (He
x − d))j > 0, alors µj = 0 ; + ⟨P (µ′ ) − µ′ , P (µ) − P (µ′ )⟩
• Si (µ − (He
x − d))j ⩽ 0, alors (He
x − d)j = 0.
Démonstration. Dans le premier cas, on doit avoir (He x − d)j , 0 et donc µj = 0. Dans le Les deux produits scalaires du membre de droite sont négatifs par l’inégalité (4.2),
second cas, si on avait (He
x − d)j < 0, alors on aurait µj = 0 et donc (µ − (Hex − d))j > 0, donc
d’où le résultat. ■ ⟨µ − µ′ , P (µ) − P (µ′ )⟩ ⩾ ∥P (µ) − P (µ′ )∥2 .
– 127 – – 128 –
4.3. Optimisation quadratique Chapitre 4. Convexité
L’avantage de cette idée est qu’elle fonctionne bien et converge sous peu d’hypo- ce qu’il fallait démontrer. ■
thèses. Il s’agit d’un résultat dû à Uzawa 4 , qui a donné son nom à la méthode. Nous
allons ici considérer le cas où le pas t est constant. Remarque 4.3.11. Le même résultat reste valable si les contraintes h1 , · · · , hp sont seule-
ment supposées convexes, mais la preuve est alors plus compliquée et nous avons par
Théorème 4.3.10 (Convergence de la méthode d’Uzawa) On suppose que les préféré nous restreindre à ce cadre plus élémentaire.
contraintes sont qualifiées en e
x. Soit λ0 > 0 la plus petite valeur propre de A. Alors, Remarque 4.3.12. On notera que la démonstration implique que la suite (µk )k∈N est
pour tout bornée, mais pas qu’elle converge. De fait, cela n’est pas vrai en général. Par contre, si
t ∈]0; 2λ0 /∥H∥2 [, H est surjective, alors la matrice HH t est inversible et on a donc
la suite (xk )k∈N converge vers e
x.
µk = (HH t )−1 (Axk + b) ,
– 129 – – 130 –
4.4. D’un bon pas Chapitre 4. Convexité
– 131 – – 132 –
4.4. D’un bon pas Chapitre 4. Convexité
Alors, g est de classe C 1 , donc par le Théorème fondamental de l’analyse, qui s’écrit aussi
1
Z
1
g(1) = g(0) + g ′ (s)ds ∥∇f (y) − ∇f (x)∥2
f (x) − f (y) ⩽ ∇f (x), x − ∇f (x), y −
2γ
0
Z1
1
= g(0) + g ′ (0) + g ′ (s) − g ′ (0)ds. ∥∇f (x) − ∇f (y)∥2
f (y) − f (x) ⩽ ∇f (y), y − ∇f (y), x −
0 2γ
Par dérivation des fonctions composées, on a g ′ (s) = ⟨∇f (x + s(y − x)), y − x⟩, d’où En sommant ces deux inégalités on obtient le résultat dont nous avons besoin, à savoir
1
g ′ (s) − g ′ (0) = ⟨∇f (x + s(y − x)) − f (x), y − x⟩ ∇f (x) − ∇f (y), x − y ⩾ ∥x − y∥2 .
2γ
⩽ ∥∇f (x + s(y − x)) − f (x)∥∥y − x∥
⩽ γ∥s(y − x)∥∥y − x∥ On conclut simplement en remplaçant α par 1/2γ dans l’énoncé de la Proposition
2 4.4.1. ■
= sγ∥y − x∥ .
Remarque 4.4.4. La preuve donne même un peu plus : s’il existe 0 < a < b < 1/γ 3 tels
Ainsi, que pour tout k ∈ N, tk ∈ [a; b], alors la suite (xk )k∈N converge vers e
x.
γ
g(1) ⩽ g(0) + g ′ (0) + ∥y − x∥2 ,
2
ce qui en revenant à la définition donne 4.4.2 Optimiser l’optimisation
γ
f (y) ⩽ f (x) + ⟨∇f (x), y − x⟩ + ∥y − x∥2 . On pourra objecter à ce qui précède que le choix d’un pas constant est une solu-
2 tion de facilité. En effet, à chaque étape, parmi tous les pas possibles, certains sont
“meilleurs” que d’autres au sens où pour tk , tk′ on peut avoir
En appliquant l’inégalité précédente à y = x et z = x − ∇f (x)/γ, on obtient
! * + f (xk − tk ∇f (xk )) < f (xk + tk′ ∇f (xk )).
∇f (x) ∇f (x) 1
f x− ⩽ f (x) + ∇f (x), − + ∥∇f (x)∥2 Il serait donc probablement plus efficace de choisir, à chaque étape un pas qui donne la
γ γ 2γ
1 valeur de f la plus petite possible : un pas optimal ! Des ennuis se profilent néanmoins à
= f (x) − ∥∇f (x)∥2 . l’horizon : comment savoir si un tel pas optimal existe et surtout comment le trouver ?
2γ
Si l’on a recours à un algorithme, alors on multiplie les complexité des deux méthodes,
Le membre de gauche est plus grand que f (e x) par définition d’un minimum global, ce qui risque de largement compenser le gain obtenu par le choix plus judicieux du
donc on a finalement pas.
1
f (e
x) ⩽ f (x) − ∥∇f (x)∥2 . Nous allons ici nous concentrer sur un cas pour lequel cette méthode est efficace,
2γ
et c’est celui des fonctions quadratiques. Pourquoi ? Parce qu’alors, on sait résoudre ex-
Pour conclure, nous allons maintenant recourir à une astuce. Les points x et y étant plicitement le problème de minimisation à chaque pas et qu’il n’y a donc pas besoin de
fixés, on définit deux fonctions f1 , f2 : U → R par combiner avec une seconde méthode. Plus concrètement, nous allons nous concentrer
( sur une fonction f : Rn → R définie par
f1 (z) = f (z) − ∇f (x), z
f2 (z) = f (z) − ∇f (y), z 1
f (x) = ⟨Ax, x⟩ + ⟨b, x⟩
2
Ces deux fonctions sont convexes – en effet,
et, pour assurer l’existence d’un minimum, nous supposerons A définie positive. Une
⟨∇f1 (z), z′ − z⟩ = ⟨∇f (z), z′ − z⟩ − ⟨∇f (x), z′ − z⟩ fois fixé un point de départ x0 ∈ Rn , nous allons chercher un pas optimal, c’est-à-dire
une valeur de t qui minimise la quantité
⩽ ⟨f (z′ ) − f (z) − ⟨∇f (x), z′ − z⟩
= f1 (z′ ) − f1 (z) f (xk − t∇f (xk )).
ce qui suffit par la Proposition 4.2.11, et de même pour f2 – et ont un minimum global La première chose à faire est de s’assurer que cette valeur existe. Bien sûr, si ∇f (xk ) = 0,
en x et y respectivement, d’où alors on a trouvé le minimum et on peut arrêter l’itération. Nous allons donc supposer
que ce n’est pas le cas.
1 Lemme 4.4.5. On suppose que ∇f (xk ) , 0. Alors, il existe une valeur optimale tk de t, qui
∥∇f1 (y)∥2
f1 (x) ⩽ f1 (y) −
2γ est donnée par
∥∇f (xk )∥2
1
∥∇f2 (x)∥2
f2 (y) ⩽ f2 (x) −
tk = .
2γ ⟨A∇f (xk ), ∇f (xk )⟩
– 133 – – 134 –
4.4. D’un bon pas Chapitre 4. Convexité
n
g(t) = f (xk − t∇f (xk )). X
∥x∥2A = λi xi2
i=1
Elle est de classe C ∞ , et sa dérivée est donnée par n
X
⩽ λn xi2
g ′ (t) = − ∇f (xk − t∇f (xk )), ∇f (xk )
i=1
= − A(xk − t∇f (xk )) + b, Axk + b n
X
= −∥Axk + b∥2 + t⟨A∇f (xk ), Axk + b⟩ = λn xi2
i=1
= t⟨A∇f (xk ), ∇f (xk )⟩ − ∥∇f (xk )∥2 . 2
= λn ∥x∥ .
On voit qu’il y a un unique point critique. Comme d’autre part g est une fonction
polynomiale du second degré, ce point critique est un extremum global. Enfin, g(t) → Notons que (v1 , · · · , vn ) est également une base orthonormée de vecteurs propres
+∞ quand t → +∞, donc le point critique doit être un minimum global, ce qui conclut pour A−1 et que sa plus grande valeur propre est λ−1 1 . Donc, le même calcul donne
la preuve. ■ ∥x∥A−1 ⩽ λ−1 2
1 ∥x∥ , de sorte que finalement
Lemme 4.4.6. Soient λ1 et λn respectivement la plus petite et la plus grande valeur propre Théorème 4.4.8 On suppose A définie positive. Alors, la méthode de gradient à
de A. Alors, pour tout x ∈ Rn , pas optimal converge quel que soit le point de départ x0 .
∥x∥4 λ
⩾ 1.
∥x∥2A ∥x∥2 −1 λn A Démonstration. En utilisant la notation ∥ · ∥A , le pas optimal peut s’écrire
Démonstration. Soit (v1 , · · · , vn ) une base orthonormée de vecteurs propres de A. Si x ∈ ∥∇f (xk )∥2
tk = .
Rn , il se décompose sur la base précédente de la façon suivante : ∥∇f (xk )∥2A
n
X L’idée est de chercher à évaluer ∥xk − e
x∥A plutôt que la distance en norme usuelle. En
x= xi vi . effet, on a
i=1
6. On peut sans peine vérifier que la fonction (x, y) 7→ ⟨Ax, y⟩ est symétrique et définie positive sur
x∥2A = ⟨A(xk+1 − e
∥xk+1 − e x), xk+1 − e
x⟩
Rn ,et que par conséquent elle donne bien lieu à une norme comme le suggère la notation. = ⟨A(xk − tk ∇f (xk )) − Ae
x, xk − tk ∇f (xk ) − e
x⟩
7. Rappelons que toutes les normes étant équivalentes du Rn , il est de fait possible de comparer ∥x∥A
à ∥x∥. = ⟨A(xk − e
x), xk − e x), ∇f (xk )⟩ + tk2 ⟨A∇f (xk ), ∇f (xk )⟩
x⟩ − 2tk ⟨A(xk − e
– 135 – – 136 –
4.4. D’un bon pas
En remarquant que Ae
x = −b puisque ∇f (e
x) = 0, on peut poursuivre le calcul
x∥2A = ∥xk − e
∥xk+1 − e x∥2A − 2tk ∥∇f (xk )∥2 + tk2 ∥∇f (xk )∥2A
∥∇f (xk )∥4 ∥∇f (xk )∥4
x∥2A − 2
= ∥xk − e +
∥∇f (xk )∥2A ∥∇f (xk )∥2A
∥∇f (xk )∥4
x∥2A −
= ∥xk − e .
∥∇f (xk )∥2A
Afin d’aller plus loin, nous allons insérer une troisième norme : celle associée à A−1 .
En effet, on a
x∥2 = ⟨A(xk − e
∥xk − e x), xk − e
x⟩
x), A−1 A(xk − e
= ⟨A(xk − e x)⟩
x)∥2A−1
= ∥A(xk − e
= ∥∇f (xk )∥2A−1 .
Ainsi,
∥∇f (xk )∥4
x∥2A = ∥xk − e
∥xk+1 − e x∥2A − ∥xk − e x∥2A
∥∇f (xk )∥2A ∥∇f (xk )∥2A−1
∥∇f (xk )∥4
x∥2A 1 −
= ∥xk − e .
∥∇f (xk )∥2A ∥∇f (xk )∥2A−1
Il ne reste plus pour conclure qu’à appliquer le Lemme 4.4.6 pour obtenir
!
λ
x∥2A 1 − 1 .
x∥2A ⩽ ∥xk − e
∥xk+1 − e
λn
Comme on a par une récurrence immédiate
!k
λ1
x∥2A ⩽ ∥x0 − e
∥xk+1 − e x∥2A 1 − ,
λn
on conclut que ∥xk − e
x∥A → 0.
Nous n’avons pas tout à fait terminé, puisque nous n’avons pas montré que ∥xk −
x∥ → 0. Néanmoins, ceci se fait sans difficulté. En effet, nous savons que pour tout
x ∈ Rn , ∥x∥A ⩾ λ1 ∥x∥, et donc
1
x∥ ⩽
∥xk − e ∥x − x∥A → 0.
λ1 k
■
– 137 –
Annexe A. Un théorème de Fubini facile
Démonstration. Le Lemme A.1 assure que les deux termes de l’égalité sont bien définis.
De plus, on a, en utilisant une somme de Riemann et la linéarité de l’intégrale,
Nous avons utilisé, dans la démonstration du Théorème 2.3.21, une propriété per-
Z b Z d ! Zb
mettant d’intervertir des intégrales. Si le Théorème de Fubini permet bien sûr de justi-
fier cette interversion, il existe en fait une justification beaucoup plus simple. Cela est f (x, y)dy dx = Fy dx
a c a
dû au fait que la fonction considérée est continue et que les intégrales portent sur des n !
1 X b−a
segments. Nous allons donc énoncer et démontrer un résultat d’interversion qui suffit = lim Fy a + k
n→+∞ n + 1 n
à nos besoins et ne nécessite que des propriétés classiques de l’intégrale de Riemann. k=0
n Z d !
Soit f : U → R une fonction continue et soit R = [a; b] × [c; d] un rectangle contenu 1 X b−a
= lim f a+k , y dy
dans U . Avant de démontrer le résultat, nous allons vérifier que l’égalité a bien un n→+∞ n + 1 n
k=0 c
sens, c’est-à-dire que chaque intégrande est bien intégrable au sens de Riemann. Cela Zd n !
sera facile car elles sont tout simplement continues. 1 X b−a
= lim f a+k , y dy.
n→+∞ c n + 1 n
k=0
Lemme A.1. Les fonctions
Posons, pour n ∈ N,
n !
Z b 1X b−a
Fx : y 7→ f (x, y)dx gn (y) = f a+k ,y .
n n
a k=1
Z d
Nous allons montrer que la suite (gn )n∈N converge uniformément vers Fx , ce qui per-
Fy : x 7→ f (x, y)dy
c mettra de conclure.
Soit ϵ > 0. En posant, pour 0 ⩽ k ⩽ n,
sont continues, donc intégrables.
b−a
ak = a + k
n
Démonstration. Nous ne traiterons que la première fonction, la preuve pour la seconde
et utilisant la Relation de Chasles, on a
est la même, mutatis mutandis. Soit ϵ > 0. La fonction f étant continue sur le rectangle
[a; b] × [c; d] qui est compact, elle est uniformément continue. Il existe donc η > 0 tel n−1 Z
1 X ak+1
!
b−a
que dès que ∥(x, y) − (x′ , y ′ )∥ < η, on a gn (y) − Fx (y) = f a+k , y − f (x, y) dy
n+1 n
k=0 ak
|f (x, y) − f (x′ , y ′ )| < ϵ/(b − a). 1
n−1 Z ak+1
X b−a
!
⩽ f a+k , y − f (x, y) dy
n+1 ak n
1. C’est surtout par l’habitude et l’exercice qu’on acquiert la facilité k=0
– 140 –
Comme f est continue sur le rectangle R qui est compact, elle est uniformément continue
par le Théorème de Heine. Par conséquent, il existe η > 0 tel que ∥(x, y) − (x′ , y ′ )∥ < η
implique
|f (x, y) − f (x′ , y ′ )| < ϵ.
Soit N tel que (b − a)/N < η. Alors, dans chaque terme de la somme, l’intégrande est
majorée par ϵ. Par conséquent, pour tout n ⩾ N ,
n−1 Z ak+1
1 X
gn (y) − Fx (y) ⩽ ϵdy
n+1 ak
k=0
n
=ϵ
n+1
< ϵ.
Ceci montre que ∥gn − Fx ∥∞ < ϵ pour tout n ⩾ N , donc que la suite converge uniformé-
ment. Le Théorème de convergence uniforme pour l’intégrale de Riemann donne
alors le résultat. ■
– 141 –
Annexe B. L’envers de l’endroit : les théorèmes d’inversion
ANNEXE B Nous arrivons au moment où naît en nous un espoir : la condition nécessaire pourrait-
elle être suffisante ? Pour avoir une meilleur intuition, considérons le cas d’une seule
variable. On a alors une fonction f : I → R et un point x ∈ I tel que f ′ (x) , 0. Si f est
L’ENVERS DE L’ENDROIT : LES THÉORÈMES de classe C 1 , la continuité de f ′ assure l’existence d’un intervalle J ⊂ I sur lequel f ′ est
de signe constant strict. Alors, f est strictement monotone sur J, donc inversible ! De
D’INVERSION plus, le résultat classique sur les fonction bijectives dérivables dont la dérivée de s’an-
nule pas assure que f −1 sera dérivable, et même de classe C 1 . Nous voilà convaincus
que notre condition nécessaire est suffisante. Le démontrer dans le cas de plusieurs
variables n’est cependant pas chose aisée ... à moins d’utiliser habilement le Théorème
des fonctions implicites !
Nous avons mentionné au Paragraphe 3.1.2 du Chapitre 3 que le Théorème des Théorème B.3 (Théorème d’inversion locale) Soit f : U → Rn une fonction de
fonctions implicites 3.1.6 possède un proche parent connu sous le nom de Théorème classe C k et soit x ∈ U tel que Dx f est inversible. Alors, il existe un ouvert V ⊂ U
d’inversion locale. Nous allons maintenant discuter un peu plus en détail ce dernier, contenant x et un ouvert W ⊂ Rm contenant f (x) tels que f (V ) = W et la restriction
ainsi que son inséparable comparse le Théorème d’inversion globale. de f à V est un C k -difféomorphisme.
Le problème de départ est assez naturel : existe-t-il un moyen simple de s’assu-
rer qu’une application f : U → Rm de classe C k est une bijection ? Et si possible une Démonstration. Attention, astuce droit devant ! Considérons les applications gi : R2n →
bijection dont l’inverse est également de classe C k ? Suivant un procédé éprouvé des R définies par
mathématiques, il est sage de commencer par aborder le problème localement. Autre- gi (z1 , · · · , z2n ) = zi − fi (zn+1 , · · · , z2n ).
ment dit, étant donné x ∈ U , à quelle condition existe-t-il un ouvert V ⊂ U contenant x pour 1 ⩽ i ⩽ n. En posant ex = (f (x), x), on observe que gi (e
x) = 0. De plus, les n dernières
et un ouvert W dans Rm contenant f (x) tel que f soit une bijection de V sur W dont la coordonnées de ∇gi ne sont autres que les dérivées partielles de fi , tands que les n
réciproque est de classe C k ? Avant d’aller plus loin remarquons l’hypothèse que W soit premières sont les colonnes de la matrice identité. Par conséquent, la matrice dont les
un ouvert. Cela est indispensable si on veut que la réciproque soit au moins continue. colonnes sont les ∇gi est :
En effet, W sera alors la préimage par f −1 de V qui est ouvert ! I 0
!
x) = n
Jg (e .
Maintenant, commençons par chercher une condition nécessaire. Si nous cherchons 0 Jf (e
x)
dans notre mémoire (ou dans le début de ce texte), nous voyons que pour calculer la Ainsi, comme Jf (x) est inversible, la famille de vecteurs
différentielle d’une fonction réciproque f −1 , il nous faut supposer que la différentielle
de f au point correspondant est inversible. Cela dit, ceci pourrait n’être qu’une condi- ∇g1 (e
x), · · · , ∇gn (e
x)
tion suffisante pratique pour les calculs. Vérifions qu’il n’en est rien, en commençant est libres. On peut donc appliquer le Théorème des fonctions implicites : il existe un
par introduire une terminologie bien pratique. ouvert W contenant f (x), un ouvert V contenant x et une application ϕ : W → V de
Définition B.1. Une application f : U → Rm est un C k -difféomorphisme si elle est de classe C k telle que pour tous (z, z′ ) ∈ W × V et tout 1 ⩽ i ⩽ n,
classe C k , bijective, et que sa réciproque f −1 est également de classe C k .
gi (z, z′ ) = 0 ⇐⇒ z′ = ϕ(z).
Nous pouvons maintenant démontrer notre condition nécessaire, qui au passage L’équation de gauche est équivalente à z = f (z′ ), donc ϕ est une réciproque de f , ce qui
nous donnera également une information sur la dimension de l’espace d’arrivée. Il est démontre le théorème. ■
fructueux d’accorder un instant d’attention à sa proximité – mais surtout ses diffé-
rences – avec le Corollaire 2.3.13. Nous avons obtenu ci-dessus une solution “locale” à notre problème, qui est de
plus optimale au sens où nous avons une équivalence : f est un difféomorphisme au
voisinage de x si et seulement si Dx f est inversible. L’étape suivante est de s’interroger
sur la possibilité d’un critère global. Pour cela, il est sain de chercher en premier lieu
ce qui peut faillir dans la caractérisation précédente. Autrement dit : à quoi ressemble
Proposition B.2. Soit f : U → Rm un C k -difféomorphisme. Alors, pour tout x ∈ U , l’appli- une fonction qui est un homéomorphisme au voisinage de tout point mais qui n’est pas
cation linéaire Dx f est inversible, d’inverse Df (x) (f −1 ). De plus, on doit avoir m = n. un homéomorphisme global ? Il est en fait assez simple de donner un exemple.
– 144 –
Exemple B.4. On considère U =]0; 1[∪]2; 3[ qui est un ouvert de R et la fonction f :
U → R définie par (
x si x ∈]0; 1[
f (x) =
x − 2 si x ∈]2; 3[.
Cette fonction est de classe C ∞ et sa différentielle en tout point est l’application linéaire
identité de R dans R, qui est inversible. Pourtant, f n’est pas un difféomorphisme,
puisqu’elle n’est pas injective : f (1/2) = f (3/2).
Démonstration. Comme le suggère l’énoncé, nous allons commencer par montrer que
f (U ) est ouvert. Soit donc y ∈ f (U ) et x ∈ U tel que f (x) = y. D’après le Théorème
B.3, il existe un ouvert V ⊂ U contenant x et un ouvert W contenant f (x) tel que la
restriction de f : V → W soit un C k -difféomorphisme. En particulier, W = f (V ) ⊂ f (U )
donc f (U ) est ouvert.
Comme f est supposée injective, l’application f : U → f (U ) est bijective. De plus, si
y = f (x) ∈ f (U ) et si les ouverts V et W sont comme précédemment, alors la restriction
de f −1 à W coïncide avec l’application donnée par le Théorème B.3, qui est de classe C k .
Ainsi, f −1 est de classe C k au voisinage de chaque point, donc elle est bien globalement
de classe C k , ce qui conclut la preuve. ■
– 145 –
Annexe C. Tangence
Le choix de la lettre c n’est pas anodin, elle a pour but d’évoquer un chemin. En
effet, l’idée cachée derrière l’objet que nous venons de définir provient de la physique :
il s’agit de suivre le déplacement d’un point le long d’un chemin et de regarder ses
“vecteurs vitesses”, qui sont les vecteurs c′ (t). Ainsi, les vecteurs tangents au point x
sont les vecteurs qui peuvent décrire la vitesse instantanée au point x d’un point se
déplaçant sur S.
Il n’est pas évident sur la définition précédente que les vecteurs vitesse forment un
sous-espace vectoriel de Rn , ni encore moins qu’ils ont quelque chose avoir avec Tx S.
ANNEXE C Et pourtant ...
Je m’étais mis à choyer immodérément les mots pour l’espace qu’ils admettent autour d’eux,
pour leurs tangences avec d’autres mots innombrables.
Démonstration. Soit v un vecteur tangent à S au point x et c la fonction correspondante.
A. Breton, Manifeste du surréalisme
Si on note (c1 , · · · , cn ) les coordonnées de la fonction c, posons e
c = (c1 , · · · , cn−p ). Comme
U × V est un ouvert contenant x et que c est en particulier continue, il existe ϵ′ > 0 tel
que c(t) ∈ U × V pour tout t ∈] − ϵ′ ; ϵ′ [. Par conséquent, pour de tels t on a
Nous allons dans ce bref appendice donner quelques éléments pour mieux appré-
hender la notion d’espace tangent à une sous-variété, introduite au Paragraphe 3.1.3 c(t) = (e
c(t), ϕ ◦ e
c(t)).
du Chapitre 3. Rappelons pour plus de confort la définition de sous-variété que nous
avions alors introduite : Si cette égalité en t = 0, on obtient alors
Définition C.0.1. Une sous-variété de Rn de codimension p et de classe C k est une partie c′ (0) = (e
c′ (0), Dx ϕ(e
c(0))) ∈ Tx S.
S ⊂ Rn telle que pour tout x ∈ S, quitte a permuter les coordonnées, il existe
Réciproquement, soit v ∈ Tx S. Il existe donc x ∈ Rn−p tel que
• Un ouvert U de Rn−p ;
v = (w, Dx ϕ(w)) .
• Un ouvert V de Rp ;
Soit maintenant e
x = (x1 , · · · , xn−p ) ∈ U et r > 0 tel que B(e
x, r) ⊂ U . En posant ϵ = r/∥w∥,
• Une application ϕ : U → V de classe C k telle que x ∈ U × V et on aque pour tout t ∈] − ϵ; ϵ[,
x + tw) − e
∥(e x∥ < r,
S ∩ (U × V ) = Sϕ .
x + tw ∈ U . Par conséquent, la fonction c :] − ϵ; ϵ[→ Rn définie par
donc que e
Pour montrer que c’est bien le cas, nous allons donner une autre description de cet ■
espace tangent qui n’utilisera cette fois que S en tant qu’ensemble. Cette description
repose sur une notion de vecteur tangent que nous introduisons maintenant.
Définition C.1. Un vecteur v ∈ Rn est dit tangent à S en un point x s’il existe ϵ > 0 et
une fonction continue c :] − ϵ; ϵ[→ S dérivable telle que
• c(0) = x ;
• c′ (0) = v.
– 148 –
Annexe D. In cauda venenum
il faut prévoir un cas d’exception pour renvoyer alors l’information. Autrement dit, on
retournera alors un message indiquant que l’algorithme n’a pas pu conclure.
Concluons par un aspect plus concret : Python dispose de nombreuses librairies
contenant des outils divers en fonction des besoins. Dans notre cas, il faudra pouvoir
manipuler des vecteurs et des matrices et ceci peut se faire à l’aide de la librairie numpy.
Il faudra donc commencer ainsi :
import numpy as np
ANNEXE D
– 150 –
D.3. Algorithme d’Uzawa Annexe D. In cauda venenum
return(xn)
xnplusun = xn - dot(Hn , f(xn))
D.4 Descente de gradient
an = dot(transpose(xnplusun - xn), dot(Hn , f(xnplusun) - f(xn)))
Hn = Hn + (( xnplusn - xn - dot(Hn , f(xnplusun) - f(xn))/an) * Hn D.4.1 À pas constant
xn = xnplusun
return("Echec")
Rappelons tout d’abord que le but de cette méthode est de chercher un point cri-
tique d’une fonction f : Rn → R en partant d’un point x0 ∈ Rn et en définissant par
récurrence une suite par la relation
D.3 Algorithme d’Uzawa xn+1 = xn − t∇f (xn ),
L’algorithme d’Uzawa, détaillé au Paragraphe 4.3.2, ne cherche pas les zéros d’une où t > 0 est le pas de la méthode. Comme dans le cas précédent, le pas t sera inclus
fonction mais le minimum d’une fonction quadratique sous contraintes d’inégalité. comme variable de l’algorithme afin de pouvoir aisément l’ajuster.
Ceci signifie que le choix de la condition d’arrêt n’est pas aussi immédiat. En effet, Pour tester la précision d’une itération donnée, le plus simple est de calculer la
puisqu’on ne connaît pas le point e x auquel le minimum est atteint, on ne peut calcu- norme du gradient ∥∇f (xn )∥. En effet, l’algorithme converge vers un point critique de f ,
ler ∥e
x − xn ∥ pour estimer la qualité de l’approximation. Une solution est d’utiliser les qui vérifie donc ∇f (x) = 0. La fonction f étant supposée de classe C 1 , ∇f sera petit dans
conditions KKT, et de s’arrêter quand ces dernières sont satisfaites à ϵ près, c’est-à-dire un voisinage de x, donc on peut décider de s’arrêter lorsque ∥∇f (xn )∥ < ϵ. On obtient
quand alors l’algorithme suivant, qui ne nécessite d’ailleurs pas de prendre f en argument
Axn + b − H t µn < ϵ. mais seulement son gradient. Remarquons que le gradient est utilisé deux fois dans
l’itération : pour vérifier la condition d’arrêt, puis pour calculer la nouvelle valeur de
Pour implémenter l’Algorithme d’Uzawa, nous aurons également besoin de la pro- xn . Il est donc judicieux de le calculer une seule fois, au début de la boucle, et de stocker
jection P sur Rp− . Celle-ci peut se définir sans peine à l’aide de la fonction min de Py- sa valeur dans une variable temporaire grad qu’on appellera ensuite.
thon, qui utilise le même ordre sur les vecteurs que nous (c’est-à-dire la comparaison
coordonnée par coordonnée).
def GradienAPasConstant (gradf , t, x0 , epsilon , N):
xn = x0
def P(x): for n in range(N):
min(0, x) grad = gradf(xn)
if norm(grad) < epsilon:
return(xn)
Cela dit, on peut également directement utiliser la fonction min dans l’algorithme, xn = xn - t * grad
ce que nous allons faire. Regardons maintenant les arguments de la fonction. Il nous print("Erreur")
faudra la matrice A et le vecteur b définissant la forme quadratique, ainsi que la matrice
H et le vecteur d définissant les contraintes. Nous aurons également besoin d’un vecteur
de départ mu0 ainsi que d’un pas t 2 . Enfin, les indispensables tolérance epsilon et D.4.2 À pas optimal
nombre maximal d’itérations N.
Avant de donner le code, ajoutons un détail : il est préférable de calculer dès le Pour la méthode du gradient à pas optimal, le seul changement est que l’on doit à
début les matrices B = A−1 et K = H t afin de ne pas refaire ce calcul à chaque fois 3 . chaque étape calculer le nouveau pas. Dans le cas quadratique, qui est le seul auquel
nous nous sommes intéressés, ce pas se calcule facilement grâce à une formule expli-
cite, ce qui simplifie l’algorithme. De plus, la donnée du problème étant réduite à la
def Uzawa(A, b, H, d, mu0 , t, epsilon , N):
B = [Link](A) matrice symétrique définie positive A et au vecteur b, ce sont ces deux quantités qui
K = [Link] () apparaîtront comme variables plutôt que la fonction f . Cela permettra de simplifier
mun = mu0 également le calcul du gradient, qu’on prendre soin de n’effectuer qu’une seule fois par
xn = [Link](B, [Link](K, mun)-b) itération à l’aide d’une variable auxiliaire comme précédemment.
for n in range(N):
if norm([Link](A, xn) + b - [Link](K, mun)) < epsilon:
return(xn) def GradientAPasOptimal (A, b, x0 , epsilon , N):
mun = min(0, mun - t * ([Link](K, xn) - d)) xn = x0
xn = [Link](B, [Link](K, mun)-b) for n in range(N):
return("Echec") grad = dot(A, xn) - b
if norm(grad) < epsilon:
return(xn)
2. Inclure le pas comme variable permet de facilement tester plusieurs valeurs, afin par exemple tn = (norm(grad)^4)/(dot(dot(A, grad), grad)^2)
d’améliorer la vitesse de convergence si l’algorithme échoue à renvoyer une valeur. xn = xn - tn * grad
3. On pourrait aussi envisager de ne jamais calculer A−1 et d’appeler un algorithme pour résoudre print("Erreur")
numériquement l’équation Axn + b = H t µn à chaque étape, si ceci s’avère pertinent.
– 151 – – 152 –
BIBLIOGRAPHIE
[1] P. Ciarlet & J.-L. Lions – Introduction à l’analyse numérique matricielle et à l’opti-
misation, Sciences Sup, Dunod, 2007.
[5] M. Hoy, J. Livernois, C. McKenna, R. Rees & T. Stengos – Mathematics for Econo-
mics, MIT press, 2022.
[9] C. Simon & L. Blume – Mathematics for economists, Norton, New York, 1994.