[PDF] Cours dOptimisation numérique PDF

Ecrire les conditions nécessaires d'opti- malité et calculer cette solution. 3. (difficile) Montrer que le probl`eme admet bien une solution. Exercice 3. On

QUELQUES EXERCICES CORRIGÉS DOPTIMISATION EXERCICE

QUELQUES EXERCICES CORRIGÉS D'OPTIMISATION. EXERCICE I (Calcul différentiel). 1. Montrer que la fonction f : R2 ? R2 définie par f(x y) =.

MS41 Optimisation I

29 juil. 2014 Optimisation I. Recueil d'exercices corrigés et aide-mémoire. Gloria Faccanoni i http://faccanoni.univ-tln.fr/enseignements.html.

Optimisation I

Il est important de ne pas consulter le corrigé qui se trouve à la fin du texte sur des feuilles de couleur avant d'avoir terminé les exercices. 2° Évaluez vos

Devoir Maison dOptimisation Numérique – Corrigé

Devoir Maison d'Optimisation Numérique. –. Corrigé. Exercice 1 (6 points). Soit C ? R2 l'ensemble donné par. C := {(x y) ? R2 : (x2 ? 1)2 + y2 ? 4}.

Table des matières 1 Calcul différentiel

QUELQUES EXERCICES CORRIGÉS D'OPTIMISATION. Yannick PRIVAT - yannick.privat@unistra.fr 2 Analyse des problèmes d'optimisation sans contrainte.

1 Les conditions de Kuhn-Tucker

Corrigés d'optimisation convexe et quadratique Exercices corrigés . ... C'est un probl`eme d'optimisation sous contrainte égalité. On utilise donc la.

MS52 Optimisation

6 oct. 2016 On a inclus dans ce texte nombreux exercices corrigés. ... et l'omniprésence des fonctions de plusieurs variables et de l'optimisation.

Corrigé optimisation 3M

Exercice 7.5. ? Figure d'étude et définition des inconnues. • x = distance de O à P. • base du rectangle = 2x. • hauteur du rect. = y. ? À optimiser.

Corrigé type de la série des exercices 1 Optimisation sans

Corrigé type de la série des exercices 1. Optimisation sans contraintes -LMD- S5. Solution de l'exercice 1. Soit f : R2 ?? R la fonction définie f(x y) =.

[PDF] Exercices sur le cours “Optimisation et programmation dynamique”

Montrer que le point (10) est le minimum du probl`eme Exercice 6 Soit A une matrice symétrique de format n × n 1 Montrer que m = min

[PDF] Optimisation I - Sofad

Voici quelques suggestions pour réussir ces exercices 1° Rédigez les solutions en prenant pour modèle les exemples présentés dans le texte Il est important de

(PDF) Optimisation: Cours et exercices Version 2021 - ResearchGate

21 sept 2021 · PDF On Jul 9 2021 Sonia Radjef published Optimisation: Cours et exercices Version 2021 Find read and cite all the research you need

[PDF] Optimisation - Dspace

12 mar 2020 · 1 I Optimisation sans contraintes 5 2 5 Quelques exemples corrigés Chaque chapitre est clôturé par un ensemble d'exercices

[PDF] Devoir Maison dOptimisation Numérique Corrigé

Corrigé essayez de le faire en deux heures max Vrai ou faux 1 (4 points) Exercice 2 (5 points) Considérer la fonctionnelle J(f) := ? 1

[PDF] Devoir Maison dOptimisation Numérique – Corrigé

Devoir Maison d'Optimisation Numérique – Corrigé Exercice 1 (6 points) Soit C ? R2 l'ensemble donné par C := {(x y) ? R2 : (x2 ? 1)2 + y2 ? 4} 1

(PDF) Exercices + Correction dOptimisation Linéaire - Academiaedu

Exercice 1 (Voir la solution 1) Un artisan menuisier fabrique des tables et des chaises à base du bois et d'un métal pour le compte d'un revendeur

[PDF] Cours dOptimisation numérique

5 2 Exercices sur l'optimisation sans contraintes Cours de G Carlier (optimisation) : https://www ceremade dauphine fr/?carlier/progdyn pdf

[PDF] Éléments de Cours exercices et problèmes corrigés

ANALYSE VARIATIONNELLE ET OPTIMISATION Éléments de Cours exercices et problèmes corrigés D AZÉ J -B HIRIART-URRUTY

Universite Montpellier 2 (2016-2017) - M1 Mathematiques statistique et applications - Optimisation Numerique

Cours d'Optimisation numerique

Notes redigees par Terence Bayen

Table des matieres

1 Introduction a l'optimisation4

2 Calcul dierentiel, espaces de Hilbert, convexite 6

2.1 Un peu de calcul dierentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Fonctions semi-continue inferieurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3 Brefs rappels sur les espaces de Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4 Convexite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.1 Proprietes generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.2 Fonctions convexes de classeC1etC2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12

2.4.3 Un peu de sous-dierentiabilite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5 Quelques resultats d'existence et d'unicite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.6 Lemme de Farkas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Conditions d'optimalite18

3.1 Optimisation sans contraintes et condition d'Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Theoreme de Fritz-John et Karush-Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3 Criteres de qualication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.1 Condition de Mangasarian-Fromowitz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.2 Qualication et c^one de Bouligand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.3 Preuve de KKT par le lemme de Farkas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.4 Cas des contraintes anes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.5 Contraintes convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.6 Condition de qualication pour les contraintes d'inegalite . . . . . . . . . . . . . . . . . . . . .

3.3.7 Cas des contraintes d'egalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.8 Cas general (contraintes d'egalites et d'inegalites) . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4 Resume des conditions de qualication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5 Theoreme de Karush-Kuhn-Tucker en dimension innie . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.1 Cas des contraintes d'egalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.2 Cas des contraintes d'inegalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6 Conditions d'optimalite au second ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7 Dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7.1 Generalites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7.2 Points selles de Lagrangien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7.3 Problemes convexes et dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7.4 Exemple de saut de dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7.5 Preuve de la condition necessaire au second ordre par dualite . . . . . . . . . . . . . . . . . . .

4 Algorithmes numeriques39

4.1 Algorithmes de descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.1 Regle d'Armijo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.2 Regle de Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.3 Conditionnement pour la methode de gradient a pas optimal . . . . . . . . . . . . . . . . . . .

4.1.4 Gradient projete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.5 Algorithme d'Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44
2

TABLE DES MATI

ERES3

4.2 Methode du gradient conjugue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3 Algorithme de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.1 Methode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.2 Methode de quasi-Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Exercices51

5.1 Exercices sur la convexite et les espaces de Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2 Exercices sur l'optimisation sans contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3 Demonstration du lemme de Farkas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.4 Exercices autour du theoreme de KKT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.5 Conditions d'optimalite en dimension inni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.6 Exercices autour de la dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.7 Exercices autour des algorithmes numeriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.8 TP sous matlab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Sujets d'examen66

6.1 Session 2015-2016 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.1.1 Partiel (1h) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.1.2 Examen nal (2h) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2 Session 2016-2017 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.1 Partiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.3 Devoir Maison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.3.1 Devoir Maison sur l'algorithme de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 1

Introduction a l'optimisation

Un probleme d'optimisation met en evidence des variables d'etat (parametres) et des contraintes. Le but est de

minimiser une fonctionfdansC: infx2Cf(x):(1.0.1)

Icifest une fonction deni sur l'ensembleC(un sous-ensemble d'un espace vectoriel norme) a valeurs reelles.

L'ensembleCs'appelle ensemble de contraintes : il s'agit d'une restriction sur les parametres admissibles.

On ne s'interessera pas dans ce cours a des problemes multi-criteres: inf x2CF(x);

ouF(x) := (f1(x);:::;fm(x)) sontmfonctions a valeurs reelles denies surC. Ce type de probleme multi-objectif (i.e.

qui consiste a vouloir minimiser simultanement plusieurs objectifs parfois antagonistes) est plus dicile et depasse

le cadre de ce cours.

Les dierentes questions relatives a (1.0.1) que l'on est amene a se poser en optimisation sont les suivantes :

- 1. Existence d'une solution. - 2. Conditions necessaires d'optimalite (du type \f0(x) = 000). - 3. Conditions susantes d'optimalite. - 4. Algorithmes numeriques pour trouver une solution. - 5. Analyse qualitative de la solution lors d'une perturbation des parametres.

On etudiera principalement les points 1,2,3 et 4 (partiellement). Citons quelques exemples de problemes bien etudies

dans la litterature:

Probleme isoperimetrique: parmi les courbes fermeesCdu plan et de longueur 1, trouver celle d'aire maximale:

max

C;L(C)=1A(C):

Il s'agit d'un probleme geometrique a transformer analytiquement. Le probleme du voyageur de commerce: on a un graphe avecnpoints (les villes) etn(n1)2 ar^etes de co^utcij telles quecij=cji. On posexij= 1 si on va du noeudiau noeudjet 0 sinon. On cherche a minimiser: min x2Rn2X

1i;jnc

ijxij; sous les contraintes Pn j=1xij=Pn i=1xij= 1 etP i2Ixij jIj 1 pour tout sous-ensembleI&f1;:::;ng. Ce

probleme modelise comment un voyageur de commerce peut passer dans toutes les villes une et une seule fois

sans cyclage. Son but est de minimiser son co^ut de trajet total possible (i.e. de trouver le meilleur chemin

possible). Il s'agit d'un exemple de probleme lineaire mais dont la complexite est tres elevee (grand nombre de

contraintes). 4 5

Probleme de la cha^nette : il s'agit de trouver la forme prise par une cha^nette accrochee a deux points du mur:

ceci revient a etudier un probleme de calcul des variations: inf y2C1([a;b];R) y(a) =aa;y(b) =ybZ b a y(x)p1 +y02(x)dx:

En eet, la courbe optimale (dite cha^nette) minimise son energie potentielle de pesanteur. Ainsi, ce probleme

exprime la minimisation de cette energie parmi toutes les courbes possible.

Le probleme de Newton consiste a trouver parmi tous les objets convexes de hauteur donnee et de base donnee,

celui qui tombe le plus rapidement, c.a.d., celui qui en tombant minimise la resistance de l'air. Sous certaines

hypotheses, ce probleme se ramene a un probleme de calcul des variations du m^eme type que le precedent (mais

c'est un probleme tres dicile a resoudre). Parmi les solutions d'un systeme lineaireAx=bavecA2Mmn(R) (avecm < n), on cherche celle qui minimise la semi-normekxk0qui mesure le nombre de composantes non-nulles: min x Ax=bkxk0:

Trouver une solution au systeme ayant le plus de composantes nulles est tres utile dans le domaine du traitement

du signal. La diculte est que la fonction a minimiser n'est pas reguliere.

Le cours suivra les grandes lignes suivantes:

Existence de solutions en optimisation (proprietes de convexite convexite) Conditions necessaires et susantes d'optimalite, qualication (dimension nie et innie)

Theorie de la dualite

Methodes numeriques (algorithmes de descente et Newton). Optimisation en dimension innie (conditions d'optimalite) et calcul des variations.

Il serait possible d'etudier d'autres aspects de l'optimisation comme par exemple la programmation dynamique (en

horizon ni ou en horizon inni) et le contr^ole optimal. Certains aspects seront traites plus en details en M2 (comme

le contr^ole optimal qui constitue la continuation naturelle du calcul des variations).

References: Pour certaines sections, le cours s'est inspire entre autres des polycopies mentionnes ci-dessous. Merci

de me signaler tout oubli. Une liste plus exhaustive des diverses references (livres) ayant ete utilises pour ce polycopie

est donnee a la n du document. - Cours de G. Carlier (calcul dierentiel) :https://www.ceremade.dauphine.fr/carlier/calculdiff.pdf - Cours de G. Carlier (optimisation) :https://www.ceremade.dauphine.fr/carlier/progdyn.pdf - Cours de S. Delabriere :https://webusers.imj-prg.fr/sylvie.delabriere/AnaConv/ACPoly.pdf - Cours de P. Cardaliaguet :https://www.ceremade.dauphine.fr/cardalia/OptiPgrDyn15-16.pdf - Cours de Y. Privat :https://www.ljll.math.upmc.fr/privat/documents/optimAgreg.pdf - Cours de A. Rondepierre et P. Weiss :http://www.math.univ-toulouse.fr/rondep/CoursTD/polyGMM4.pdf - Cours, exercices, sujet d'examen par E. Trelat :https://www.ljll.math.upmc.fr/trelat/

Chapitre 2

Calcul dierentiel, espaces de Hilbert,

convexite

On commence par quelques rappels de calcul dierentiel qui seront utiles notamment pour l'optimisation en dimension

innie.

2.1 Un peu de calcul dierentiel

On introduit le calcul en dimension quelconque qui sert pour etudier des fonctionnelles ou bien pour le calcul des

variations: par exemple, on s'interessera a la regularite de la fonctionnelle

J(x) :=Z

1 0 `(t;x(t);x0(t))dt oul: [0;1]RnRn!Retx()2XouXest l'espace de BanachX:=C1([0;1];Rn) muni de la norme

kxk:= maxt2[0;1](jx(t)j+jx0(t)j). On s'interessera en particulier a la minimisation deJsurXet a caracteriser un

minimum. Denition 2.1.SoitXetYdeux espaces de Banach. La derivee directionnelle defau pointx2Xdans la directionh2Xest si elle existe la limite f

0(x;h) := limt#0f(x+th)f(x)t

Remarque 2.1.(i) Supposons quefadmette une derivee directionnelle enxdans la directionh. Alors on a f

0(x;th) =tf0(x;h)pourt >0i.e. la derivee directionnelle est positivement homogene.

(ii) On a aussi le developpement suivant:f(x+th) =f(x) +tf0(x;h) +o(t),t >0. Par exemplef(x) =jxjadmet enx= 0 une derivee directionnelle dans toute direction:f0(0;h) =jhj,h2R.

Denition 2.2.(i) La fonctionf:X!Yest dite G^ateaux-dierentiable enxsi la derivee directionnelle defau

pointxexiste pour touth2Xet sih7!f0(x)hest lineaire continue deXdansY. On note alorsDf(x)2 L(X;Y) sa derivee (au sens de G^ateaux) denie par:

Df(x)h=f0(x;h):

(ii) On dit quefest Frechet dierentiable enxsi elle est G^ateaux dierentiable enxet si f(x+h) =f(x) +Df(x)h+o(khkX):

On appelle alorsDf(x)la derivee au sens de Frechet defenx(appele egalement la dierentielle defenx). La

dierentielle enxest unique.

Remarque 2.2.Notons que sifest Frechet dierentiable enxalorsfest G^ateaux dierentiable enxavec la m^eme

derivee. 6

2.2. FONCTIONS SEMI-CONTINUE INF

ERIEUREMENT7

Propriete 2.1.Sifest Frechet dierentiable au pointxalorsfest continue au pointx.

La denition de \G^ateaux-dierentiable" ou \Frechet-dierentiable" depend du choix de la norme sur les espaces

consideres. Cependant, on peut montrer que pour deux normes equivalentes, on est conduit a la m^eme denition.

Remarque 2.3.(i) Soit la fonctionf:R2!Rdenie parf(x1;x2) := 1six1>0etx2=x21etf(x1;x2) = 0sinon.

Alorsfn'est pas continue en(0;0). De plusf0((0;0);h) = 0pour touth2R2, doncfest G^ateaux dierentiable en

(0;0). Commefn'est pas continue en(0;0)alorsfn'est pas Frechet dierentiable en(0;0).

(ii) Une fonction peut admettre des derivees directionnelles en un point sans ^etre Gateaux dierentiable en ce point.

Considerons la fonctionf:R2!Rdenie parf(x1;x2) =x2 1x

22+jx1jsi(x1;x2)6= (0;0)etf(0;0) = 0. Alors, on peut

montrer quef0((0;0);h)existe pour touth2R2maish7!f0(0;0)hn'est pas lineaire (en eet:f0((0;0);h) = 0si

h= (0;h2),h22Retf0((0;0);h) =jh1jsih= (h1;h2)avech16= 0). Denition 2.3.On dit quef:X!Rest de classeC1surXsifest Frechet dierentiable en tout point deXet six7!Df(x)est continue deXdansX, le dual topologique deX.

Dans la denition precedente,Df(x) est donc une application continue deXa valeur dans l'espace des formes

lineaires continues surX. Exercice 2.1.1) Montrer queA2Mn(R)7!A2est G^ateaux-dierentiable en tout pointA2Mn(R).quotesdbs_dbs7.pdfusesText_13

[PDF] cours doptimisation pour économistes

[PDF] cours optimisation sans contrainte

[PDF] resume cours optique geometrique

[PDF] cours de physique optique cours et exercices corrigés pdf

[PDF] examen corrigé optique ondulatoire

[PDF] résumé cours optique ondulatoire

[PDF] physique optique cours complet

[PDF] controle optique 1ere s

[PDF] orientation scolaire et professionnelle définition

[PDF] oxydoréduction cours bac pro

[PDF] programme daeu b physique

[PDF] programme daeu a

[PDF] cours physique daeu b pdf

[PDF] cours chimie daeu b

[PDF] la révolution et l'empire 4ème 2016

[PDF] [PDF] Cours dOptimisation numérique