Méthodes Numériques : Optimisation - CEREMADE

1 M thodes Num riques : OptimisationCours de L3, 2020-2021 Universit Paris-DauphineDavid Gontier(version du 7 mai 2021).M thodes Num riques : Optimisationde David Gontierest mis disposition selon les termes de lalicenceCreative Commons Attribution- Pas dUtilisation Commerciale - Partage dans les M mes Conditions DES MATI RES1 G n ralit Conventions.. Calcul de d riv es par diff rences finies.. Algorithmes it ratifs.. Vitesse de convergence.. Convergence lin aire.. Convergence quadratique.. Efficacit d un algorithme it ratif..12I Optimisation sans contraintes132 M thodes en une M thodes par dichotomie.

2 R soudref(x) = 0par dichotomie.. TrouverargminFpar la m thode de la "section dor e".. R soudref(x) = 0avec des algorithmes de type Newton.. L algorithme de Newton.. M thode de la s cante.. Exercices suppl mentaires..223 M thodes de type descente de .. Nombre de variables.. Surfaces de niveau.. Algorithme de descente.. M thode de gradient pas constant.. Algorithme.. tude de la convergence pour une fonction quadratique.. Multiplication matrice/vecteur.. tude de la convergence dans le cas g n ral.. Descente de gradient pas (quasi-) optimal.. Pas optimal.

3 Pas quasi-optimal.. Convergence des m thodes de descente.. Exercices suppl mentaire..37 TABLE DES MATI RES44 Le gradient conjugu Rappels sur les espaces hilbertiens.. Principe des m thodes conjugu es.. Le gradient conjugu .. Algorithme.. Etude th orique.. Extensions non-lin aires..465 Retour sur l algorithme de La m thode de Newton en plusieurs dimensions.. Newton classique.. M thode de Newton + gradient conjugu .. La m thode BFGS.. Pr sentation.. BFGS dans le cas quadratique..52II Optimisation avec contraintes546 Introduction l Optimisation sous Exemples.

4 Contraintes d in galit s lin aires, et repr sentation graphique..577 M thodes par Projection sur un ensemble convexe ferm .. Premi res propri t s.. M thode du gradient projet .. Algorithme.. Analyse dans le cas quadratique.. Calcul de projections.. Optimisation quadratique sous contraintes d galit s lin aires.. Optimisation quadratique sous contraintes d in galit s lin aires..648 P nalisation des P nalisation ext rieure pour les contraintes d galit .. P nalisation int rieure pour les contraintes d in galit s.. Algorithmes par p nalisation..709 Suppl R seaux de neurones.

5 Notations et d finitions.. Entra nement d un r seau de neurones, et r tro-propagation.. Calcul des gradients.. Bonnes pratiques num .. Astuces de code..75A Rappel d alg bre lin aire.. Formules de Taylor.. Calcul spectral..78 INTRODUCTIONDans ce cours1, nous tudions des algorithmes pour r soudre deux types de probl mes : des pro-bl mesd optimisationet des probl mesde r solution. Un probl me d Optimisation est un probl me dela formex = argmin{F(x),x Rd},o Fest une fonction deRddansR, et les probl mesde r solutionsont de la formeTrouverx Rdsolution def(x) =0,o fest une fonction deRddansRd(c est dired quations dinconnues).

6 Notre but n est pas de trouver dessolutions analytiques ces probl mes (de typex = 23+ln(2)), mais de trouver des solutionsnum riques(de typex = ). Dans la plupart desapplications, c est la connaissance d une solution num rique qui est int pr sentons diff rentsalgorithmes de r solution it ratifs. Un tel algorithme g n re une suite(xn)qui converge versx , ce qui permet de trouver une solution num rique avec une pr cision arbi-traire. Nous prouverons la convergence de ces algorithmes, et tudierons leurvitesse de cours sera illustr par de nombreux exemple premi re et principale partie du cours concerne les probl mes d optimisationsans abordons les algorithmes de type descente de gradient, la m thode du gradient conjugu , et lesm thodes de type Newton ou la seconde partie du cours, nous exposons certains algorithmes pour des probl mes d optimi-sationavec contraintes.

7 Nous introduisons les m thodes de p nalisation et de gradient projet .1. Page web du Il existe des quations sans solution analytique. Par exemple, comme le montre la th orie d Abel-Galois, l quationx5 3x 1 = 0n admet pas de solutions par radicales (s crivant avec les op rations l mentaires).TABLE DES MATI RES6 JupyterInstallationLes exemples et les TPs de ce cours se feront sur l interface3 Jupyter, qui est un outil qui permetd crire duPythonsur un navigateur Web. Pour installer Jupyter, il faut d abord installerPython3,puis lancer dans un Terminal la commande1> pip3 install jupyterCette commande permet d installer l environnementJupyter.

8 Il faut aussi charger la librairie de calculsnum riques et la librairie graphique, avec1> pip3 install numpy , matplotlibUne fois l installation termin e, on peut lancer directement unnotebookavec la commande41> cd DossierOuEstLeNotebook/2> jupyter notebookPlusieurs lignes s affichent dans le Terminal, dont une ligne de la forme1 Copy/paste this URL into your browser when you connect for the first time ,2to login with a token:3http :// localhost :8890/? token=f432a30bc62d1af678101656a61dc1e69d 38090df31e4674Si le navigateur Web ne se lance pas directement, lancez en un (Firefox, Safari, Chrome.)

9 , et copierl adresse pr c dente comme fichierPour cr er un nouveau fichier, cliquer sur "New" (en haut droite), et s lectionnerPython3. Unepage s ouvre. Cette page, appel enotebook, sera structur e encellules. Dans la premi re cellule, on criratoujours1%pylab inlineCette ligne permet de charger les librairiesnumpy(fonctions math matiques) etmatplotlib(affichagegraphique). On ex cute la cellule avecshift+enter. Pour v rifier que tout marche bien, on peut criredans la deuxi me cellule1tt = linspace (0 ,1 ,100)2deff(x) :returnsin (2*pi*x)3plot(tt, f(tt))puis valider avecshift+enter. Une sinuso de devrait appara de mon ordinateur ?

10 Projet plusieurs ?Il existe maintenant des serveurs Jupyter en ligne. On peut avez un compte Google, vous avez un compte Microsoft. Il y a , qui permet de faire du LATEX(voir documentationici).3. Le nom Jupyter est une concat nation de En lan ant la commandejupyter notebook, on cr e unserveursur l ordinateur (localhost). Vous pouvez ensuitedialoguez avec ce serveur gr ce votre navigateur Web. Si vous fermez le Terminal, vous fermez le serveur, et votrenotebook ne marche plus !CHAPITRE1G N RALIT ConventionsDans ce manuscrit, nous emploierons syst matiquement les lettresx, y, z.