最优化理论和算法(法文版)

1 Introduction de l'optimisation 1 1.1 Brève histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 1.2 Définition du problème d'optimisation . . . . . . . . . . . . . . . . .3 1.3 Classes des problèmes d'optimisation . . . . . . . . . . . . . . . . . .4 1.4 Rappels mathématiques pour l'optimisation . . . . . . . . . . . . . .5 1.4.1 Normes vectorielles et matricielles . . . . . . . . . . . . . . .5 1.4.2 Suite numérique dans Rn. . . . . . . . . . . . . . . . . . . . 12 1.4.3 Topologie dans Rn. . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.4 Fonctions de plusieurs variables et calcul différentiel . . . . . 17 2 Analyse convexe 25 2.1 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.1 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.2 Combinaison linéaire, convexe, affffine et positive . . . . . . . . 30 2.1.3 Théorème de Carathéodory . . . . . . . . . . . . . . . . . . . 36 2.1.4 Projection et Séparation . . . . . . . . . . . . . . . . . . . . . 38 2.1.5 Point extrémal et Direction extrémale . . . . . . . . . . . . . 44 2.1.6 Théorème de représentation . . . . . . . . . . . . . . . . . . . 47 2.1.7 Lemme de Farkas et de Gordan . . . . . . . . . . . . . . . . . 49 2.2 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.2.1 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.2.2 Fonction D.C. . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3 Optimisation Linéaire 65 3.1 Problème d'optimisation linéaire . . . . . . . . . . . . . . . . . . . . 65 3.2 Solution d'optimisation linéaire . . . . . . . . . . . . . . . . . . . . . 67 3.2.1 Théorème d'existence de solution optimale d'optimisation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.2.2 Solution de base . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3 Méthodes de résolution du problème (OL) . . . . . . . . . . . . . . . 75 3.3.1 Méthode graphique . . . . . . . . . . . . . . . . . . . . . . . . 75 3.3.2 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . 76 3.3.3 Tableau du simplexe . . . . . . . . . . . . . . . . . . . . . . . 85 3.3.4 Méthode des deux phases . . . . . . . . . . . . . . . . . . . . 89 3.3.5 Règles d'anti-cyclage . . . . . . . . . . . . . . . . . . . . . . . 93 3.3.6 Logiciels pour l'optimisation linéaire . . . . . . . . . . . . . . 97 4 Théorie de dualité 104 4.1 Problème dual et point-selle . . . . . . . . . . . . . . . . . . . . . . . 104 4.2 Dualité de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5 Conditions d'optimalité 114 5.1 Direction réalisable et Direction de descente . . . . . . . . . . . . . . 114 5.2 Conditions d'optimalité du problème d'optimisation sans contrainte . 116 5.3 Conditions d'optimalité du problème d'optimisation sous contraintesd'inégalités et d'égalités . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.3.1 Contrainte active et qualification de contrainte . . . . . . . . 118 5.3.2 Qualifications des contraintes usuelles . . . . . . . . . . . . . 120 5.3.3 Conditions de Karush-Kuhn-Tucker . . . . . . . . . . . . . . 123 Bibliographie 134 Index des définitions 135 Index des théorèmes 139