Topic outline

  • Ressources du cours

    • Le cours est axé sur la formulation, la résolution et l'analyse des problèmes d'optimisation non linéaire.  Les techniques modernes pour résoudre les problèmes d'optimisation non linéaire sont discutées en détail.

    • Connaissances préalables recommandées : Connaissances en calcul différentiel et en algèbre linéaire. Pour les TP une connaissance de base en programmation (C, FORTRAN, ...).

    • Référence principale (Textbook): Jorge Nocedal, Stephen J. Wright, Numerical optimization. Springer (1999).

     

  • Chapitre I: Notions Générales

    On introduit les outils de base pour la suite. On trouve les plus importants des résultats (en Algèbre et en Analyses) utilisés par la suite. Le théorème de convergence (de Zangwill). On introduit aussi les divers types de convergence locale, pour plus de détaille). On introduit aussi les méthodes de Gauss-Seidel et approximations successives dans un but purement théorique.

  • Chapitre II: Les Fondements de l’optimisation sans contraintes

    Dans ce chapitre on y trouve les conditions d’optimalité nécessaires et suffisantes. La notion de convexité pour les fonctions réelles est introduite. La négligence des notions de convexité faible (pseudo-convexité, quasi-convexité...) est due au fait que les démonstrations de convergence exigent des conditions de convexité forte. La méthode de la plus profonde descente et qui remonte à Cauchy est présentée dans le but d’appliquer les conditions d’optimalité, ce qui donne une autre interprétation aux méthodes vue dans le chapitre précédant.

  • Chapitre III: Recherche linéaire

    Un point délicat est soulevé dans le deuxième chapitre : L’ambiguïté dans le choix du pas qui est crucial pour la convergence des algorithmes : "Approximation successive" et "la plus profonde pente". La solution est dans l’adoption d’une recherche linéaire, bien que la direction est généralement facile à calculer, l’écriture d’une bonne recherche linéaire est une tache assez difficile. C’est dans cet esprit qu’un chapitre entier est consacré à ce sujet. On distinguera deux modes de recherches linéaires : Exacte et inexacte. Une tendance se dessine alors vers l’adoption des recherches linéaires inexactes (plus économiques), notre intérêt est porté pour l’étude plus au moins détaillé pour les plus importantes de ces méthodes à savoir Goldestein, Armijo et Wolfe. A la fin de ce chapitre, on expose un théorème essentiel de convergence globale (théorème de Zoutendijk), ce théorème peut être considéré comme une alternative à celui de Zangwill (vue en chapitre 1).

  • Chapitre IV: Les Méthodes Newtoniennes

    L’algorithme de Newton est développé dans ce chapitre, son mérite est qu’il sert de base pour les méthodes qui nous intéressent par la suite (quasi-Newton). On expo- sera aussi les avantages et les inconvénients de l’algorithme de Newton toutes en propo- sant quelques solutions sous formes d’algorithmes modifiés (Newton avec décomposition de Choleski et Newton tronqué).

  • Chapitre V: Méthodes Quasi-Newton

    Des algorithmes plus performants sont proposés dans ce chapitre, l’idée est de construire itérativement certaines matrices par des formules de mise à jour effectuée à chaque itération de l’algorithme de minimisation. On exposera les principes conduisant vers l’obtention des formules de mise à jour les plus célèbres : SR1 (qui est une méthode de correction de rang un), DFP et BFGS (qui sont des méthodes de correction de rang deux).

  • Bibliographie

          [1]  M. S. Bazara. H.D. Sherali, C.M Shetty. Nonlinear programming. J.W&S (1993)

    2. [2]  J. F. Bonnans, J. C. Gilbert, C. Lemaréchal and C. A. Sagastizábal. Numerical optimization : theoretical and practical aspects. Springer Science & Business Media (2006).

    3. [3]  C. G. Broyden. Quasi-Newton method and their application to function minimization, Mathematics of Computation, 21,(1967).

    4. [4]  A. Cauchy. Méthodes générales pour la résolution des systèmes d’équations simultanées. Compte rendus Acad. Sc. Paris, Tome 25 (1847) 536-538.

    5. [8]  F. Chatelin. Eigenvalues of Matrices, J.Wiley & S (1993).

    6. [9]  W. C. Davidon. Variable metric methods for minimization, AEC Research Develop- ment, Report ANL-5990 (1959).

    1. [10]  A. A. Goldestein, J.F. Price. An effective algorithm for minimization. Num. Math. 10,(1967)184-189.

    1. [11]  M. J. D. Powell. Some properties of the variable metric algorithm for minimization wi- thout exact line searches, in Nonlinear Programming, SIAM-AMS Proceeding, Vol. IX, R.W. Cottle, and C.E. Lemke, eds., SIAM, (1976)35-72.

    2. [12]  L. Schwartz. Analyse, topologie générale et analyse fonctionnelle, Hermann (1970).

    3. [13]  M. Sibony, J.C. Mardon. Analyse Numérique. Systèmes linéaires et non linéaires, HER- MAN (1982).

    2. [14]  W.I.Zangwill.Nonlinearprogramming:aunifiedapproach,PrenticeHall,Englewood Cliffs, RI, 1969.

    3. [15]  G. Zoutendijk. Non linear programming, computation programming. In J. Abadie (ed), integer and non linear programming. North Holland (1970)37-86.