Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Programmation math´ ematique SMA 5 UNIVERSITE MOULAY ISMAIL FACULTE DES SCIENCE

Programmation math´ ematique SMA 5 UNIVERSITE MOULAY ISMAIL FACULTE DES SCIENCES MEKNES SMA (S5) Programmation math´ ematique ————————— Note de cours 2018-2019 Said Kabbadj kabbajsaid63@yahoo.com 1 Pr. Said Kabbadj Programmation math´ ematique SMA 5 Table des mati` eres 1. Notions fondamentales 1.1 Introduction 1.1.1 Motivation et vocabulaire 1.1.2 Diﬀ´ erents types d’optimisation 1.2 Diﬀ´ erentiabilit´ e 1.2.1 Gradient et hessienne 1.2.2 Formules de Taylor 1.3 Convexit´ e 1.3.1 Ensembles convexes 1.3.2 Fonctions convexes 1.3.3 Caract´ erisation des fonctions convexes 1.4 Projection sur un convexe ferm´ e 1.5 Existence et unicit´ e d’un point de minimum 1.6 Conditions d’optimalit´ e 1.6.1 Conditions d’optimalit´ e du premier ordre 1.6.2 Conditions d’optimalit´ e du second ordre 2. Algorithmes de descente pour des probl` emes d’optimisation sans contraintes 2.1 Introduction 2.2 Vecteurs et facteurs de descente 2.3 G´ en´ eralit´ es sur les algorithmes de descente 2.4 Algorithmes de descente du gradient 2.4.1 Algorithme du gradient ` a pas ﬁxe 2.4.2 Algorithme du gradient ` a pas optimal 2.5 La m´ ethode des gradients conjugu´ es 3. Conditions d’optimalit´ e 3.1 Conditions d’optimalit´ e 3.2 Conditions d’optimalit´ e pour les probl` emes avec contraintes d’´ egalit´ es 3.3 Conditions d’optimalit´ e pour les probl` emes avec contraintes d’in´ egalit´ es 3.4 Conditions d’optimalit´ e pour les probl` emes avec contraintes d’´ egalit´ es et d’in´ egalit´ es 4. Probl` emes d’optimisation avec contraintes 4.1 Algorithmes du gradient ` a pas ﬁxe avec projection 4.2 M´ ethodes de dualit´ e 2 Pr. Said Kabbadj Programmation math´ ematique SMA 5 Chapitre 1 Notions fondamentales 1.1 Introduction 1.1.1 Motivation et vocabulaire : L’optimisation est une branche des math´ ematiques cherchant ` a mod´ eliser, ` a analyser et ` a r´ esoudre analytiquement ou num´ eriquement les probl` emes qui consistent ` a minimiser ou maximiser une fonction sur un ensemble . On appelle probl` eme d’optimisation tout probl` eme de la forme : (P) : ′′ Trouver x∗∈U tel que f(x∗) = min x∈U f(x)′′ . U ´ etant une partie d’un ensemble E , et f : E →R est une fonction donn´ ee. Le but de l’optimisation est de proposer des algorithmes permettant d’approcher les solutions x∗de (P) au sens o` u partant d’un vecteur initial x0 quelconque, on construit explici- tement une suite de vecteurs {xk}k∈N convergent vers une solution x∗. Le probl` eme d’optimisation est dit sans contraintes si U = E, et sous contraintes sinon . On dit que : • f est la fonction objectif ou crit` ere d’optimisation . • v = f(x∗) est la valeur optimale . • x∗est une solution optimale . • U est l’ensemble des solutions r´ ealisables ou admissibles . Dans ce cours on se placera toujours dans le cas o` u E = Rp (c’est ` a dire en dimension ﬁnie ). On note < ·, · > le produit scalaire canonique et ∥· ∥la norme euclidienne associ´ ee d´ eﬁnie par : 3 Pr. Said Kabbadj Programmation math´ ematique SMA 5 ∀x ∈Rp, ∥x∥= √< x, x > . Les m´ ethodes d´ evelopp´ ees dans ce cours permettent aussi de trouver les valeurs maxi- males de f, pour cela il suﬃt de remplacer f par -f , puisque : max x∈U f(x) = −min x∈U (−f(x)). Exemple 1.1 : Un probl` eme de production Une usine a besoin de n produits a1, .., an en quantit´ e x1, .., xn pour fabriquer un produit ﬁni b en quantit´ e h(x1, .., xn). Soit pi le prix unitaire du produit i et p le prix de vente du produit ﬁni. On d´ esire calculer la production optimale. Il s’agit donc de maximiser la fonction f(x) = ph(x1, .., xn) - i=n X i=1 pixi 1.1.2 Diﬀ´ erents types d’optimisation : 1. Optimisation lin´ eaire : • f est une fonction lin´ eaire f(x) = < c, x > • U est d´ eﬁni par des fonctions aﬃnes. 2. Optimisation quadratique . • f est une fonction quadratique : f(x) =1 2 < Ax, x > + < b, x > A est une matrice sym´ etrique sd´ eﬁnie positive • U est d´ eﬁni par des fonctions aﬃnes. 3. Optimisation convexe : f est une fonction convexe et U est un domaine convexe . 4. Optimisation diﬀ´ erentiable : f est une fonction diﬀ´ erentiable et les fonctions (contraintes) sont diﬀ´ erentiables. 5. Optimisation non diﬀ´ erentiable : f n’est pas diﬀ´ erentiable sur U . 1.2 Diﬀ´ erentiabilit´ e 1.2.1 Gradient et hessienne D´ eﬁnitions 1.2 Soit U ⊂Rp un ouvert et f : U →R 4 Pr. Said Kabbadj Programmation math´ ematique SMA 5 1. On dit que f est diﬀ´ erentiable au point x ∈U s’il existe un voisinage V de x dans U , une application lin´ eaire Lx : Rp →R et ε : V →R tels que : lim y ∈V →x ε(y −x) = 0 et ∀y ∈V , on a : f(y) = f(x) + Lx(y −x) + ∥y −x∥ε(y −x). Lx est la diﬀ´ erentielle de f en x et on la note d fx. 2. ∀x ∈U , ∀h ∈Rp . On note (s’il existe) ∂f ∂h(x) = lim t→0 f(x + th) −f(x) t = g′(0) avec g(t) = f(x + th) , et on l’appelle la d´ eriv´ ee directionnelle de f en x suivant la direction h. 3. ∀x ∈U ,∀i ∈{1, ..., p} . On note (s’il existe) ∂f ∂ei(x) = lim t→0 f(x + tei) −f(x) t = ∂f ∂xi (x) , et on l’appelle la d´ eriv´ ee partielle de f au point x de direction xi . 4. ∀x ∈U, on note (quand il existe) ∇f(x) = ( ∂f ∂x1(x), ........, ∂f ∂xp(x))T est le vecteur gradient de f en x. 5. f ∈Cm(U) si toutes les d´ eriv´ ees partielles jusque ` a l’ordre m existent et continues 6. ∀x ∈U , on note (quand il existe ) ∇2f(x) la matrice hessienne de f en x telle que : (∇2f(x))i,j = ∂f ∂xi∂xj (x) . Remarque 1.3 (a) ∂f ∂0 (x) = 0, ∀x (b) ∂f ∂xi(x) = ∂f ∂ei(x), ∀x Proposition 1.4 1 Si f est diﬀ´ erentiable en x , alors f est continue en x et admet en x une d´ eriv´ ee directionnelle suivant tout vecteur v ∈Rp de plus d fx(v) = ∂f ∂v (x). 5 Pr. Said Kabbadj Programmation math´ ematique SMA 5 2 Si f est diﬀ´ erentiable en x alors les n d´ eriv´ ees partielles de f en x existent et ∀h ∈Rp , d fx(h) =< ∇f(x), h >= p X i=1 ∂f ∂xi (x)hi 3 Soient U ouvert de Rp et V ouvert de R . Si f : U →R et g : V →R deux fonctions de classe C1 avec f(U) ⊂V alors g ◦f est de classe C1 et ∇(g ◦f)(x) = g′(f(x)) · ∇f(x) , ∀x ∈U 4 Si f ∈C2(U) alors la matrice hessienne est sym´ etrique. Proposition 1.5 Si f : U →R une fonction deux fois diﬀ´ erentiable alors ∀x ∈U, ∀h ∈Rp, ∇2f(x)h = ∇< ∇f(x), h > . Preuve. Pour i = 1, ...., , p ; ∂ ∂xi < ∇f(x), h >= ∂ ∂xi p X j=1 ∂f ∂xj (x)hj = p X j=1 ∂2f ∂xi∂xj (x)hj = (∇2f(x)h)i Exemples 1.6 Soit f : Rp →R (a) Si f(x) = c ∈R ( fonction constante) alors : ∇f = 0 et ∇2f = 0 (b) Si f(x) = < a, x > ( fonction lin´ eaire ) alors : ∇f = a et ∇2f = 0. ( ∂f ∂xi = ai ⇒∇f = a ⇒∇2f = 0.) Exercice 1.7 Soit f : Rp →R une fonction quadratique associ´ ee ` a la matrcice A ∈ Mp(R) d´ eﬁnie par : f(x) =< Ax, x >, ∀x ∈Rp Montrer que : 1) ∇f(x) = (A + AT)x , ∀x ∈Rp . 2) ∇2f(x) = A + AT , ∀x ∈Rp . 6 Pr. Said Kabbadj Programmation math´ ematique SMA 5 1.2.2 Formules de Taylor Soit U un ouvert de Rp , a ∈U , h ∈Rp et f : U →R tels que , [a, a + h] ⊂U . Proposition 1.8 : Si f ∈C1(U) alors : f(a + h) = f(a) + Z 1 0 < ∇f(a + th), h > dt. (1) (1) est la formule de Taylor ` a l’ordre 1 avec reste int´ egral f(a + h) = f(a)+ < ∇f(a), h > + ◦(∥h∥) (2) (2) est la formule de Taylor-Young ` a l’ordre 1. f(a + h) = f(a)+ < ∇f(a + θh), h >, avec θ ∈]0, 1[ (3) (3) est la formule de Taylor-Maclaurin ` a l’ordre 1 . Proposition 1.9 : Si f ∈C2(U) alors : f(a + h) = f(a)+ < ∇f(a), h > + Z 1 0 (1 −t) < ∇2f(a + th)h, h > dt. (4) (4) est la formule de uploads/Industriel/ programmation-mathematique.pdf