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.

    • Niveau: Licence et Master

    • 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 dans ce cours. On introduit aussi les divers types de convergence locale ainsi que 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 méthode de la plus profonde descente et qui remonte à Cauchy est présentée dans le but de vérifier 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, la mise en oeuvre 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).

  • Exercices suplémentaires (Chapitres I, II et III)

  • Chapitre IV: Les Méthodes Newtoniennes

    La méthode de Newton est abordée dans ce chapitre, son mérite est qu’elle sert de base pour les méthodes qui nous intéressent par la suite (quasi-Newton). On exposera aussi les avantages et les inconvénients de l’algorithme de Newton toutes en proposant quelques solutions sous formes d’algorithmes modifiés (Newton avec décomposition de Choleski et Newton tronqué).

    • Questions de cours Quiz

      Après avoir lus le cours (chapitre IV) à partir de la page 57, essayer de répondre au questionnaire suivant

    • Compilateur fortran en ligne URL

      Pour les TP,  vous pouvez utiliser un compilateur fortran en ligne:  JDoodle.com

      JDoodle offers following services:

      • Online Compiler and IDE.

      • Online Terminals for Databases.

      • Compiler API.

      • Online Assessment.


    • TP N°6 Assignment

      Modifier le code Fortran steepest_0.f90 ci-joint  pour inclure les fonctions tests de Dixon, Oren, Powel, Rosenbrock, Wood généralisées (voir le fichier fonctions_tests.pdf).

    • TP N°7 Assignment

      Modifier le code Fortran choleskii_tp0.f90 ci-joint  pour inclure la possibilité de résoudre un système linéaire de la forme Ad=b à l'aide de la méthode de décomposition de Choleskii suivit de la résolution de deux systèmes triangulaires. Dans le code demandé la matrice A et le vecteur b sont à donnés, la sortie est un vecteur d.

    • TP N°8 Assignment

      Utiliser le code produit dans le TP 7 pour modifier le code Fortran newton_tp0.f90 ci-joint  pour inclure la possibilité de résoudre un problème d'optimisation d'une fonction quadratique par la méthode de Newton modifiée du type Newton-Cholleskii (voir le cours).

    • Animation vidéo URL

      Une animation montrant la convergence lente de la méthode du gradient à pas fixe

    • Acheminement des itérées de la méthode du gradient avec recherche linéaire


  • 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ées à 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).

    • TP N°9 Assignment

      Modifier le code Fortran quasinewton0.f90 ci-joint  pour inclure les fonctions tests de Dixon, Oren, Powel, Rosenbrock, Wood généralisées (voir le fichier fonctions_tests.pdf).

    • TP de validation FORTRAN du S2, le Jeudi 24/06/2021 à 08h30 (Salle TP-Master)

  • 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.

    • Examens précédants

    • Discussion Finale