Retrouver ce titre sur Numilog.

com

COLLECTION ENSEIGNEMENT SUP //// Mathématiques

L3M1

Optimisation
et analyse convexe
EXERCICES CORRIGÉS

Jean-Baptiste Hiriart-Urruty
 Retrouver ce titre sur Numilog.com

OPTIMISATION
ET
ANALYSE CONVEXE
Exercices et problèmes corrigés,
avec rappels de cours

Jean-Baptiste Hiriart-Urruty

Collection dirigée par Daniel Guin

17, avenue du Hoggar

Parc d’activités de Courtabœuf, BP 112
91944 Les Ulis Cedex A, France
 Retrouver ce titre sur Numilog.com

Illustration de couverture : un corps convexe d’épaisseur presque constante et son

ombre ; reproduit avec la gracieuse permission de Christof Weber (université de
Zurich).

Imprimé en France

ISBN : 978-2-7598-0373-6
Tous droits de traduction, d’adaptation et de reproduction par tous procédés réservés pour tous
pays. Toute reproduction ou représentation intégrale ou partielle, par quelque procédé que ce soit, des
pages publiées dans le présent ouvrage, faite sans l’autorisation de l’éditeur est illicite et constitue une
contrefaçon. Seules sont autorisées, d’une part, les reproductions strictement réservées à l’usage privé
du copiste et non destinées à une utilisation collective, et d’autre part, les courtes citations justifiées
par le caractère scientifique ou d’information de l’œuvre dans laquelle elles sont incorporées (art. L.
122-4, L. 122-5 et L. 335-2 du Code de la propriété intellectuelle). Des photocopies payantes peuvent
être réalisées avec l’accord de l’éditeur. S’adresser au : Centre français d’exploitation du droit de copie,
3, rue Hautefeuille, 75006 Paris. Tél. : 01 43 26 95 35.


c 2009, EDP Sciences, 17, avenue du Hoggar, BP 112, Parc d’activités de Courtabœuf,
91944 Les Ulis Cedex A
 Retrouver ce titre sur Numilog.com

TABLE DES MATIÈRES

Introduction v

Abréviations et notations ix

I Révision de bases : calcul différentiel, algèbre linéaire

et bilinéaire 1
I.1 Algèbre linéaire et bilinéaire . . . . . . . . . . . . . . . . . . . 1
I.2 Calcul différentiel . . . . . . . . . . . . . . . . . . . . . . . . . 2
I.3 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . 3

II Minimisation sans contraintes. Conditions de minimalité 41

II.1 Conditions de minimalité du premier ordre . . . . . . . . . . . 41
II.2 Conditions de minimalité du second ordre . . . . . . . . . . . . 42

III Minimisation avec contraintes. Conditions de minimalité 63

III.1 Conditions de minimalité du premier ordre . . . . . . . . . . . 63
III.2 Cône tangent, cône normal à un ensemble . . . . . . . . . . . . 65
III.3 Prise en compte de la convexité . . . . . . . . . . . . . . . . . 66
III.4 Conditions de minimalité du second ordre . . . . . . . . . . . . 66

IV Mini-maximisation. Dualisation de problèmes

de minimisation convexe 127
IV.1 Points-selles (ou cols) ; problèmes de mini-maximisation . . . . 127
IV.2 Points-selles de lagrangiens . . . . . . . . . . . . . . . . . . . . 128
IV.3 Premiers pas dans la théorie de la dualité . . . . . . . . . . . . 129
 Retrouver ce titre sur Numilog.com

Optimisation et analyse convexe

V Polyèdres convexes fermés. Optimisation à données affines

(Programmation linéaire) 165
V.1 Polyèdres convexes fermés . . . . . . . . . . . . . . . . . . . . 165
V.2 Optimisation à données affines (Programmation linéaire) . . . 168
V.2.1 Définitions et notations . . . . . . . . . . . . . . . . . 168
V.2.2 Résultats fondamentaux d’existence . . . . . . . . . . 170
V.3 La dualité en programmation linéaire . . . . . . . . . . . . . . 171
V.3.1 Formulations de problèmes duaux . . . . . . . . . . . . 171
V.3.2 Relations entre les valeurs optimales et les solutions
de programmes linéaires en dualité . . . . . . . . . . . 172
V.3.3 Caractérisation simultanée des solutions du problème
primal et du problème dual . . . . . . . . . . . . . . . 173

VI Ensembles et fonctions convexes. Projection sur un convexe

fermé 217
VI.1 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . 217
VI.1.1 Ensembles convexes associés à un convexe donné . . . 217
VI.1.2 Enveloppe convexe, enveloppe convexe fermée . . . . . 218
VI.1.3 Hyperplan d’appui, fonction d’appui . . . . . . . . . . 219
VI.1.4 Théorèmes de séparation par un hyperplan affine . . . 219
VI.2 Projection sur un convexe fermé . . . . . . . . . . . . . . . . . 220
VI.3 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . 220

VII Initiation au calcul sous-différentiel et de transformées

de Legendre-Fenchel 271
VII.1 La transformation de Legendre-Fenchel . . . . . . . . . . . . . 271
VII.1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . 271
VII.1.2 Quelques propriétés et règles de calcul . . . . . . . . . 272
VII.2 Le sous-différentiel d’une fonction . . . . . . . . . . . . . . . . 273
VII.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . 273
VII.2.2 Quelques propriétés et règles de calcul . . . . . . . . . 274
VII.3 La convexification d’une fonction . . . . . . . . . . . . . . . . . 275

Sources 323

Références générales 325

Notice historique 327

Index 331

iv
 Retrouver ce titre sur Numilog.com

INTRODUCTION

« Good modern science implies good variational problems »

M.S. Berger (1983)

Le recueil d’exercices et problèmes corrigés que nous proposons ici concerne

les domaines des Mathématiques répertoriées sous les vocables d’Optimisation
et Analyse convexe. L’Optimisation est traitée dans ses aspects suivants : la clé
de voûte que constituent les conditions d’optimalité (chapitres II et III) ; le rôle
(incontournable) de la dualisation de problèmes (chapitre IV) ; le monde particu-
lier (et toujours en haut de l’affiche depuis ses débuts) de l’Optimisation linéaire
(chapitre V). L’Analyse convexe (moderne) n’est pas traitée en tant que telle mais
par l’utilisation qu’on peut en avoir en Optimisation ; il s’agit en fait d’une initia-
tion à la manipulation de concepts et de résultats concernant essentiellement : la
projection sur un convexe fermé (au chapitre VI), le calcul sous-différentiel et de
transformées de Legendre-Fenchel (chapitre VII). L’Analyse linéaire et bilinéaire
(ou, plutôt, l’Analyse matricielle) ainsi que le Calcul différentiel interviennent de
manière harmonieuse en Optimisation et Analyse convexe : un chapitre de revi-
sion des bases leur est consacré (chapitre I). Près de 160 exercices et problèmes
sont corrigés, parfois commentés et situés dans un contexte d’utilisation ou de
développement historique, gradués dans leur difficulté par un, deux ou trois ∗ :
∗ Exercices plutôt faciles (applications immédiates d’un résultat du Cours,
vérification d’un savoir-faire de base, etc.) ;
∗∗ Exercices que le lecteur-étudiant doit pouvoir aborder après une bonne
compréhension et assimilation du Cours. De difficulté moyenne, ce sont de loin
les plus nombreux ;
∗ ∗ ∗ Exercices plus difficiles, soit à cause de certains calculs à mener à bien,
soit simplement en raison d’un degré de maturité plus grand que leur résolution
requiert.
Comme tous les exercices de mathématiques, ceux présentés ici ne seront pro-
fitables au lecteur-étudiant que si celui-ci les travaille, un crayon à la main, sans
 Retrouver ce titre sur Numilog.com

Optimisation et analyse convexe

regarder la correction dans un premier temps. Qu’il garde à l’esprit ce proverbe

chinois :
« J’entends et j’oublie, (cours oral)
je vois et je retiens, (étude du cours)
je fais et je comprends » . (exercices)
Le cadre de travail choisi est volontairement simple (celui des espaces de di-
mension finie), et nous avons voulu insister sur les idées et mécanismes de base
davantage que sur les généralisations possibles ou les techniques particulières à tel
ou tel contexte. Les problèmes dits variationnels requièrent dans leur traitement
une intervention plus grande de la Topologie et de l’Analyse fonctionnelle, à com-
mencer par le cadre – fondamental – des espaces de Hilbert ; ils seront abordés
dans un prochain recueil.
Les connaissances mathématiques pour tirer profit des exercices et problèmes
du recueil présent sont maintenues minimales, celles normalement acquises après
une formation scientifique à Bac + 2 ou Bac + 3 (suivant les cas).
Chaque chapitre débute par des rappels de résultats essentiels, ce qui ne doit
pas empêcher le lecteur-étudiant d’aller consulter les références indiquées à la
fin du livre. L’approche retenue est celle d’une progression en spirale plutôt que
linéaire au sens strict : ainsi, par exemple, la fonction A ∈ Mn (R) −→ ln(détA)
est d’abord considérée pour un calcul de différentielles, puis pour sa convexité,
puis plus tard en raison de son rôle comme fonction-barrière dans des problèmes
d’optimisation matricielle.
Pour ce qui est de l’enseignement, les aspects de l’Optimisation et Analyse
convexe traités en exercices ici trouvent leur place dans les formations de niveau
deuxième cycle universitaire (modules généralistes ou professionnalisés) et dans
la formation mathématique des ingénieurs, sur une durée d’un semestre environ ;
la connaissance de ces aspects est un préalable à des formations plus en aval, en
optimisation numérique par exemple.
La plupart des exercices et problèmes proposés, sinon tous, ont été posés en
séances d’exercices ou examens à l’Université Paul Sabatier de Toulouse.
Je voudrais remercier les anciens étudiants ou jeunes collègues qui ont bien
voulu relire une première version de ce document et y relever une multitude de
petites fautes (il en reste sûrement...), parmi eux : D. Mallard, M. Torki, Y. Lucet,
C. Imbert et J. Benoist. Enfin je ne voudrais pas oublier A. Andrei pour la part
primordiale qui a été la sienne dans la saisie informatique de l’ouvrage.

Toulouse, 1989–1997
J.-B. Hiriart-Urruty

vi
 Retrouver ce titre sur Numilog.com

Introduction

Depuis sa publication il y a dix ans (en mars 1998), cet ouvrage a subi les vicis-
situdes d’un document de formation destiné à un public (d’étudiants en sciences)
en nette diminution. Il a été traduit en russe par des collègues de Kiev (Ukraine)
en 2004, mais la version française originelle n’est plus disponible depuis 2006.
Ainsi, pour répondre à une demande de collègues et étudiants, un nouveau tirage
a été envisagé. Je remercie les éditions EDP Sciences, notamment mon collègue
D. Guin (directeur de la collection Enseignement Sup – Mathématiques), d’avoir
accueilli ce projet. Aude Rondepierre a donné un coup de main pour reprendre
les fichiers informatiques anciens ; qu’elle soit remerciée de sa bonne volonté et
efficacité.

Toulouse, printemps 2009

J.-B. Hiriart-Urruty

vii
 Retrouver ce titre sur Numilog.com

This page intentionally left blank

 Retrouver ce titre sur Numilog.com

ABRÉVIATIONS ET NOTATIONS

:= : égal par définition.

cf. : confer , signifie « se reporter à ».
i.e. : id est , signifie « c’est-à-dire ».
ln : notation normalisée pour le logarithme népérien.

R+ ∗
∗ , R+ ou ]0, +∞[ : ensemble des réels strictement positifs.
+
u : partie positive du réel u.
x = (x1 , . . . , xn ) ou x = (ξ1 , . . . , ξn ) : notation générique pour un vecteur
de Rn .
u+ signifie (u+ +
1 , . . . , un ) lorsque u = (u1 , . . . , un ) ∈ R .
n

Lorque u et v sont deux vecteurs de Rn , u  v signifie « ui  vi pour tout

i = 1, . . . , n ».
{uk } ou (uk ) : notations utilisées pour les suites indexées par des entiers
naturels.
Pour une fonction f différentiable en x (resp. deux fois différentiable en x),
Df (x) désigne la différentielle (première) de f en x (resp. D 2 f (x) désigne la
différentielle seconde de f en x). Si la variable est réelle (et notée t), on utilise la
notation f  (t) (resp. f  (t)) pour la dérivée de f en t (resp. la dérivée seconde de f
en t) [ce sont des éléments de l’espace d’arrivée et non des applications linéaires].
Pour une fonction numérique f définie sur un ouvert O de Rn , différentiable
en x ∈ O (resp. deux fois différentiable en x ∈ O), ∇f (x) (resp. ∇2 f (x)) désigne
le (vecteur) gradient de f en x (resp. la matrice hessienne de f en x).
Lorsqu’elle existe, la dérivée directionnelle de f en x dans la direction d est
notée f  (x, d).
Pour une fonction vectorielle f : O ⊂ Rn → Rm différentiable en x ∈ O, Jf (x)
désigne la matrice jacobienne de f en x (matrice à m lignes et n colonnes).
 Retrouver ce titre sur Numilog.com

Optimisation et analyse convexe

Mm,n (R) : ensemble des matrices (m, n) (m lignes et n colonnes) à coefficients

réels ; Mn (R) est une abréviation de Mn,n (R).
[aij ] : matrice de terme général aij (à la i-ème ligne et j-ème colonne).
diag (λ1 , . . . , λn ) : matrice diagonale dont les éléments diagonaux sont
λ1 , . . . , λn .
In (ou I quand il n’y a pas d’ambiguïté) : matrice-unité de Mn (R), i.e.
diag (1,. . .,1).
A ou t A : transposée de A ∈ Mm,n (R) [les deux notations sont d’un usage
très courant ; par contre At est à proscrire car génératrice de confusions].
Lorsque A est inversible, A− désigne l’inverse de A (ou, ce qui revient au
même, la transposée de A−1 ).
tr A : trace de A ∈ Mn (R).
dét A : déterminant de A ∈ Mn (R).
cof A : matrice des cofacteurs de A ∈ Mn (R), i.e. celle dont le terme (i, j) est
(−1)i+j dét Aij , où Aij est obtenue à partir de A en enlevant la i-ème ligne et la
j-ème colonne.
Sn (R) : ensemble des matrices de Mn (R) qui sont symétriques.

⊕ symbolise la somme directe de sous-espaces vectoriels.

vect{v1 , . . . , vk } : sous-espace vectoriel engendré par les vecteurs v1 , . . . , vk .
Sauf indication contraire, Rn est muni de sa base canonique ; ainsi à A ∈
Mm,n (R) est canoniquement associée une application linéaire de Rn dans Rm ,
d’où les notations Ker A, Im A, etc.
L’isomorphisme canonique de R⎡n sur ⎤ Mn,1 (R) est celui qui à x = (x1 , . . . , xn )
x1
⎢ ⎥
associe la matrice unicolonne X = ⎣ ... ⎦ ; des expressions comme AX (ou Ax) ne
xn
devraient pas arrêter l’étudiant-lecteur. Si, par exemple, u et v sont deux vecteurs
de Rn , uv  est une matrice carrée de taille n dont le terme général est ui vj , alors
n
que u v est la matrice-scalaire (ou scalaire) ui vj .
i=1

·, · ,  ·, · , (· | ·) : notations utilisées pour les produits scalaires (dans
des espaces euclidiens). Sauf indication contraire,
·, · désigne dans Rn le produit
scalaire usuel (celui qui à x = (ξ1 , . . . , ξn ) et y = (η1 , . . . , ηn ) associe
x, y :=
n
ξi ηi , soit encore x y (cf. supra)). Bien des problèmes d’optimisation se posent
i=1
dans des espaces de matrices : si X := Mm,n (R), le produit scalaire standard sur
X est défini par  M, N := tr (M  N ).

x
 Retrouver ce titre sur Numilog.com

Abréviations et notations

Soit A ∈ Mn (R), u et v des vecteurs de Rn : u Av est un(e) (matrice-)

scalaire égal(e) à (sa transposée) uA v ; un mécanisme plus commode

d’utilisation
et engendrant moins de fautes est d’écrire
u, Av = A u, v .
Si l est une application linéaire d’un espace euclidien (E,  ·, · ) dans un
autre espace euclidien (F,
·, ·), l’adjointe l∗ de l est l’application linéaire de F
dans E définie par

 l∗ (y), x =
y, l(x) pour tout (x, y) ∈ E × F.

Si l’on représente l’ensemble des formes linéaires sur E par E via le produit
scalaire  ·, · (idem pour F ), prendre l’adjointe de l ou sa transposée revient
au même. Lorsque E et F sont munies de bases orthonormales (comme c’est le
cas des espaces euclidiens (Rn ,
·, ·) munies de leurs bases canoniques), la matrice
représentant l’adjointe de l (= sa transposée) dans ces bases est la transposée de
la matrice représentant l.
· : norme dans un espace vectoriel normé X. Si X est muni d’un produit
scalaire
·, · (exemples typiques : Rn , Mm,n (R)), et en l’absence d’autres  pré-
cisions, · désignera la norme dérivée du produit scalaire (i.e. · =
·, ·).
Lorsqu’interviennent à la fois des normes de vecteurs et de matrices, on évite les
confusions en utilisant · pour les vecteurs et ||| · ||| pour les matrices).
◦
int S ou S : intérieur de S ; S : adhérence de S ;
fr S : frontière de S.
B(x, r) : boule fermée de centre x et de rayon r.
Δn : simplexe-unité de Rn , c’est-à-dire l’ensemble des (α1 , . . . , αn ) ∈ Rn tels
que α1 + . . . + αn = 1 et αi  0 pour tout i (coefficients qui servent dans la prise
de combinaisons convexes).

A ∈ Sn (R) est dite (symétrique) semi-définie positive lorsque

Ax, x  0
pour tout x ∈ Rn [cette appellation est préférable à « positive » qui peut signifier,
dans certains cas, « à coefficients positifs »]. On désignera par Pn (R) l’ensemble
des matrices semi-définies positives de taille n.
A ∈ Sn (R) est dite (symétrique) définie positive lorsque
Ax, x > 0 pour tout
x = 0 de Rn (ce qui revient à : A semi-définie positive et inversible). On désignera
◦
par Pn (R) l’ensemble des matrices définies positives de taille n.
Le caractère de semi-définie ou définie positivité ne sera considéré dans ce
recueil que pour des matrices symétriques.

xi
 Retrouver ce titre sur Numilog.com

This page intentionally left blank

 Retrouver ce titre sur Numilog.com

I
RÉVISION DE BASES : CALCUL
DIFFÉRENTIEL, ALGÈBRE LINÉAIRE
ET BILINÉAIRE

Rappels
I.1. Algèbre linéaire et bilinéaire

Si l : Rn → R est linéaire, il existe un unique v ∈ Rn tel que l(x) =

v, x pour
tout x ∈ Rn ; les fonctions affines à valeurs réelles sont de la forme x −→
v, x+c,
où v ∈ Rn et c ∈ R. Même chose si l est une forme linéaire sur un espace euclidien
(E,
·, ·) : l s’écrit de manière unique sous la forme
v, ·, où v ∈ E.
Si q : Rn → R est une forme quadratique, il existe un unique Q ∈ Sn (R) tel
1
que q(x) =
Qx, x pour tout x ∈ Rn (le coefficient 1/2 est mis là pour simplifier
2
les calculs).
Rappel du mécanisme de transposition :
Ax, y =
x, A y (produits scalaires
dans Rm et Rn respectivement).
Si H est un sous-espace vectoriel de Rn , H ⊥ désigne son sous-espace orthogo-
nal. Rappel : si A est linéaire, (KerA)⊥ = Im(A ).
Un résultat-clé de l’Algèbre linéaire et bilinéaire : si S ∈ Sn (R), toutes les
valeurs propres λi de S sont réelles et il existe une matrice orthogonale U telle
que U  SU = diag(λ1 , . . . , λn ) ; ainsi il existe des vecteurs propres xi unitaires (xi
 n
associé à λi ) tels que S = λi xi x
i (ceci est appelé une décomposition spectrale
i=1
de S).
 Retrouver ce titre sur Numilog.com

Chapitre I. Révision de bases : calcul différentiel...

Les formulations variationnelles suivantes de la plus grande et la plus petite

valeurs propres de S ∈ Sn (R) sont essentielles :

Sx, x
Sx, x
λmax (S) = max , λmin (S) = min ·
x = 0  x 2 x = 0  x 2

Sn (R) est muni de l’ordre (partiel) suivant : A  B dans Sn (R) lorsque A − B est
semi-définie positive (A − B ∈ Pn (R)).
◦
Si X ∈ Pn (R), la racine carrée positive de X (notée X 1/2 ) est l’unique S ∈
◦
Pn (R) telle que S 2 = X. L’application X −→ X 1/2 a des propriétés similaires
à celles de la fonction racine carrée sur R+
∗ ; prudence tout de même... Mêmes
remarques pour l’application X −→ X −1 .
Si K est un cône convexe fermé d’un espace euclidien (E,
·, ·), le cône polaire
◦
K de K est le cône convexe fermé de E défini comme suit :

K ◦ := {s ∈ E |
s, x  0 pour tout x ∈ K}.

I.2. Calcul différentiel

f : O ⊂ Rn −→ R définie sur un ouvert O de Rn est dite différentiable en
x ∈ O s’il existe l : Rn −→ R linéaire telle que :

f (x + h) = f (x) + l(h) +  h  ε (h) , avec ε (h) → 0 quand h−→ 0. (1.1)

=

l est représentée (dans (Rn ,

·, ·) euclidien) par un unique vecteur, appelé gradient
de f en x, et noté ∇f (x) (ça se lit « nabla f de x »). Désignant par ∂j f (x) la
dérivée partielle en x de f par rapport à la j e variable, ∇f (x) est le vecteur de
Rn de composantes ∂1 f (x) , ..., ∂n f (x). Une manière équivalente d’exprimer (1.1)
est :
f (x + td) − f (x)
lim =
∇f (x) , d (1.2)
t→0+ t
et la convergence est uniforme par rapport à d lorsque celui-ci reste dans un
ensemble borné de Rn (la sphère-unité par exemple).
⎛ Plus ⎞ généralement, F : O ⊂ Rn −→ Rm qui à x ∈ O associe F (x) =
f1 (x)
⎜ .. ⎟
⎝ . ⎠ est dite différentiable en x ∈ O si chacune des fonctions-composantes
fm (x)
f1 , ..., fm l’est. On appelle alors matrice jacobienne de F en x, et on note JF (x)
la matrice de Mm,n (R) dont les lignes sont [∇f1 (x)] , ..., [∇fm (x)] , c’est-à-dire
que le terme (i, j) de JF (x) est ∂j fi (x) .

2
 Retrouver ce titre sur Numilog.com

I.3. Fonctions convexes

Revenant à une fonction numérique f : O ⊂ Rn −→ R différentiable sur O,

on dit que f est deux fois différentiable en x ∈ O lorsque ∇f : O ⊂ Rn −→ Rn
est différentiable en x. La matrice jacobienne de ∇f en x est appelée matrice
hessienne de f en x et notée ∇2 f (x) ; il s’agit d’une matrice symétrique de taille
2 f (x) (dérivée partielle d’ordre 2 en x
n dont le terme (i, j) est ∂i (∂j f )(x) = ∂ij
de f par rapport à la ie et j e variables).
Rappel : dans le cas où f est deux fois différentiable en x ∈ O, on a le
développement de Taylor-Young d’ordre deux suivant :
1
f (x + h) = f (x) +
∇f (x) , h +
∇2 f (x) h, h +  h 2 ε (h) , (1.3)
2
avec ε (h) → 0 quand h−→ 0.
=
Enfin deux ensembles de résultats de Calcul différentiel sont essentiels en Op-
timisation : le théorème de la fonction implicite et le théorème d’inversion locale ;
les développements de Taylor sous leurs formes diverses. À revoir si nécessaire.

I.3. Fonctions convexes

Soit C un convexe de Rn ; f : C → R est dite convexe sur C si pour tout

(x, x ) ∈ C × C et tout α ∈ ]0, 1[ on a :
 
f αx + (1 − α) x  αf (x) + (1 − α) f (x ). (1.4)

f est dite strictement convexe sur C quand l’inégalité (1.4) est stricte dès que
x = x . Une propriété encore plus forte est comme suit : f est dite fortement
convexe sur C, de module de forte convexité c > 0, lorsque
  1
f αx + (1 − α) x  αf (x) + (1 − α) f (x ) − c α (1 − α)  x − x 2 (1.5)
2
pour tout (x, x ) ∈ C × C et tout α ∈ ]0, 1[ .
Rappelons deux résultats essentiels :

Théorème. Soit f différentiable sur un ouvert O de Rn et C un convexe de O.

Alors :

(i) f est convexe sur C si et seulement si

f (x)  f (x) +
∇f (x) , x − x pour tout (x, x) ∈ C × C ; (1.6)

3
 Retrouver ce titre sur Numilog.com

Chapitre I. Révision de bases : calcul différentiel...

(ii) f est strictement convexe sur C si et seulement si l’inégalité (1.6) est stricte
dès que x = x ;

(iii) f est fortement convexe sur C de module c si et seulement si

1
f (x)  f (x) +
∇f (x) , x − x + c  x − x 2 , pour tout (x, x) ∈ C × C. (1.7)
2
Théorème. Soit f deux fois différentiable sur un ouvert convexe O. Alors :
(i) f est convexe sur O si et seulement si ∇2 f (x) est semi-définie positive
pour tout x ∈ O ;
(ii) Si ∇2 f (x) est définie positive pour tout x ∈ O, alors f est strictement
convexe sur O ;
(iii) f est fortement convexe sur O de module c si et seulement si la plus
petite valeur propre de ∇2 f (x) est minorée sur O par c , soit encore :

∇2 f (x) d, d  c  d 2 pour tout x ∈ O et tout d ∈ Rn .

Références. Parmi les exercices de [15] figurent des applications simples à l’Ana-
lyse numérique matricielle et l’Optimisation. Outre les références suggérées en
pp. 305 307 de [15] (et rééditées à présent), signalons [16], ouvrage complet et très
diffusé, dans lequel l’aspect matriciel (celui qui prévaut dans les applications) est
privilégié.
Pour les fonctions convexes différentiables, on pourra consulter [12], Cha-
pitre IV, Section 4, par exemple.

* Exercice I.1. Soit f : Rn −→ R continûment différentiable.

1◦ ) Soit x0 tel que ∇f (x0 ) = 0. Que représente ∇f (x0 ) pour la surface de
niveau S := {x ∈ Rn | f (x) = f (x0 )} ?
2◦ ) Rappeler l’équation de l’hyperplan affine (de Rn+1 ) tangent au graphe
de f en (x0 , f (x0 )) .
Donner à l’aide de ∇f (x0 ) un vecteur normal à cet hyperplan.
3◦ ) On suppose qu’il existe L > 0 tel que
   
 ∇f (x) − ∇f x   L  x − x  pour tout x, x ∈ Rn × Rn .

Montrer qu’alors
L
|f (x + d) − f (x) −
∇f (x), d|   d 2 pour tout (x, d) ∈ Rn × Rn .
2

4
 Retrouver ce titre sur Numilog.com

I.3. Fonctions convexes

Solution : 1◦ ) ∇f (x0 ) est un vecteur normal à S en x0 ; le sous-espace tangent

à S en x0 est orthogonal à ∇f (x0 ).
2◦ ) Soit grf := {(x, f (x)) | x ∈ Rn } le graphe de f (partie de Rn+1 donc).
Le sous-espace affine tangent à grf en (x0 , f (x0 )) a pour équation

y = f (x0 ) +
∇f (x0 ), x − x0 .

Un vecteur normal à cet hyperplan est fourni par (∇f (x0 ), −1) ∈ Rn × R.
On peut voir aussi grf comme la surface de niveau 0 de la fonction

g : (x, r) ∈ Rn × R −→ g(x, r) := f (x) − r.

Comme ∇g (x0 , f (x0 )) = (∇f (x0 ), −1) n’est jamais nul, le vecteur
(∇f (x0 ), −1) est normal à grf en (x0 , f (x0 )) .

Figure 1.

3◦ ) f étant continûment différentiable, on a grâce à la formule de Taylor à

l’ordre zéro avec reste sous forme d’intégrale
 1
f (x + d) = f (x) +
∇f (x + td), ddt.
0
 1
Sachant que
∇f (x), d =
∇f (x), ddt, on transforme l’expression pré-
0
cédente en
 1
f (x + d) − f (x) −
∇f (x), d =
∇f (x + td) − ∇f (x), ddt.
0

5
 Retrouver ce titre sur Numilog.com

Chapitre I. Révision de bases : calcul différentiel...

Il s’ensuit grâce à l’hypothèse faite sur ∇f :

|
∇f (x + td) − ∇f (x), d|   ∇f (x + td) − ∇f (x)  ·  d 
 tL  d 2 ,
d’où :
 1
L
|f (x + d) − f (x) −
∇f (x), d|  (tL  d 2 )dt =  d 2 .
0 2

Commentaire :
– Prolongement de l’exercice. On suppose à présent que f est deux fois diffé-
rentiable sur Rn . Comment traduire alors en termes de ∇2 f l’hypothèse dans la
3e question ? Proposer ensuite une démonstration de l’inégalité de la 3e question
qui s’appuie sur une autre formule de Taylor.
– Il importe de bien assimiler ce que représentent géométriquement les objets
∇f (x) et ∇2 f (x) vis-à-vis des surfaces de niveau et du graphe de f .
* Exercice I.2.
Situations : À déterminer :
1◦ ) f : Rn −→ R ∇f (x), ∇2 f (x) en tout point x.
x −→ f (x) :=
c, x + γ.
2◦ ) F : Rn −→ Rm JF (x).
x −→ F (x) := Lx + b, où L ∈ Mm,n (R).
3◦ ) f : Rn −→ R ∇f (x), ∇2 f (x).
x −→ f (x) := 12
Ax, x +
d, x + δ,
où A ∈ Mn (R).
4◦ ) g : Rn −→ R ∇g(x), ∇2 g(x).

m
x −→ g(x) := [ri (x)]2 ,
i=1
où les ri : Rn −→ R sont deux
fois différentiables.

Commentaire : Ne pas se lancer tête baissée dans le calcul de dérivées partielles !

Pour les fonctions de base que sont les fonctions affines, quadratiques, sommes
de carrés, etc., il faut savoir déterminer ∇f (x), ∇2 f (x) rapidement et sans erreur,
« mécaniquement » presque.

6
 Retrouver ce titre sur Numilog.com

I.3. Fonctions convexes

Solution :
1◦ ) ∇f (x) = c, ∇2 f (x) = 0 pour tout x ∈ Rn .
2◦ ) JF (x) = L (L est la partie linéaire de la fonction affine F ).
 
3◦ ) ∇f (x) = 12 A + A x + d, ∇f (x) = Ax + d si A est symétrique.
 
∇2 f (x) = 12 A + A , ∇2 f (x) = A si A est symétrique.
m
4◦ ) ∇g(x) = 2 ri (x)∇ri (x),
i=1
m  
∇2 g(x) = 2 ∇ri (x) [∇ri (x)] + ri (x)∇2 ri (x) .
i=1
Ainsi, si (r1 (x), ..., rm (x)) est « proche de 0 dans Rm », on peut considé-
m
rer que 2 ∇ri (x) [∇ri (x)] est une « bonne » approximation de ∇2 g(x) ;
i=1
approximation qui, de plus, ne fait appel qu’aux gradients des fonctions ri .

* Exercice I.3.
Situations : Questions :

1◦ ) g : Rn −→ R

m
 2 , g est-elle différentiable deux fois
x −→ g(x) := fi+ (x)
différentiable ?
i=1
où les fi : Rn −→ R sont deux
fois différentiables et a+ désigne max
(0, a).
2◦ )
A
Rn Rm

f
g := f ◦ A

où A : u −→ Au = A0 u + b, avec Déterminer ∇g, ∇2 g en fonction des

A0 ∈ Mm,n (R), et f deux fois diffé- éléments correspondants ∇f et ∇2 f .
rentiable.
Application : Soit : Rn −→ R deux Calculer ϕ (t) (resp. ϕ (t)) en fonc-
fois différentiable, x0 ∈ Rn , d ∈ Rn . tion de ∇f (x0 + td) (resp. ∇2 f (x0 +
On pose ϕ (t) := f (x0 + td). td)).

7
 Retrouver ce titre sur Numilog.com

Optimisation et analyse convexe

J. JENSEN (1859–1925). Mathématicien danois, autodidacte. Il n’occupa aucune po-

sition universitaire mais fut longtemps expert dans une compagnie téléphonique de Co-
penhague. L’inégalité de convexité qui porte son nom (cf. Chapitre VI) date de 1906.
La tradition de convexité chez les mathématiciens scandinaves est commémorée par la
flamme de la poste danoise ci-dessous.

F. JOHN (1910–1994) (on trouve souvent écrit Fritz John) est aussi un mathématicien
de ce siècle qui a établi les conditions qui portent son nom (cf. Chapitre III) en 1948.
Le travail de F. John était motivé par des questions de nature géométrique ; les ellip-
soïdes pleins de volume extrémal mis en évidence dans les Exercices III.21 et III.22 sont
d’ailleurs appelés ellipsoïdes de John (ou de Loewner-John). On doit aussi au mathéma-
ticien d’origine tchèque Ch. Loewner (ou K. Löwner) l’ordre partiel  dans Sn (R).
H. MINKOWSKI (1864–1909). Mathématicien allemand considéré comme le fondateur
de la géométrie des nombres entiers ; il s’est intéressé aussi à la Physique mathématique
(les fameux espaces de Minkowski de dimension 4) et a, le premier, procédé à une étude
systématique de la convexité dans les espaces de dimension finie.
J. (VON) NEUMANN (1903–1957). Il y a plusieurs mathématiciens du nom de
Neumann. Celui-ci, Von Neumann (John) est un mathématicien américain d’origine hon-
groise, mort relativement jeune, et qui fut pionnier dans ses idées et recherches en Ma-
thématiques appliquées. Et quand il attaquait un problème, il n’enfonçait pas des portes
ouvertes ! On lui doit notamment un théorème de mini-maximisation (cf. Chapitre IV).

330
 INDEX

B formulation en programmes linéaires : V.18, V.20

fractionnaire (problème d’optimisation) : V.20,
(fonction-) barrière : II.6, III.21, IV.12, V.25
VI.27
bases, éléments de base : V.1, V.2
BFGS : III.23
G
Birkhoff : V.11
Gibbs (problème d’optimisation) : IV.7
C Gordan (lemme de) : VI.8, VII.1
chemin central : IV.12, V.25
cône convexe polyédrique : V.8, V.9, V.10, V.12 H
conjuguées de fonctions : VII.2, VII.3, VII.4,
VII.6, VII.7, VII.8, VII.9, VII.12, Hamilton-Jacobi (équations) : VII.28
VII.19, VII.20
convexification d’ensembles : VI.10, VI.11, I
VI.12, VI.13, VI.14
convexification de fonctions : VII.22, VII.23, inversion de matrices aléatoires : VI.29
VII.24, VII.25, VII.26 inversion de matrices perturbées : I.8

D K
décomposition de Moreau : VI.22
Kantorovitch (inégalité) : I.9
dérivée directionnelle : III.12, III.30, VI.21
DFP : III.23
L
différence de fonctions convexes : VII.27
(problème) dual en minimisation convexe : IV.4,
lagrangien augmenté : I.18(B), IV.13
IV.5, IV.6, IV.7, IV.8, IV.9, IV.10,
logarithme du déterminant : I.13, I.14
IV.11
logarithmiquement convexe (fonction) : I.15
dual augmenté : IV.13
(problème) dual en programmation linéaire :
M
V.21, V.22, V.23, V.24, V.25
matrices définies positives : I.10, I.11, I.12
E
minimum local vs. minimum global : II.5
Ekeland : II.3 moindres carrés : I.2 (4◦ ), II.11
ellipsoïde : III.8 Moreau-Yosida : VII.15, VII.17
ellipsoïde de volume maximal : III.21, III.22
Everett (lemme de) : III.15 N

F
Newton (direction de) : III.9
face : VI.14 normal (cône) : VI.23