| Titre : | Introduction à l'optimisation |
| Auteurs : | Jean-Christophe Culioli, Auteur |
| Type de document : | Monographie imprimée |
| Mention d'édition : | 2e éd. |
| Editeur : | Paris [France] : Ellipses, impr. 2012 |
| Collection : | Références sciences, ISSN 2260-8044 |
| ISBN/ISSN/EAN : | 978-2-7298-7624-1 |
| Format : | 1 vol. (380 p.) / ill., couv. ill. en coul. / 24 cm |
| Note générale : | Bibliogr. p. 367-373. Index |
| Langues: | Français |
| Index. décimale : | 519.607 6 |
| Catégories : |
[Agneaux] Optimisation mathématique > Problèmes et exercices |
| Résumé : |
Ce livre d’introduction à l’Optimisation a servi de support écrit pour de nombreux enseignements à Mines ParisTech, à l’université Paris Dauphine, à l’École Centrale Paris et d’autres cours spécialisés. Il est couramment utilisé dans des masters universitaires et certains centres de recherche industriels. La théorie de l’Optimisation est un cadre mathématique permettant d’interpréter et de résoudre dans les mêmes termes un grand nombre de problèmes de commande optimale, d’identification, d’analyse numérique, de statistiques, de mécanique et d’économie. Cet ouvrage s’adresse à tous ceux qui désirent acquérir des bases unificatrices leur permettant de modéliser, d’étudier et de commander des systèmes complexes. Plus de 150 exercices (dont la moitié sont corrigés) devraient permettre la mémorisation des concepts fondamentaux.
Un prologue pose les bases numériques minimales. On aborde ensuite l’Optimisation statique non-linéaire et linéaire. Le calcul des variations ouvre le bal des méthodes dynamiques, puisque c’est l’ancêtre commun du principe du maximum de Pontryaguine et de la programmation dynamique de R. Bellman, longuement traités eux aussi. Suivent enfin des considérations utiles au traitement de grands systèmes. |
| Sommaire : |
Prologue 11
1.1 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 Optimisation unidimensionnelle . . . . . . . . . . . . . . . . . . 13 1.2.1 M´ethode de dichotomie . . . . . . . . . . . . . . . . . . 14 1.2.2 M´ethode de la section dor´ee . . . . . . . . . . . . . . . . 18 1.3 R´esolution d’´equations en dimension 1 . . . . . . . . . . . . . . 20 1.3.1 M´ethode de Newton Raphson . . . . . . . . . . . . . . . 21 1.3.2 M´ethode de la s´ecante . . . . . . . . . . . . . . . . . . . 27 1.4 Rappels d’analyse matricielle . . . . . . . . . . . . . . . . . . . 29 1.4.1 D´efinitions et r´esultats classiques . . . . . . . . . . . . . 29 1.4.2 Quelques consid´erations num´eriques . . . . . . . . . . . 32 1.4.3 R´esolution de syst`emes lin´eaires . . . . . . . . . . . . . 35 2 M´ethodes de descente 45 2.1 Minimum et descente . . . . . . . . . . . . . . . . . . . . . . . . 45 2.2 Conditions d’optimalit´e . . . . . . . . . . . . . . . . . . . . . . 46 2.2.1 Cas diff´erentiable . . . . . . . . . . . . . . . . . . . . . . 46 2.2.2 Cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2.3 Application : la transformation de Legendre-Fenchel . . 57 2.3 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.3.1 M´ethode du gradient . . . . . . . . . . . . . . . . . . . . 61 2.3.2 Algorithme de gradient `a pas fixe (ou `a pas constant). . 67 2.3.3 M´ethode de relaxation . . . . . . . . . . . . . . . . . . . 71 2.3.4 M´ethode de Newton . . . . . . . . . . . . . . . . . . . . 74 2.3.5 M´ethodes de gradient conjugu´e . . . . . . . . . . . . . . 77 2.3.6 M´ethodes de Quasi-Newton . . . . . . . . . . . . . . . . 81 2.4 Retour sur la recherche lin´eaire . . . . . . . . . . . . . . . . . . 89 2.5 Optimisation non-diff´erentiable . . . . . . . . . . . . . . . . . . 93 2.5.1 Inapplicabilit´e des algorithmes classiques . . . . . . . . 93 2.5.2 Existence du sous-diff´erentiel pour les fonctions convexes 97 7 8 TABLE DES MATI `ERES 2.6 Algorithmes de sous-gradient . . . . . . . . . . . . . . . . . . . 101 2.6.1 M´ethode de faisceaux . . . . . . . . . . . . . . . . . . . 106 3 Optimisation sous contraintes 109 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 3.2 Approche non-lin´eaire . . . . . . . . . . . . . . . . . . . . . . . 110 3.2.1 Th´eor`eme des fonctions implicites . . . . . . . . . . . . 110 3.2.2 Contraintes ´egalit´e : multiplicateurs de Lagrange . . . . 111 3.2.3 Interpr´etation des multiplicateurs de Lagrange. . . . . . 118 3.2.4 Contraintes in´egalit´e : multiplicateurs de Karush, Kuhn et Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . 121 3.2.5 Conditions d’optimalit´e du second ordre . . . . . . . . . 127 3.3 Approche minimax . . . . . . . . . . . . . . . . . . . . . . . . . 128 3.3.1 Un petit jeu `a somme nulle . . . . . . . . . . . . . . . . 128 3.3.2 Th´eor`eme de point-selle . . . . . . . . . . . . . . . . . . 130 3.3.3 Application `a la minimisation sous contraintes . . . . . 132 3.3.4 Cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . 134 3.3.5 Existence d’un point-selle . . . . . . . . . . . . . . . . . 136 3.4 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 3.4.1 M´ethodes admissibles . . . . . . . . . . . . . . . . . . . 138 3.4.2 P´enalisation ext´erieure et int´erieure. . . . . . . . . . . . 143 3.4.3 Forme g´en´eralis´ee du th´eor`eme de Karush, Kuhn et Tucker (Fritz John) . . . . . . . . . . . . . . . . . . . . . . 148 3.4.4 M´ethodes de Lagrangien (m´ethodes dites duales) . . . . 152 3.4.5 M´ethode “prox” et Lagrangien augment´e . . . . . . . . . 161 3.4.6 Interpr´etation g´eom´etrique des algorithmes d’Uzawa avec Lagrangien et Lagrangien augment´e . . . . . . . . . . . 170 3.4.7 Minimisation d’une fonction de m´erite . . . . . . . . . . 175 4 Programmation Lin´eaire 181 4.1 Mod`ele et exemples . . . . . . . . . . . . . . . . . . . . . . . . . 181 4.2 Un essai de r´esolution `a la main . . . . . . . . . . . . . . . . . . 183 4.3 Le th´eor`eme fondamental . . . . . . . . . . . . . . . . . . . . . 186 4.4 Le Simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 4.4.1 L’algorithme classique du Simplexe . . . . . . . . . . . . 192 4.4.2 Non-d´eg´en´erescence et cyclage . . . . . . . . . . . . . . 193 4.4.3 Initialisation (phase I) . . . . . . . . . . . . . . . . . . . 194 4.4.4 Algorithme du Simplexe sous forme r´evis´ee (phase II) . 194 4.5 Existence et dualit´e . . . . . . . . . . . . . . . . . . . . . . . . 196 4.5.1 D´efinitions et lemme de Farkas . . . . . . . . . . . . . . 196 4.5.2 Existence . . . . . . . . . . . . . . . . . . . . . . . . . . 200 TABLE DES MATI`ERES 9 4.5.3 Probl`eme dual et th´eor`eme de dualit´e . . . . . . . . . . 201 4.6 Approches non lin´eaires : leurs qualit´es . . . . . . . . . . . . . . 204 4.7 Algorithme de Karmarkar . . . . . . . . . . . . . . . . . . . . . 205 4.8 Algorithme primal-dual int´erieur . . . . . . . . . . . . . . . . . 212 4.9 Algorithme affine . . . . . . . . . . . . . . . . . . . . . . . . . . 217 4.10 Remarques sur la phase I : admissibilit´e . . . . . . . . . . . . . 221 4.11 Complexit´e et convergence polynˆomiale . . . . . . . . . . . . . 223 5 Calcul des variations 231 5.1 Probl`eme ´el´ementaire du Calcul des variations . . . . . . . . . 233 5.1.1 Espaces de courbes, crit`eres etminima . . . . . . . . . . 233 5.1.2 Les contraintes . . . . . . . . . . . . . . . . . . . . . . . 236 5.1.3 Principe du Calcul des variations . . . . . . . . . . . . . 237 5.2 Conditions n´ecessaires d’Euler (premier ordre) . . . . . . . . . 240 5.2.1 ´Equation d’Euler ´el´ementaire . . . . . . . . . . . . . . . 240 5.2.2 ´Equation d’Euler vectorielle . . . . . . . . . . . . . . . . 243 5.2.3 D´etermination d’int´egrales premi`eres . . . . . . . . . . . 243 5.3 Applications de l’´equation d’Euler . . . . . . . . . . . . . . . . 245 5.3.1 Principe de Hamilton . . . . . . . . . . . . . . . . . . . 245 5.3.2 Calcul de g´eod´esiques . . . . . . . . . . . . . . . . . . . 248 5.4 Conditions de transversalit´e . . . . . . . . . . . . . . . . . . . . 249 5.4.1 Extr´emit´e assujettie `a se d´eplacer sur une courbe . . . . 249 5.4.2 Extr´emit´e libre soumise `a un coˆut. Condition limite naturelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 5.5 Probl`emes isop´erim´etriques . . . . . . . . . . . . . . . . . . . . 254 5.6 Autres conditions d’optimalit´e . . . . . . . . . . . . . . . . . . 257 5.6.1 Condition suffisante du premier ordre : cas convexe . . 257 5.6.2 Condition n´ecessaire du second ordre (Legendre) . . . . 257 5.6.3 Probl`eme secondaire et condition suffisante de Jacobi . 259 5.6.4 Variation forte : condition de Weierstrass . . . . . . . . 262 5.6.5 Transformation de Legendre et ´equations canoniques . . 264 6 Principe du Maximum de Pontryaguine 267 6.1 Le probl`eme de la Commande optimale . . . . . . . . . . . . . 267 6.1.1 ´Etat et commande . . . . . . . . . . . . . . . . . . . . . 267 6.1.2 Stabilit´e, commandabilit´e, observabilit´e, d´etectabilit´e . . 271 6.2 Principe du Maximum de Pontryaguine . . . . . . . . . . . . . 277 6.2.1 Typologie des probl`emes de commande optimale . . . . 277 6.2.2 Origine du Principe du Maximum . . . . . . . . . . . . 278 6.2.3 Un ´enonc´e assez g´en´eral . . . . . . . . . . . . . . . . . . 280 6.2.4 D´emonstration du Principe du Maximum . . . . . . . . 282 10 TABLE DES MATI `ERES 6.2.5 Une preuve rigoureuse dans un cadre simplifi´e . . . . . . 285 6.3 Contraintes int´egrales, instantan´ees, d’´etat . . . . . . . . . . . . 287 6.4 Applications avec r´esolution num´erique . . . . . . . . . . . . . . 290 6.4.1 Commande en temps minimal . . . . . . . . . . . . . . . 290 6.4.2 Probl`emes lin´eaires-quadratiques g´en´eraux . . . . . . . . 291 7 Programmation Dynamique 295 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 7.2 Principe d’optimalit´e en temps discret . . . . . . . . . . . . . . 296 7.3 ´Equation de Hamilton-Jacobi-Bellman discr`ete . . . . . . . . . 300 7.3.1 Probl`eme de plus Court Chemin . . . . . . . . . . . . . 300 7.3.2 Probl`eme de Commande Optimale en temps discret . . 302 7.3.3 Probl`eme Lin´eaire Quadratique . . . . . . . . . . . . . . 307 7.4 ´Equation de Hamilton-Jacobi-Bellman continue . . . . . . . . . 311 7.4.1 Probl`eme Lin´eaire Quadratique . . . . . . . . . . . . . . 313 7.4.2 D´emonstration heuristique du Principe du Maximum . . 314 7.5 Complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 8 Probl`emes de grande taille 319 8.1 M´ethodes classiques de d´ecomposition . . . . . . . . . . . . . . 320 8.1.1 D´ecomposition par les prix . . . . . . . . . . . . . . . . 321 8.1.2 D´ecomposition par les quantit´es . . . . . . . . . . . . . 322 8.2 Principe du Probl`eme Auxiliaire . . . . . . . . . . . . . . . . . 325 8.3 M´ethodes de coupes et de faisceaux . . . . . . . . . . . . . . . . 329 8.3.1 M´ethode de coupe ou des plans s´ecants . . . . . . . . . 329 8.3.2 Les m´ethodes de faisceaux . . . . . . . . . . . . . . . . . 332 9 Solutions des exercices 337 |
Disponibilité (2)
| Cote | Support | Localisation | Statut | Emplacement | |
|---|---|---|---|---|---|
| S8/1721 | Livre | BIB.FAC.ST. | Empruntable | Magazin | |
| S8/1721 | Livre | BIB.FAC.ST. | Empruntable | Magazin |
Erreur sur le template
