Introduction à loptimisation Aspects théoriques et numériques PDF

Les algorithmes génétiques diffèrent des autres méthodes d'optimisation car ils utilisent un codage des variables de contrôle plutôt que les variables de

Introduction à loptimisation aspects théoriques et numériques

Méthodes de type gradient. 2. Algorithmes pour l'optimisation SANS contrainte. Les méthodes de Newton en dimension supérieure. 3. Introduction `a

Introduction à lOptimisation Numérique

2.3.1 Algorithmes de gradient à pas fixe/pas optimal . solution de problèmes d'optimisation sans contrainte (cf chapitre 2) puis avec contraintes (cf.

Introduction à loptimisation Aspects théoriques et numériques

III.3 Méthodes de gradient . III.4 Les méthodes de Newton et quasi-Newton . ... Si K = V on dit que (I.1) est un problème d'optimisation sans ...

Méthodes Numériques : Optimisation

La première et principale partie du cours concerne les problèmes d'optimisation sans contraintes. Nous abordons les algorithmes de type descente de gradient

Introduction à loptimisation Aspects théoriques et numériques

III.3 Méthodes de gradient . III.4 Les méthodes de Newton et quasi-Newton . ... Si K = V on dit que (I.1) est un problème d'optimisation sans ...

Introduction à lOptimisation Numérique

Ces informations sont fournies en “boite noire” i.e. par un sous-programme indépendant de l'algorithme d'optimisation choisi : routine de calcul du gradient

Comparaison de différentes méthodes doptimisation sans

Dans ce TP d'introduction `a l'optimisation pour l'image nous allons introduire un gradient comment chercher le minimum d'une fonction par descente de ...

Méthodes numériques : optimisation

Apr 19 2015 chapitre portera sur les méthodes de gradient conjugué

Notes de cours - Préparation à lagrégation - Introduction à l

3 Conditions d'optimalité - optimisation sans contrainte L'interpolation de Lagrange et les algorithmes de gradients seront étudiés ultérieurement au.

[PDF] Introduction aux Méthodes dOptimisation sans Gradient pour l - Inria

Introduction aux Méthodes d'Optimisation sans Gradient pour l'Optimisation et le Contrôle en Mécanique des Fluides R Duvigneau

[PDF] Méthodes doptimisation sans gradient pour des probl`emes

18 avr 2013 · Méthodes d'optimisation sans gradient pour des probl`emes inverses en ingénierie pétroli`ere Laurent DUMAS avec F Delbos D Ding (IFPEN)

[PDF] Introduction à lOptimisation Numérique

Dans les chapitres suivants nous entrons dans le vif du sujet en nous intéressant à la ré- solution de problèmes d'optimisation sans contrainte (cf chapitre 2)

[PDF] Cours-Optimisationpdf

L'optimisation consiste en la recherche du minimum (ou du maximum) d'une cer- taine quantité appelée coût ou objectif Dans ce cours on supposera que le

[PDF] Méthodes Numériques : Optimisation - ceremade

La première et principale partie du cours concerne les problèmes d'optimisation sans contraintes Nous abordons les algorithmes de type descente de gradient

[PDF] Méthodes numériques : optimisation - ceremade

19 avr 2015 · chapitre portera sur les méthodes de gradient conjugué et s'il reste un pour résoudre des problèmes d'optimisation avec contraintes

[PDF] optimisationpdf

Plan du cours • Introduction • Analyse de la fonction objectif • Conditions d'optimalité sans contrainte • Résolution d'équations • Optimisation sans

[PDF] aspects théoriques numériques et algorithmes

1 3 6 Le gradient d'un champ scalaire 4 Quelques algorithmes pour l'optimisation sans contraintes 4 6 Les méthodes de Newton et quasi-Newton

[PDF] Introduction à loptimisation Aspects théoriques et numériques

Même pour le gradient à pas optimal qui est en principe la meilleure de ces méthodes d'un point de vue de la rapidité de convergence celle-ci peut être lente

[PDF] Résumé dOptimisation

Et donc le gradient de f en uk+1 lui est orthogonal 5 2 Méthode de Newton Si f est une fonction réguli`ere dont on sait calculer le gradient et la matrice

Ecole Nationale Supérieure d"Electricité et de Mécanique

Introduction à l"optimisation

Aspects théoriques et numériquesCours de première année - année universitaire 2014-2015

Yannick PRIVATLaboratoire Jacques-Louis Lions, UMR 7598 Université Pierre et Marie Curie - Paris 6 & CNRS email : yannick.privat@upmc.fr -ii-

Préambule

Ce cours présente les bases théoriques et numériques de l"optimisation Vous trouverez,

dans le premier chapitre des rappels de calcul différentiel et des précisions sur le vocabulaire

de l"optimisation. Dans le second chapitre, nous étudierons quelques résultats théoriques

(existence, unicité de solutions) sur l"optimisation sans puis avec contrainte(s). Ces dévelop-

pements sont destinés à mettre en place les notions utiles au développement d"algorithmes numériques. C"est l"objet des troisième et quatrième chapitres où nous introduisons les algorithmes classiques de l"optimisation numérique. Ce polycopié est volontairement succinct. Sa lecture ne peut exempter d"une présence assidue en cours. L"évaluation de ce cours sera organisée de la façon suivante : - Un rapport sur séances de travaux pratiques (1/4 de la note finale); - Un examen écrit (3/4 de la note finale).

Y. PRIVAT

Paris, février 2015-iii-

Table des matières

-iv-

Table des matières

Préambuleiii

I. Introduction

1 I.1 Le vocabulaire de l"optimisation. . . . . . . . . . . . . . . . . . . . . . . . . . .1 I.2 Quelques rappels de calcul différentiel. . . . . . . . . . . . . . . . . . . . . . . .2 I.3 Détour vers la dimension finie. . . . . . . . . . . . . . . . . . . . . . . . . . . .4 I.4 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 II. Généralités et étude théorique des problèmes d"optimisation 7 II.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7 II.2 Résultats d"existence et d"unicité. . . . . . . . . . . . . . . . . . . . . . . . . .8 II.3 Conditions d"optimalité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9 II.3.1 Cas sans contrainte. . . . . . . . . . . . . . . . . . . . . . . . . . . . .9 II.3.2 Cas avec contraintes. . . . . . . . . . . . . . . . . . . . . . . . . . . . .11 II.4 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14 III. Algorithmes pour l"optimisation sans contrainte 19 III.1 Algorithmes unidimensionnels ou recherche du pas. . . . . . . . . . . . . . . .19 III.1.1 Méthode de la section dorée. . . . . . . . . . . . . . . . . . . . . . . .19 III.1.2 Méthode d"interpolation parabolique. . . . . . . . . . . . . . . . . . . .20 III.2 Quelques notions sur les algorithmes. . . . . . . . . . . . . . . . . . . . . . . .22 III.3 Méthodes de gradient. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23 III.3.1 Gradient à pas fixe ou optimal. . . . . . . . . . . . . . . . . . . . . . .23 III.3.2 Méthode du gradient conjugué. . . . . . . . . . . . . . . . . . . . . . .25 III.4 Les méthodes de Newton et quasi-Newton. . . . . . . . . . . . . . . . . . . .27 III.4.1 Méthodes de Newton. . . . . . . . . . . . . . . . . . . . . . . . . . . .28 III.4.2 Méthode de quasi-Newton de Lenvenberg-Marquardt. . . . . . . . . . .29 III.5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31 IV. Algorithmes pour l"optimisation sous contrainte(s) 33
IV.1 Retour sur les conditions d"optimalité. . . . . . . . . . . . . . . . . . . . . . .33 IV.2 Conditions d"optimalité nécessaires du second ordre. . . . . . . . . . . . . . . .33 IV.3 Les algorithmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34 IV.3.1 Méthode du gradient projeté. . . . . . . . . . . . . . . . . . . . . . . .34 IV.3.2 Méthodes de pénalisation. . . . . . . . . . . . . . . . . . . . . . . . .36 IV.3.3 Méthode de dualité : l"algorithme d"Uzawa. . . . . . . . . . . . . . . .37 IV.4 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39-v- I.

Introduction

I.1Le vocabulaire de l"optimisation

SoitVest un espace vectoriel normé, muni de la normekk. Dans ce cours, on s"intéresse au problème suivant infx2Kf(x)(I.1) oùKVetf:K!Rest une fonction, appeléefonction coûtoucritère. SiK=V, on dit que (I.1) est un problème d"optimisationsans contrainte. SiK(V, on dit que (I.1) est un problème d"optimisationsous contrainte. Si dimK <+1(resp. dimK= +1), on dit que (I.1) est un problème d"optimisation en dimension finie (resp. infinie). Remarquons que ce formalisme englobe tous les problèmes d"optimisation, y compris les problèmes de maximisation puisque maximiser une quantité revient à minimiser son opposé. Dans le cadre de ce cours, on étudiera essentiellement l"optimisation en dimension finie. Nous adopterons la convention suivante : si l"on veut indiquer que la valeur du minimum est atteinte, on écrira minx2Kf(x) tandis que l"on utilisera la notation "inf" quand on ne sait pasa priorisi la valeur de la borne inférieure est, ou non atteinte.

On dira que

xest unminimiseur globaldu problème (I.1) sixest solution de ce problème; xest unminimiseur localdu problème (I.1) s"il existe un voisinageVdextel quexest solution du problème infx2Vf(x): Enfin, rappelons que toute partie minorée non vide deRadmet une borne inférieure, caractérisée de la façon suivante :Proposition I.1.1. Suites minimisantes

SoitX, une partie minorée non vide deR.

Alors, les assertions suivantes sont équivalentes : (i)m= inffx;x2Xg; (ii)8" >0;9x2Xjmx < m+"; (iii)mest un minorant deXet il existe(xn)n2N2XN, appelée "suite minimisante" convergeant versm.-1-

CHAPITRE I. INTRODUCTION

En conséquence, voici les questions qu"il sera naturel de se poser lorsque vous rencontrerez un problème d"optimisation :

Ce problème possède t-il une solution?

1ercas de figure.

Si ce problème possède une solution, on cherchera à la caractériser (par exemple, est-elle unique?) ou mieux, à la déterminer lorsque ce sera possible. On exploitera pour cela les conditions nécessaires d"optimalité (aux premier et deuxième ordres).

2èmecas de figure.

Si ce problème ne possède pas de solution, on cherchera à exhiber une suite minimi- sante, i.e. une suite d"éléments de l"ensembleKconvergeant versinfff(x);x2Kg. Enfin, on se posera la question, lorsque l"on ne sait pas déterminer explicitement les solutions du problème d"optimisation, du choix de méthodes numériques adaptées pour déterminer le minimum et ses minimiseurs. Terminons ce paragraphe en présentant quelques problèmes d"optimisation.

Problème 1. (dimension finie)

,!Déterminer le parallélépipède rectangle de volume maximal parmi ceux dont la surface extérieure vaut 6. En introduisanta,betc, les longueurs des côtés du parallélépipède, on se ramène

à la résolution du problème

8 :supV(a;b;c) =abc ab+ac+bc= 3; a0; b0; c0: Il s"agit donc d"un problème d"optimisation dansR3sous contrainte.

Problème 2. (dimension infinie)

,!Problème de la reine Didon. Le problème consiste à trouver la courbe plane de longueur`fixée qui enclot avec le segment reliant ses deux extrémités, la portion plane d"aire maximale, autrement dit, on résout pourb > a0, sup y2YZ b a y(x)dx oùYest un espace fonctionnel donné, par exemple Y= y2C1([a;b])jZ b ap1 +y02(x)dx=`ety(a) =y(b) = 0 :I.2Quelques rappels de calcul différentiel Commençons par la notion dedifférentiabilité.-2-

I.2. QUELQUES RAPPELS DE CALCUL DIFFÉRENTIEL

Définition I.2.1. Différentiabilité

SoientEetF, deux espaces vectoriels normés réels. SoitU, un ouvert deEet x

02U. On dit qu"une applicationf:U!Festdifférentiable enx0ou admet

un développement limité au premier ordre enx0s"il existedfx02L(E;F) (continue), telle que f(x0+h)f(x0) =dfx0(h) +oh!0(khkE):

Quelques remarques immédiates :

En dimension infinie, la différentiabilité d"une fonction dépend de la norme dont sont munis les espacesEetF. Ça n"est bien sûr pas le cas en dimension finie, étant donné que toutes les normes sont équivalentes. Par définition, l"applicationdfx0est continue. Il n"en est pas nécessairement de même de l"applicationdf:U!L(E;F) x

07!dfx0. Si c"est le cas, on dira quefest de classe

1au voisinage dex0.

Comment calculer de façon pratique une différentielle? Si l"on a au préalable démontré quefest différentiable enx0, alors, on peut écrire pour touth2Eque df x0(h) = lim"!0"2Rf(x0+"h)f(x0)" L"intérêt d"une telle écriture vient du fait que l"on s"est ainsi ramené au calcul d"une limite d"une fonction d"une variable réelle. La limite précédente s"appelle indifféremmentdérivée directionnelle defenx0selon le vecteurhoudifférentielle au sens de Gâteaux defenx0dans la directionh. Notons que sifest différentiable, il est aisé de montrer quefadmet une dérivée directionnelle selon tout vecteurh, mais que la réciproque n"est pas vraie. Résumons sous la forme d"un schéma les relations d"implication entre ces différentes pro- priétés. festC1enx0=)fest différentiable enx0=)festC0enx0 fdérivable enx0selon tout vecteurhquotesdbs_dbs4.pdfusesText_8