Optimisation et analyse convexe

De
Publié par

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 1ère 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).
Publié le : lundi 3 décembre 2012
Lecture(s) : 75
Licence : Tous droits réservés
EAN13 : 9782759807000
Nombre de pages : 344
Voir plus Voir moins
Cette publication est uniquement disponible à l'achat
C O L L E C T I O N E N S E I G N E M E N T S U P / / / / M a t h é m a t i q u e s
L3M1 Optimisation et analyse convexe
EXERCICES CORRIGÉS
Jean-Baptiste Hiriart-Urruty
Extrait de la publication
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
Extrait de la publication
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.
c2009, EDP Sciences, 17, avenue du Hoggar, BP 112, Parc d’activités de Courtabœuf, 91944 Les Ulis Cedex A
Extrait de la publication
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.1Algèbre linéaire et bilinéaire . . . . . . . . . . . . . . . . . . . I.2Calcul différentiel . . . . . . . . . . . . . . . . . . . . . . . . . I.3Fonctions 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.1. . . . . . . . . . .Conditions de minimalité du premier ordre III.2Cône tangent, cône normal à un ensemble . . . . . . . . . . . . III.3. . . . . . . . . . . . . . . . .Prise en compte de la convexité III.4Conditions 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) ; problèmes de mini-maximisation . . . . 127 IV.2. . . . . . . . . . . . . . . . . . . . 128Points-selles de lagrangiens IV.3. . . . . . . . . . . . 129Premiers pas dans la théorie de la dualité
Extrait de la publication
Optimisation et analyse convexe
iv
V
VI
VII
Polyèdres convexes fermés. Optimisation à données affines (Programmation linéaire)165 V.1. . . . . . . . . . . . . . . . . . . . 165Polyèdres convexes fermés 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.3. . . . . . . . . . 219Hyperplan d’appui, fonction d’appui 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.1Définitions . . . . . . . . . . . . . . . . . . . . . . . . 273 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 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
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 di-mension 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, à com-mencer 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 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é.
Extrait de la publication
Toulouse, printemps 2009 J.-B. Hiriart-Urruty
vii
Extrait de la publication
:= cf. i.e. ln
ABRÉVIATIONS ET NOTATIONS
: égal par définition. :confer, signifie « se reporter à ». :id est, signifie « c’est-à-dire ». : notation normalisée pour le logarithme népérien.
+R,Rou]0,+[ :ensemble des réels strictement positifs. + + u:partie positive du réelu. x= (x1, . . . , xn)oux= (ξ1, . . . , ξn) :notation générique pour un vecteur n deR. + + +n usign. . . , u) ifie(u1,nlorsqueu= (u1, . . . , un)R. n Lorqueuetvsont deux vecteurs deR, uvsignifie «uivipour tout i= 1, . . . , n». {uk}ou(uk) :notations utilisées pour les suites indexées par des entiers naturels. Pour une fonctionfdifférentiable enx(resp. deux fois différentiable enx), 2 Df(x)désigne la différentielle (première) defenx(resp.D f(x)désigne la différentielle seconde defenx).Si la variable est réelle (et notéet), on utilise la   notationf(t)(resp.f(t)) pour la dérivée defent(resp. la dérivée seconde def ent) [ce sont des éléments de l’espace d’arrivée et non des applications linéaires]. n Pour une fonction numériquefdéfinie sur un ouvertOdeR,différentiable 2 enx∈ O(resp. deux fois différentiable enx∈ O),f(x)(resp.f(x)) désigne le (vecteur)gradientdefenx(resp. la matricehessiennedefenx). Lorsqu’elle existe, la dérivée directionnelle defenxdans la directiondest notéef(x, d). n m Pour une fonction vectoriellef:O ⊂RRdifférentiable enx∈ O,J f(x) désigne la matricejacobiennedefenx(matrice àmlignes etncolonnes).
Extrait de la publication
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.