Informatique & Math´ematiques Appliqu´ees Programmation Math´ematique et Application J. Gergaud & D. Ruiz 17 avril 2008 Table des mati`eres 1 D´efinition du probl`eme 3 1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Cas continu et de dimension finie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Probl`emes en nombres entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Probl`eme en dimension infinie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Probl`eme d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1 D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 Condition n´ecessaire, condition suffisante : cas sans contraintes et cas convexe 17 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 Convexit´e des fonctionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1 Ensembles convexes - fonctionnelles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Convexit´e et d´eriv´ee premi`ere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 Convexit´e et d´eriv´ee seconde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3 Extr´emas de fonctionnelles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 Prise en compte des d´eriv´ees premi`eres. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Prise en compte des d´eriv´ees secondes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3 Prise en compte de la convexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4 Existence d’un minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 i Introduction Optimiser, c’est rechercher parmi un ensemble C de choix possibles le meilleur (s’il existe!). Si f est une application d’un ensemble E dans F. On note le probl`eme (cid:26) minf(x) (P) x∈C ⊂E. Il faut donc pour cela pouvoir comparer 2 choix et donc avoir une structure d’ordre sur l’ensemble F. On prendra toujours F =R. Suivant les domaines d’applications : • E s’appelle l’ensemble des strat´egies, des ´etats, des param`etres, l’espace; • C est l’ensemble des contraintes; • f est la fonction couˆt, ´economique ou le crit`ere, l’objectif. Une fois le probl`eme bien d´efini, il se pose deux questions. La premi`ere est de savoir si (P) admet une solution. Si la r´eponse est positive, il nous faut trouver la ou les solutions. Suivant la nature de l’ensemble E les r´eponses sont plus ou moins faciles. Si E est fini, l’existence de solution est´evidente, mais le calcul est difficile si le nombre d’´el´ements est grand. Par contre si E = Rn ou est de dimension infinie la question de l’existence de solution est moins triviale, mais si les fonctions sont d´erivables il est ”plus” facile de calculer la solution. 1 2 TABLE DES MATIE`RES Chapitre 1 D´efinition du probl`eme 1 Exemples 1.1 Cas continu et de dimension finie Exemple 1.1.1. [Principe de Fermat] Pierre de Fermat est un juriste et math´ematicien fran¸cais, surnomm´e « le Fig. 1.1 – Pierre de Fermat, n´e vers 1601, `a Beaumont-de-Lomagne, pr`es de Montauban, et mort le 12 janvier 1665 `a Castres. prince des amateurs ». On lui doit entre autre le principe de Fermat qui dit que la lumi`ere se propage d’un point `a un autre sur des trajectoires telles que la dur´ee du parcours soit minimale. Il imagina aussi pour la solution des probl`emes, une m´ethode, dite de maximis et minimis, qui le fait regarder comme le premier inventeur du calcul diff´erentiel dont il est un pr´ecurseur : il est le premier `a utiliser la formule (sinon le concept) du nombre d´eriv´e!∗ On s’int´eresse ici `a la trajectoire d’un rayon lumineux d’un point A(0,a) vers un point B(k,b) situ´es dans deux milieux homog`enes diff´erents (cf. la figure 1.2). Nous allons grˆace au principe de Fermat retrouver la loi de la r´efraction. On suppose pour cela que la trajectoire d’un rayon lumineux dans un milieu homog`ene est un segment de droite (ce qui peut aussi se d´emontrer grˆace au principe de Fermat et `a l’optimisation!). On note P, de coordonn´ees (x,0), le point d’impact du rayon lumineux sur la surface du changement de milieu et c et c les vitesses de la lumi`ere dans l’air et dans l’eau. Le temps de parcours entre les point A et B est donc 1 2 1 p 1 p T(x)= a2+x2+ b2+(k−x)2. c c 1 2 Le probl`eme est alors ici de trouver le point P (c’est-`a-dire x∗ ∈R) tel que (cid:26) Min f(x) T(x∗)≤T(x)∀x∈R⇐⇒(P) x∈R. ∗http://fr.wikipedia.org/wiki/Pierre de Fermat. 3 4 CHAPITRE 1. DE´FINITION DU PROBLE`ME 3 A(0,a) air 2 1 α1 P(x,0) 0 −1 α 2 eau B(k,b) −2 −3 −1 0 1 2 3 4 5 6 7 Fig. 1.2 – Principe de Fermat. On peut ici tracer cette fonction (cf. la figure 1.3). 6.5 6 5.5 T(x) 5 4.5 4 0 1 2 3 4 5 6 7 x Fig. 1.3 – Fonction T. Une condition n´ecessaire de solution de (P) est T0(x)=0 (cf. la figure 1.3). Ce qui donne ici x −(k−x) T0(x) = √ + =0 p c a2+x2 c b2+(k−x)2 1 2 x (k−x) ⇐⇒ √ = p c a2+x2 c b2+(k−x)2 1 2 sinα sinα ⇐⇒ 1 = 2 c c 1 2 ⇐⇒ n sinα =n sinα . 1 1 2 2 Remarque 1.1.2. Nous retrouvons dans ce cas les lois de Descartes† ou de Snell. †Associer les noms de Fermat et Descartes est surprenant pour qui connaˆıt les confrontations scientifiques virulentes qui les op- pos`erent.Les´etudiantsint´eress´espeuventvoirlavid´eo([3])ou` serendreaumus´eePierredeFermatdeBeaumontdeLomagne,ville nataledeP.deFermatpr`esdeToulouse. 1. EXEMPLES 5 Remarque 1.1.3. La condition T0(x) = 0 n’est qu’une condition n´ecessaire, en effet si nous consid´erons la fonctionnelle r´eelle f(x)=x3 nous avons f0(0)=0 mais 0 n’est pas un minimum de f (1.4). 8 6 4 2 f(x) 0 −2 −4 −6 −8 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 x Fig. 1.4 – f0(0)=0 et 0 n’est pas un minimum. Exemple 1.1.4. Un condensateur charg´e `a une tension de U volts se d´echarge sur une r´esistance. On mesure la 0 tension U entre les armatures du condensateur toutes les secondes pendant un intervalle de temps de 10 secondes. Les r´esultats des mesures sont donn´ees dans la table (1.1). t U t U i i i i 0 100 6 15 1 75 7 10 2 55 8 10 3 40 9 5 4 30 10 5 5 20 Tab. 1.1 – Donn´ees. Th´eoriquement, la tension en fonction du temps s’´ecrit U(t)=Ae−αt. Ond´esireiciestimerlesvaleursdesconstantesAetα.Notrebutestdoncdetrouverlesvaleursdecesconstantes pourquecettefonctionU(t)”colle”aumieux`anosdonn´ees.Siondonnedesvaleurs`acesconstantes,nouspouvons calculer les quantit´es appel´ees r´esidus (Fig. 1.5) r (A,α)=U −U(t )=U −Ae−αti. i i i i Par suite nous pouvons calculer la quantit´e n 1X f(A,α)= (U −Ae−αti)2. 2 i i=1 Cette quantit´e est la somme des carr´es des longueurs des r´esidus. Pluscettequantit´eserafaible,plusnotrecourbeseraprochedenospointsexp´erimentaux.Estimerlesparam`etres A et α par les moindres carr´es, c’est rechercher la valeur solution du probl`eme d’optimisation suivant : (P)(cid:26) Minf(A,α)= 12Pni=1(Ui−Ae−αti)2 (A,α)∈R2. 6 CHAPITRE 1. DE´FINITION DU PROBLE`ME 110 100 90 80 ← r1 70 ← r 2 60 ← r 50 3 ← r 40 4 ← r 5 30 ← r 6 ← r 20 7 ← r8 ← r9 ← r10 ← r11 10 0 −2 0 2 4 6 8 10 12 Fig. 1.5 – Crit`eres des moindres carr´es. Attention dans le probl`eme (P) ci-dessus, les instants t et les valeurs U sont connus. Ce sont les valeurs des i i param`etres que l’on cherche. Remarque 1.1.5. • Dans l’exemple pr´ec´edent on peut aussi ´ecrire : f(β)= 1 kr(β)k2 ou` 2   r (β) 1 β =(cid:0)A α(cid:1), r(β)= ... ,ri(β)=Ui−Ae−αti et ||.|| est la norme euclidienne. r (β) n • Minimiser f(β) est ´equivalent `a minimiser αf(β) avec α>0. Le terme 1 est mis ici afin de ne pas avoir le 2 terme 2 lorsque l’on d´erive la fonction f(β). • On peut aussi prendre comme crit`ere : – f(β)=||r(β)|| =Pn |r (β)|; 1 i=1 i – f(β)=||r(β)|| =Max |r (β)|. ∞ i=1,...,n i Exemple1.1.6(Mod`eledeKaplan). Ond´esire´etudierladiffusiond’unedroguedansunorganed’uncorpsdonn´e. La drogue est inject´ee par intraveineuse dans le sang `a l’instant t = 0. On mod´elise le syst`eme par un mod`ele `a 0 compartiments (cf. la figure 1.6). k1 - Sang y (t) Organe y (t) 1 2 (cid:27) k3 k 2 ? Fig. 1.6 – Mod`ele par compartiments. 1. EXEMPLES 7 Les concentrations dans le sang, mesur´ees `a diff´erents instants, sont donn´ees `a la table 1.2. t y t y i i1 i i1 0.25 215.6 3.00 101.2 0.50 189.2 4.00 88.0 0.75 176.0 6.00 61.6 1.00 162.8 12.00 22.0 1.50 138.6 24.00 4.4 2.00 121.0 48.00 0.0 Tab. 1.2 – Donn´ees pour l’exemple de Kaplan. Le syst`eme d’´equations diff´erentielles d´ecrivant le mod`ele est alors  dy  ddyt1 =y˙1(t)=−(k1+k2)y1(t)+k3y2(t) (EDO) 2 =y˙ (t)=k y (t)−k y (t) dt 2 1 1 3 2  yy1((00))==c00. 2 On d´esire estimer les param`etres c ,k ,k et k par les moindres carr´es. Posons β =(c ,k ,k ,k ), alors pour 0 1 2 3 0 1 2 3 toute valeur de β, on peut int´egrer le syst`eme d’´equations diff´erentielles ordinaires `a condition initiale (EDO). Notons (y (tβ),y (tβ)) cette solution. Par suite on peut calculer les n r´esidus 1 2 r (β)=y −y (t β). i i1 1 i Ces r´esidus sont visualis´es sur la figure 1.7. Nous estimerons alors le param`etre β en r´esolvant le probl`eme d’opti- misation aux moindres carr´es (cid:26) Minf(β)= 1Pn r2(β)= 1||r(β)||2 (P) 2 i=1 i 2 β ∈R4. 250 200 ← r 1 ← r 150 ← r2 y(t)1100 ←←← r 34r 5r 50 ←←6 r7 r←8 r 9 0 ← r10 ← r ← r 11 12 0 5 10 15 20 25 30 35 40 45 50 t 80 60 y(t)240 20 0 0 5 10 15 20 25 30 35 40 45 50 t Fig. 1.7 – Crit`ere des moindres carr´es pour le mod`ele de Kaplan. 8 CHAPITRE 1. DE´FINITION DU PROBLE`ME Exemple 1.1.7. On veut mesurer la liaison entre 2 g`enes dominants, l’un contrˆolant la couleur d’une fleur, rouge (R) est dominant sur blanc (b), et l’autre la taille, grand (G) est dominant sur petit (p). Dans la descendance F , 2 issu de deux populations homozygotes de ph´enotype [RG] et [bp], on a ´etudi´e n = 3839 plantes. On a obtenu les r´esultats de la table 1.3. Ph´enotypes [RG] [Rp] [bG] [bp] Effectifs observ´es 1997 906 904 32 Tab. 1.3 – Donn´ees de Sir R.A. Fisher. Leprobl`emeestd’estimer,`apartirdecesdonn´eesletauxderecombinaisonr.IcilapopulationF esth´et´erozygote 1 de g´enotype Rb,Gp. Nous avons donc les probabilit´es de la table 1.4 pour les diff´erents gam`etes possibles et les diff´erents croisements possibles. : RG bp Rp bG ♀ ♂ 1(1−r) 1(1−r) 1r 1r 2 2 2 2 RG [RG] [RG] [RG] [RG] 1(1−r) 1(1−r)2 1(1−r)2 1r(1−r) 1r(1−r) 2 4 4 4 4 bp [RG] [bp] [Rp] [bG] 1(1−r) 1(1−r)2 1(1−r)2 1r(1−r) 1r(1−r) 2 4 4 4 4 Rp [RG] [Rp] [Rp] [RG] 1r 1r(1−r) 1r(1−r) 1r2 1r2 2 4 4 4 4 bG [RG] [bG] [RG] [bG] 1r 1r(1−r) 1r(1−r) 1r2 1r2 2 4 4 4 4 Tab. 1.4 – Probabilit´es pour la descendance F . 2 Par suite nous avons dans la population F la loi suivante pour la variable al´eatoire ph´enotype X 2 X :F −→ {[RG],[Rp],[bG],[bp]} 2 1 plante 7−→ son ph´enotype, 1 2+θ P(X =[RG]) = (3−2r+r2)= 4 4 1 1−θ P(X =[Rp]) = (2r−r2)= 4 4 1 1−θ P(X =[bG]) = (2r−r2)= 4 4 1 θ P(X =[bp]) = (1−r)2 = 4 4 ou` θ =(1−r)2 ∈[1;1]. 4 D´efinissons maintenant le vecteur al´eatoire de dimension 4 (A,B,C,D):Fn −→ R4 2 (nb de plantes de ph´enotypes [RG], nb de plantes de ph´enotypes [Rp], n plantes 7−→ nb de plantes de ph´enotypes [bG], nb de plantes de ph´enotypes [bp]). On suppose la population F de taille infinie, donc la loi de ce vecteur al´eatoire est une loi multinomiale 2 L(a,b,c,d;θ) = P((A,B,C,D)=(a,b,c,d)) n! = P(X =[RG])aP(X =[Rp])bP(X)[bG])cP(X =[bp])d a!b!c!d! n! (cid:18)2+θ(cid:19)a(cid:18)1−θ(cid:19)b+c(cid:18)θ(cid:19)d = . a!b!c!d! 4 4 4