COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin
COURS OPTIMISATION. Cours en Master M1 SITN. Ionel Sorin CIUPERCA 4.2.3 Applications de la théorie du point selle à l'optimisation . . . . . . 51.
Cours-Optimisation.pdf
Jean-Baptiste Hiriart-Urruty Optimisation et analyse convexe (exercices cor- rigés). Cependant
Résumé dOptimisation
Résumé d'Optimisation. MI5 Master Pro 1`ere année 6 Optimisation avec contraintes ... Ceci un résumé des principaux résultats du cours d'optimisation.
COURS DOPTIMISATION [.2pc] ISIMA – F4 3ème année – Master
Dualité. Algorithmes. COURS D'OPTIMISATION. ISIMA – F4 3ème année – Master Recherche Maths. Jonas Koko. ISIMA. J. Koko. Cours d'Optimisation Convexe
Optimisation cours
Optimisation (MML1E31). Notes de cours. Master 1 Mathématiques et Modélisation (MM). 2017-2018. Bruno GALERNE. Bureau 812-F bruno.galerne@parisdescartes.fr
M1 MApI3 - UE OPTIMISATION Support de cours
cours ”Fondamentaux de la recherche opérationnelle” du Master 2 MApI3. Algorithmique de l'optimisation. Un algorithme associé au probl`eme (PX) consiste `a
Optimisation et programmation dynamique
Ces notes sont un support pour le cours. Optimisation et programmation dynamique du Master 1 de mathématiques appliquées de l'Université Paris Dauphine.
Cours Optimisation
Cours Optimisation. Cours destiné aux étudiants de première année Master TP 4 : Résolution d'un problème d'optimisation linéaire sans contraintes.
D03-MI-2015-Optimisation et Contrôle
Etablissement : Université Sétif 1 Intitulé du master : Optimisation et Contrôle Cours TD
Exercices sur le cours “Optimisation et programmation dynamique” 1
Exercices sur le cours. “Optimisation et programmation dynamique”. 2020-2021. Master mention Mathématiques appliquées 1`ere année. Université Paris Dauphine.
[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] Cours en Master M1 SITN
Pour décrire (et éventuellement résoudre) un problème d'optimisation nous utilisons la modélisation mathématique La démarche de modélisation comporte 3
[PDF] Manuel de Cours Optimisation - univ-ustodz
Ce manuscrit traite les notions de base de l'optimisation et s'adresse essen- tiellement au étudiants de Master 1 spécialité Automatique et Informatique
[PDF] Cours Optimisationpdf
Département de Génie Mécanique Cours Optimisation Cours destiné aux étudiants de première année Master Filière : Génie Mécanique Option : Construction
[PDF] Résumé du cours doptimisation
13 sept 2005 · Dans ce cours tous les résultats sont établis sur les problèmes de minimisation 1 1 Théorème de Weierstrass Théorème 1 1 Si K est un compact
[PDF] Cours doptimisation ENSAI Rennes
11 déc 2019 · dessins en cours 1 2 1 Contraintes d'égalité et d'inégalité Si K = ? il s'agit d'un probl`eme d'optimisation sans contrainte L'en-
[PDF] Introduction `a loptimisation
2 Page 3 Nous étudierons dans ce cours uniquement des probl`emes d'optimisation non linéaire 1 2 2 Optimisation non linéaire On distingue trois types de
[PDF] M1 MApI3 - UE OPTIMISATION Support de cours
cours ”Fondamentaux de la recherche opérationnelle” du Master 2 MApI3 Algorithmique de l'optimisation Un algorithme associé au probl`eme (PX) consiste `a
[PDF] Résumé dOptimisation
Résumé d'Optimisation MI5 Master Pro 1`ere année 6 Optimisation avec contraintes Ceci un résumé des principaux résultats du cours d'optimisation
[PDF] Cours doptimisation
- Représentation 3D (cf pdf ) - Courbes de niveau : La courbe de niveau ? d'une fonction f est défini par l'ensemble des points (
Quelles sont les méthodes d'optimisation ?
La fonction à optimiser s'écrit sous la forme z=ax+by+c, z = a x + b y + c , où x et y sont les variables et où z représente la quantité qu'on cherche à maximiser ou à minimiser.Comment calculer l'optimisation ?
Théorème 2.1 Un fonction f est convexe si et seulement si, pour tout (x, y) ? (dom(f))2 et ? ? 0 tels que y + ?(y ? x) ? dom(f), f satisfait : f(y + ?(y ? x)) ? f(y) + ?(f(y) ? f(x)).
![COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin](https://pdfprof.com/Listes/17/48729-17cours-optim-M1-sitn.pdf.pdf.jpg)
COURS OPTIMISATION
Cours en Master M1 SITN
Ionel Sorin CIUPERCA
1Table des matières
1 Introduction 4
2 Quelques rappels de calcul différentiel, analyse convexe et extremum 5
2.1 Rappel calcul différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Quelques Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Quelques rappels sur le calcul différentiel . . . . . . . . . . . . . . . 6
2.1.3 Rappel formules de Taylor . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.4 Quelque rappels sur le matrices carrées réelles . . . . . . . . . . . . 11
2.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Fonctions convexes, strictement convexes, fortement convexes . . . . 11
2.2.2 Exemples des fonctions convexes, strictement convexes et fortement
convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.3 Fonctions coercives . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Conditions nécéssaires et suffisantes de minimum . . . . . . . . . . . . . . 17
2.4 Existence et unicité d"un point de minimum . . . . . . . . . . . . . . . . . 21
3 Optimisation sans contraintes 23
3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.1 Description de la méthode . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.2 Cas particulier des fonctions quadratiques . . . . . . . . . . . . . . 27
3.2 Méthodes de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.1 Méthodes de gradient à pas optimal . . . . . . . . . . . . . . . . . . 29
3.2.2 Autres méthodes du type gradient . . . . . . . . . . . . . . . . . . . 30
3.3 La méthode des gradients conjugués . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 Le cas quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.2 Cas d"une fonctionJquelconque . . . . . . . . . . . . . . . . . . . 38
4 Optimisation avec contraintes 39
4.1 Rappel sur les multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . . 40
4.2 Optimisation sous contraintes d"inégalités . . . . . . . . . . . . . . . . . . . 41
4.2.1 Conditions d"optimalité de premier ordre : multiplicateurs de Karush-
Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2.2 Théorie générale du point selle . . . . . . . . . . . . . . . . . . . . . 49
24.2.3 Applications de la théorie du point selle à l"optimisation . . . . . . 51
4.2.4 Le cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Algorithmes de minimisation avec contraintes . . . . . . . . . . . . . . . . 53
4.3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.2 Méthodes de projection . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.3 Méthodes de pénalisation exterieure . . . . . . . . . . . . . . . . . . 59
4.3.4 Méthode d"Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3Chapitre 1
Introduction
En généraloptimisersignifie le fait de chercher une configuration optimale d"un sys-tème, c"est à dire, chercher la meilleure configuration parmi tous les configurations possibles
du système et ceci, par rapport à un critère donné. Pour décrire (et éventuellement résoudre) un problème d"optimisation nous utilisons la modélisation mathématique. La démarche de modélisation comporte 3 étapes : Etape 1.Choisir lesvariables de décision, qui sont les composantes du système sur lesquelles on peut agir. On supposera dans ce cours qu"il y a un nombre finit notén2INde variables de décision, chacune de ces variables étant un nombre réel. Alors les variables
de décision seront représentés par un vecteurx= (x1;x2;xn)T2IRn(vecteur colonne). Etape 2.Décrirel"étatdu système, étant donnée une configuration des variables de décision. Ceci revient mathématiquement à se donner une fonctionJ:IRn!IRqui s"appellefonction objectifoufonction coûtet que nous voulons rendre la plus petite possible ou la plus grande possible. Etape 3.Décrire lescontraintesque les variables de décision satisfont. Ceci revient à définir un ensemble de contraintesUIRnet imposer d"avoirx2U. Pour résumer on peut dire que pour décrire un problème d"optimisation on se donne1. Une fonctionJ:IRn7!IR(fonction coût)
2. Un ensembleUIRn(ensemble des contraintes)
On cherche à minimiserJsurU, c"est à dire, on cherchex2Utel queJ(x) = minx2UJ(x)
ou équivalentJ(x)J(x);8x2U:
Motivation et exemples pratiques :en classe
4Chapitre 2
Quelques rappels de calcul différentiel,
analyse convexe et extremum2.1 Rappel calcul différentiel
2.1.1 Quelques Notations
1. Pour toutn2IN;IRndésigne l"espaceeuclidienIRIRIR( "produitnfois").
En général un vecteurx2IRnsera notéx= (x1;x2;xn)T(vecteur colonne).2. On notee1;e2;enles éléments de labase canoniquedeIRn, oùeiest le vecteur
deIRndonné par : (ei)j=ij=0sij6=i1sij=i;8i;j= 1;2n(2.1)
(ij=symboles deKronecker).3. Pour tousx;y2IRnon note par< x;y >2IRleproduit scalairedexety, qui
est donné par < x;y >=nX i=1x iyi: Deux vecteursx;y2IRnsontorthogonaux(on noterax?y) si< x;y >= 0.4. Pour toutx2IRnon note parkxk 0lanorme euclidiennedex, donnée par
kxk=p< x;x >=v uutn X i=1x 2i: Rappellons lespropriétés d"une norme(donc aussi de la norme euclidienne) : i)kxk=jjkxk 82IR;8x2IRn ii)kx+yk kxk+kyk 8x;y2IRn iii)k0k= 0etkxk>0six2IRn f0g. 55. Pour tousx2IRnetr >0on notera parB(x;r)laboule ouvertedu centrexet
rayonr, donnée parB(x;r) =fy2IRn;kyxk< rg:
6. Si x(k) k2INest une suite dansIRnetxest un élément deIRnon dit quex(k) convergeversx(notéex(k)!x) sikx(k)xk !0. Rappellons que nous avons :x(k)!xsi et seulement six(k) i!xienIRoùx(k) i(respectivementxi) est lai-ème composante dex(k)(respectivementx).7. SoitUIRn.
- On définitl"intérieurdeUcomme l"ensemble des élémentsx2Upour lesquels il exister >0tel queB(x;r)U. - On dit queUestouvertsi8x2U9r >0tel queB(x;r)U. - On dit queUestfermési pour tout suitefx(k)g Utel quex(k)!x2IRnon ax2U.8. Sia;b2IRnon note[a;b]le sous-ensemble deIRndonné par
[a;b] =fa+t(ba)(1t)a+tb; t2[0;1]g: L"ensemble[a;b]est aussi appelléle segmentreliantaàb.Remarques :
[a;b] = [b;a](Exo!) Sia;b2IRaveca < bon retrouve la notation[a;b]pour l"intervalle des nombres x2IRtels queaxb.9. Rappellons aussi l"inégalité de Cauchy-Schwarz :
j< x; y >j kxk kyk 8x;y2IRn:2.1.2 Quelques rappels sur le calcul différentiel
On considère dans cette partiemetndeux nombres deN(très souvent dans ce cours on auram= 1).1. SoitUun sous-ensemble deIRnetf:U7!IRm.
On dit quefestcontinueenx2Usif(x(k))!f(x)pour toute suitex(k)U telle quex(k)!x. On dit quefest continue surUsifest continue en tout pointx2U. Remarque :Sif= (f1;f2;fm)avecf1;f2;fm:U!IRalorsfest continu enx2Usi et seulement sif1;f2;fmsont continues enx.Pour tous les poins suivants on va supposer que
est un ouvert de IRnetfest une fonctionf: !IRm. 62. Pour toutx2
eth2IRnon note (quand9) @f@h (x) = limt7!01t [f(x+th)f(x)] (c"est ladérivée directionnelledefenxdans la directionh).Remarques :
i)@f@0(x) = 0: ii)Sif= (f1;f2;fn)T2IRnavecf1;f2;fm: !IRalors @f@h (x) =@f1@h (x);@f2@h (x);@fm@h (x) T3. Pour toutx2
et touti2 f1;2;;ngon note (quand9) @f@x i(x) =@f@e i(x) = limt7!01t [f(x+tei)f(x)] (c"est ladérivée partielledefenxpar rapport à la variablexi.)En particulier, sin= 1on notef0(x) =@f@x
1(x) = limt!01t
[f(x+t)f(x)] = lim y!x1yx[f(y)f(x)]4. Pour toutx2
on note (quand9)Jf(x) =lamatrice Jacobiennedefenxqui est un élément deMm;n(IR)définie par (Jf(x))ij=@fi@x j(x)2IR8i= 1;m;8j= 1;n: Legradientdefenxest défini comme la transposée de la matrice Jacoblenne de fenx: rf(x) = (Jf(x))T2 Mn;m(IR): Remarque importante :Dans le cas particulierm= 1(doncf: !IR) alors en considérant tout élément deMn;1comme un vector colonne deIRn, on va dire que rf(x)est le vecteur colonne rf(x) =@f@x 1@f@x2;@f@x
n T 2IRn:Rappellons la formule :
@f@h (x) =8h2IRn:
5. Sif:
!IR(icim= 1) on dit qu"un pointx2 est unpoint critiquepour la fonctionfsirf(x) = 0. 76. Pour toutx2
eti;j2 f1;2;ngon note (quand9) 2f@x i@xj(x) =@@x i @f@x j (x)2IRm dérivée partielle à l"ordre 2.Notation :pouri=jon écrira@2f@
2xi(x)à la place de@2f@x
i@xi(x).7. Dans le casm= 1on note pour toutx2
(quand9)r2f(x) =la matrice carrée 2 M n(IR)donnée par r2f(x) ij=@2f@x i@xj(x);8i;j= 1;2;n: (r2f(x)s"appelle aussila matrice Hessiennedefenx).8. On dit quefest de classeCpsur
(on noteraf2Cp( )) pourp= 1oup= 2 si les dérivées partielles desfjusqu"à l"ordrepexistent et sont continues sur . Par extension on dit quefest de classeC0sur sifest continue sur9. On a le Théorème de Schwarz : sif2C2(
)alors 2f@x i@xj(x) =@2f@x j@xi(x)8x2 ;8i;j= 1;n (c"est à dire, la matricer2f(x)est symmétrique).10. (Lien entrer;Jfetr2) : Sif:
!IRest de classeC2alors r2f(x) =Jrf(x) =rJf(x)8x2
(la matrice Hessienne defest le Jacobien du gradient defou le gradient de laJacobienne def).
11. (Composition) Soient
IRn; UIRmavec
;Uouvertsf: !IRm; g:U! IR pavecp2INetf( )U. Considérons la fonction composéegf: !IRp. i)Sifetgsont continues alorsgfest continue. ii)Sifetgsont de classeC1alorsgfest de classeC1et on a l"égalité matricielle J gf(x) =Jg(f(x))Jf(x)8x2Conséquences :
i)Sim=p= 1alors r(gf)(x) =g0(f(x))rf(x): i)Sin=p= 1alors (gf)0(x) =Proposition 2.1.Nous avons
r2f(x)h=r8x2
;8h2IRn: où le premier gradient dans le membre de droite de l"égalité est considéré par rapport à la
variablex.Démonstration.On a :
@@x i1. Sif:IRn!IRmest une fonctionconstantealorsrf= 0etJf= 0. On a aussi
évidementr2f= 0dans le casm= 1.
2. Soitf:IRn!IRmdéfinie par
f(x) =Ax8x2IRn oùA2 Mm;n(IR)est une matrice donné (c"est à dire,fest une fonctionlinéaire).Il est facile de voir qu"on a
J f(x) =A8x2IRn (la matrice Jacobienne est constante). Dans la cas particulierm= 1une fonction linéaire générale peut être écrite sous la forme f(x) =< a; x >8x2IRn oùa2IRnest un vecteur donné. Il est clair alors que rf=a et r2f= 0:
3. Soitf:IRn!IRdonnée par
f(x) =< Ax; x >8x2IRn; oùA2 Mn(IR)est un matrice carrée, réelle, de taillen(c"est à dire,fest laforme quadratiqueassociée à la matriceA). Alors pour unp2 f1;2;ngfixé, on peutécrire
f(x) =nX i;j=1A ijxixj=Appx2p+nX j=1;j6=pA pjxpxj+nX i=1;i6=pA ipxixp+nX i;j=1;i6=p;j6=pA ijxixj 9 ce qui nous donne @f@x p= 2Appxp+nX j=1;j6=pA pjxj+nX i=1;i6=pA ipxi=nX j=1A pjxj+nX i=1A ipxi= (Ax)p+(ATx)p:Nous avons donc obtenu :
rf(x) = (A+AT)x;8x2IRn:En utilisant la formuler2f=Jrfon déduit
r2f(x) =A+AT;8x2IRn
(donc la hessienne defest constante).quotesdbs_dbs32.pdfusesText_38[PDF] exercices corrigés doptimisation pdf
[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