Optimisation et analyse convexe

COLLECTION ENSEIGNEMENT SUP //// Mathématiques
Optimisation
et analyse convexe
Jean-Baptiste Hiriart-Urruty
OPTIMISATION
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
91944 Les Ulis Cedex A, France
ombre ; reproduit avec la gracieuse permission de Christof Weber (université de
Zurich).
Imprimé en France
ISBN : 978-2-7598-0373-6
pays. Toute reproduction ou représentation intégrale ou partielle, par quelque procédé que ce soit, des
122-4, L. 122-5 et L. 335-2 du Code de la propriété intellectuelle). Des photocopies payantes peuvent
3, rue Hautefeuille, 75006 Paris. Tél. : 01 43 26 95 35.
91944 Les Ulis Cedex A
Introduction
Abréviations et notations
et bilinéaire
Algèbre linéaire et bilinéaire . . . . . . . . . . . . . . . . . . .
Fonctions convexes
. . . . . . . . . . . . . . . . . . . . . . . .
Minimisation sans contraintes. Conditions de minimalité
Conditions de minimalité du premier ordre . . . . . . . . . . .
Conditions de minimalité du second ordre . . . . . . . . . . . .
Minimisation avec contraintes. Conditions de minimalité
Conditions de minimalité du premier ordre . . . . . . . . . . .
Cône tangent, cône normal à un ensemble . . . . . . . . . . . .
Prise en compte de la convexité . . . . . . . . . . . . . . . . .
Conditions de minimalité du second ordre . . . . . . . . . . . .
Mini-maximisation. Dualisation de problèmes
de minimisation convexe
Points-selles (ou cols) ; problèmes de mini-maximisation . . . . 127
Points-selles de lagrangiens . . . . . . . . . . . . . . . . . . . . 128
Premiers pas dans la théorie de la dualité . . . . . . . . . . . . 129
Optimisation et analyse convexe
(Programmation linéaire)
Polyèdres convexes fermés
. . . . . . . . . . . . . . . . . . . . 165
La dualité en programmation linéaire . . . . . . . . . . . . . . 171
Formulations de problèmes duaux . . . . . . . . . . . . 171
Relations entre les valeurs optimales et les solutions
de programmes linéaires en dualité . . . . . . . . . . . 172
Caractérisation simultanée des solutions du problème
primal et du problème dual . . . . . . . . . . . . . . . 173
Ensembles et fonctions convexes. Projection sur un convexe
Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . 217
VI.1.1 Ensembles convexes associés à un convexe donné . . . 217
VI.1.2 Enveloppe convexe, enveloppe convexe fermée . . . . . 218
Projection sur un convexe fermé . . . . . . . . . . . . . . . . . 220
Fonctions convexes
. . . . . . . . . . . . . . . . . . . . . . . . 220
de Legendre-Fenchel
La transformation de Legendre-Fenchel . . . . . . . . . . . . . 271
. . . . . . . . . . . . . . . . . . . . . . . . 271
VII.1.2 Quelques propriétés et règles de calcul . . . . . . . . . 272
. . . . . . . . . . . . . . . . . . . . . . . . 273
VII.2.2 Quelques propriétés et règles de calcul . . . . . . . . . 274
Sources
Références générales
Notice historique
INTRODUCTION
« Good modern science implies good variational problems »
M.S. Berger (1983)
(incontournable) de la dualisation de problèmes (chapitre IV) ; le monde particu-
tion à la manipulation de concepts et de résultats concernant essentiellement : la
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
les plus nombreux ;
requiert.
Comme tous les exercices de mathématiques, ceux présentés ici ne seront pro-
Optimisation et analyse convexe
chinois :
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-
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
dans un prochain recueil.
du recueil présent sont maintenues minimales, celles normalement acquises après
Chaque chapitre débute par des rappels de résultats essentiels, ce qui ne doit
puis plus tard en raison de son rôle comme fonction-barrière dans des problèmes
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 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
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,
J.-B. Hiriart-Urruty
Introduction
Depuis sa publication il y a dix ans (en mars 1998), cet ouvrage a subi les vicis-
en nette diminution. Il a été traduit en russe par des collègues de Kiev (Ukraine)
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
accueilli ce projet. Aude Rondepierre a donné un coup de main pour reprendre
Toulouse, printemps 2009
J.-B. Hiriart-Urruty