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

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 contrainte

L'algorithme débute par le choix d'un codage permettant de représenter les variables du problème d'optimisation par une structure génétique Une population

[PDF] 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 contrainte

[PDF] Introduction à lOptimisation Numérique - Sébastien Tordeux

2 4 1 Algorithmes de gradient à pas fixe/pas optimal ce cours) : ce sont les paramètres sur lesquels l'utilisateur peut agir pour faire évoluer le tion de problèmes d'optimisation sans contrainte (cf chapitre 2), puis avec contraintes (cf

[PDF] Résumé dOptimisation

5 1 2 Méthode de la plus profonde descente (méthode du gradient) Ceci un résumé des principaux résultats du cours d'optimisation le cas pour les probl` emes sans contrainte, et que si la ou les solutions sont sur le bord, il y a, comme

[PDF] Introduction `a loptimisation : aspects théoriques, numériques et

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

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

19 avr 2015 · chapitre portera sur les méthodes de gradient conjugué, et s'il reste un le cas de convergence d'ordre β avec β > 1, le nombre de décimales

[PDF] Méthodes Numériques : Optimisation - Ceremade - Université Paris

7 3 1 Optimisation quadratique sous contraintes d'égalités linéaires Nous abordons les algorithmes de type descente de gradient, la méthode du gradient

[PDF] COURS OPTIMISATION Cours à lISFA, en M1SAF Ionel Sorin

3 2 1 Méthodes de gradient à pas optimal 4 2 Optimisation sous contraintes d' inégalités Les méthodes de gradient sont définis alors par les relations :

[PDF] 2 Optimisation sans contraintes

Les contraintes inégalité inactives n'ont pas d'influence sur la solution x* du problème (PO) On peut les (dérivée directionnelle = produit scalaire avec le gradient) Fonction Méthode de mise à l'échelle : transformation affine X' = αX + β

[PDF] Méthodes numériques pour loptimisation Méthode de gradient (1

de gradient (1) Probl`eme d'optimisation sans contrainte inf Méthode du gradient conjugué : tr`es efficace pour les syst`emes SDP (vk est minimiseur de J

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

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

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