Optimisation et analyse convexe

Jean-Baptiste Hiriart-Urruty

Description

L'auteur a fait sienne cette universelle maxime chinoise : « j'entends et j'oublie (cours oral) je vois et je retiens (étude du cours) je fais et je comprends » (exercices)…

Ainsi, ce livre est un recueil d'exercices et problèmes corrigés, de difficulté graduée, accompagnés de commentaires sur l'utilisation du résultat obtenu, sur un prolongement possible et, occasionnellement, placés dans un contexte historique. Chaque chapitre débute par des rappels de définitions et résultats du Cours. Le cadre de travail est volontairement simple, l'auteur a voulu insister sur les idées et mécanismes de base davantage que sur des généralisations possibles ou des techniques particulières à telle ou telle situation.

Les connaissances mathématiques requises pour tirer profit du recueil ont été maintenues minimales, celles normalement acquises à Bac+3 (ou Bac+2 suivant les cas). L'approche retenue pour avancer est celle d'une progression en spirale plutôt que linéaire au sens strict.

Pour ce qui est de l'enseignement, les aspects de l'optimisation et analyse convexe traités dans cet ouvrage trouvent leur place dans les formations de niveau M1, parfois L3, (modules généralistes ou professionnalisés) et dans la formation mathématique des ingénieurs (en 2e année d'école, parfois en 1re année). La connaissance de ces aspects est un préalable à des formations plus en aval, en optimisation numérique par exemple.

Détails: après un chapitre de révisions de base (analyse linéaire et bilinéaire, calcul différentiel), l'ouvrage aborde l'optimisation par les conditions d'optimalité (chap. 2 et 3), le rôle incontournable de la dualisation des problèmes (chap. 4) et le monde particulier de l'optimisation linéaire (chap.5). L'analyse convexe est traitée par l'initiation à la manipulation des concepts suivants : projection sur un convexe fermé (chap.6), le calcul sous différentiel et de transformées de Legendre-Fenchel (chap.7).

Sujets

• Sciences & Techniques
• Mathématiques
• Sciences formelles
• Mathématiques générales
• Mathématiques générales
• Mathématiques fondamentales
• Mathématiques pures
• Mathematics
• Sciences et techniques

Informations

• Publié par: EDP Sciences
• Date de parution: 01 mars 2009
• Nombre de lectures: 5
• EAN13: 9782759807000
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

COLLECTION ENSEIGNEMENT SUP //// Mathématiques

L3M1
Optimisation
et analyse convexe

EXERCICES CORRIGÉS

Jean-Baptiste Hiriart-Urruty

OPTIMISATION
ET
ANALYSE CONVEXE

Exercices
avec

et problèmes corrigés,
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

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. : [phone].

c2009, EDP Sciences, 17, avenue du Hoggar, BP 112, Parc d’activités de Courtabœuf,
91944 Les Ulis Cedex A

Introduction

Abréviations et notations

I

II

III

IV

TABLE DES MATIÈRES

Révision de bases : calcul différentiel, algèbre linéaire
et bilinéaire
I.1. . . . . . . . . . . . . . . . . . .Algèbre linéaire et bilinéaire
I.2. . . . . . . . . . . . . . . . . . . . . . . . .Calcul différentiel
I.3. . . . . . . . . . . . . . . . . . . . . . . .Fonctions convexes

Minimisation sans contraintes. Conditions de minimalité
II.1Conditions de minimalité du premier ordre. . . . . . . . . . .
II.2Conditions de minimalité du second ordre .. . . . . . . . . . .

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

v

ix

1
1
2
3

41
41
42

63
63
65
66
66

Mini-maximisation. Dualisation de problèmes
de minimisation convexe127
IV.1Points-selles (ou cols). . . . 127; problèmes de mini-maximisation
IV.2Points-selles de lagrangiens. . . . . . . . . . . . . . . . . . . . 128
IV.3Premiers pas dans la théorie de la dualité. . . . . . . . . . . . 129

Optimisation et analyse convexe

iv

V

VI

VII

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

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

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

Sources

Références générales

Notice historique

Index

323

325

327

331

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
etAnalyse 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
particulier (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
initiation à 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
revision 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
profitables au lecteur-étudiant que si celui-ci les travaille, un crayon à la main, sans

Optimisation et analyse convexe

vi

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)
Lecadre de travailchoisi est volontairement simple (celui des espaces de
dimension finie), et nous avons voulu insister sur lesidéesetmécanismes de base
davantage que sur les généralisations possibles ou les techniques particulières à tel
ou tel contexte. Les problèmes ditsvariationnelsrequièrent dans leur traitement
une intervention plus grande de la Topologie et de l’Analyse fonctionnelle, à
commencer par le cadre – fondamental – des espaces de Hilbert; ils seront abordés
dans un prochain recueil.
Lesconnaissances mathématiquespour tirer profit des exercices et problèmes
du recueil présent sont maintenues minimales, celles normalement acquises après
une formation scientifique àBac + 2ouBac + 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 fonctionA∈ 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

Introduction

Depuis sa publication il y a dix ans (en mars 1998), cet ouvrage a subi les
vicissitudes 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 po