Remerciez-le!

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

Cours d’optimisation M1 (AS et AII) N. DJEGHALI Département Automatique UMMTO,

Cours d’optimisation M1 (AS et AII) N. DJEGHALI Département Automatique UMMTO, 2021/2022 djeghalinadial2csp@gmail.com Chapitre 1. Rappels mathématiques 1.1 Définition d’un problème d’optimisation D’un point de vue mathématique, l’optimisation consiste à rechercher le minimum ou le maximum d’une fonction avec ou sans contraintes. Un problème d’optimisation avec contraintes est défini comme suit : a) Problème de minimisation avec contraintes (recherche du minimum d’une fonction) n R x ), x ( f Min ∈ Sous les contraintes : m ,..., 1 i , 0 ) x ( g i = = (Contraintes d’égalité) p ,..., 1 j , 0 ) x ( h j = ≥ (Contraintes d’inégalité) Avec : Min f(x) signifie le minimum de f(x). On dit que l’on cherche à minimiser la fonction f. Exemple 1.1 2 1x x Min Sous les contraintes : 0 1 x x 2 1 = + + 0 x 2 x 2 1 ≥ + b) Problème de maximisation avec contraintes (recherche du maximum d’une fonction) Un problème de maximisation avec contraintes est défini comme suit : n R x ), x ( f Max ∈ Sous les contraintes : m ,..., 1 i , 0 ) x ( g i = = p ,..., 1 j , 0 ) x ( h j = ≥ Avec : Max f(x) signifie le maximum de f(x). On dit que l’on cherche à maximiser la fonction f. Dans les problèmes d’optimisation Pc1 et Pc2, la fonction f(x) définie de D dans R (i.e., ) R D : f → porte divers noms : fonction de coût, fonction objectif ou critère d’optimisation. Pc2 : Pc1 : Chapitre 1. Rappels mathématiques N. DJEGHALI 2 . R D ) x ,......., x , x ( x n n 2 1 ⊂ ∈ = Les variables n 2 1 x ,......., x , x sont appelées variables de décision. D est appelé l’ensemble ou domaine admissible, défini par l’ensemble des contraintes comme suit: { } p ,..., 1 j , 0 ) x ( h et m ,...., 1 i , 0 ) x ( g / R x D j i n = ≥ = = ∈ = . Remarque 1.1 : Les problèmes Pc1 et Pc2 peuvent être écrits sous les formes simplifiées P’ c1 et P’ c2 suivantes : ) x ( f Min ) x ( f Max n R D x ⊂ ∈ n R D x ⊂ ∈ Remarque 1.2 : En absence de contraintes p ,..., 1 j , 0 ) x ( h et m ,...., 1 i , 0 ) x ( g j i = ≥ = = , les problèmes Pc1 et Pc2 deviennent : ) x ( f Min Max f(x) n R x ∈ n R x ∈ Dans ce cas, P1 et P2 sont respectivement des problèmes de minimisation et de maximisation sans contraintes. Remarque 1.3 : Max f(x)= - Min (-f(x)) et Min f(x)= - Max (-f(x)) Ainsi la recherche d’un maximum peut se ramener à la recherche d’un minimum et vice versa. P’ c1 : P1: P2: P’ c2 : f(x) -f(x) x Min f(x) Max -f(x) Chapitre 1. Rappels mathématiques N. DJEGHALI 3 1.2 Convexité a) Ensemble convexe : un ensemble n R D ⊂ est dit convexe si pour tout couple D ) x , x ( 2 1 ∈ et ] 1 0 [ ∈ α ∀ , on a : D x ) 1 ( x x 2 1 ∈ α − + α = Cette définition peut être interprétée en disant que le segment reliant 2 1 x et x doit être dans D. Exemples d’ensembles convexes : Exemples d’ensembles non convexes : b) Fonction convexe : une fonction n R D , R D : f ⊂ → est convexe ssi : D x , x 2 1 ∈ ∀ , ] 1 0 [ ∈ α ∀ , ) x ( f ) 1 ( ) x ( f ) x ) 1 ( x ( f 2 1 2 1 α − + α ≤ α − + α ) x ( f 2 ) x ( f ) x ( f ) 1 ( ) x ( f 1 2 1 α − + α ) x ) 1 ( x ( f 2 1 α − + α x x x ) 1 ( x x 2 2 1 1 α − + α Fonction convexe x1 x2 D x x1 x2 x D D D Chapitre 1. Rappels mathématiques N. DJEGHALI 4 ) x ) 1 ( x ( f 2 1 α − + α ) x ( f ) x ( f ) 1 ( ) x ( f ) x ( f 1 2 1 2 α − + α x x x ) 1 ( x x 2 2 1 1 α − + α Fonction non convexe On dit que f est strictement convexe dans D ssi : D x , x 2 1 ∈ ∀ , ] 1 0 [ ∈ α ∀ , ) x ( f ) 1 ( ) x ( f ) x ) 1 ( x ( f 2 1 2 1 α − + α < α − + α c) Fonction concave : Une fonction est concave si –f est convexe. La définition d’une fonction et ensemble concave se fait en inversant les inégalités dans les définitions précédentes. Fonction concave f(x) x Chapitre 1. Rappels mathématiques N. DJEGHALI 5 1.3 Définitions Soit le problème d’optimisation suivant: n R x ), x ( f Min ou Max ∈ s.c : m ,..., 1 i , 0 ) x ( g i = = p ,..., 1 j , 0 ) x ( h j = ≥ Définition 1.1 : Tout vecteur x vérifiant l’ensemble des contraintes (i.e., D x ∈ ) est appelé solution admissible ou réalisable du problème d’optimisation. Définition 1.2 : Un optimum ou extremum d’une fonction f est soit un maximum soit un minimum, c'est-à-dire la valeur la plus haute ou la plus faible que prend la fonction sur son ensemble de définition D. Cet optimum est donné par f(x*). f(x*)=Min f(x) dans le cas d’un problème de minimisation ⇒ f(x*) : Minimum. f(x*)=Max f(x) dans le cas d’un problème de maximisation ⇒ f(x*) : Maximum. Définition 1.3 : Le point x* où la fonction f possède un minimum (resp. maximum) est dit un point de minimum ou minimiseur (resp. un point de maximum ou maximiseur). x* est aussi appelé solution optimale du problème d’optimisation. f(x) ) * x ( f imum min ) * x ( f imum max 2 1 ← ← x * x * x 2 1 Point de maximum Point de minimum Chapitre 1. Rappels mathématiques N. DJEGHALI 6 1.4 Minima et maxima d’une fonction Soit f une fonction de n R D ⊂ dans R ( ) R R D : f n → ⊂ . a) Minimum ou maximum local : f admet un minimum (resp. maximum) local (ou relatif) en D * x ∈ , si et seulement s’il existe un voisinage *) x ( Vε de x*, tel que : ) x ( f *) x ( f *), x ( V x ≤ ∈ ∀ ε (resp. ) x ( f *) x ( f ≥ ) On dit alors que f(x*) est un minimum local de f dans D et x* est un point de minimum local. b) Minimum ou maximum local strict : f admet un minimum (resp. maximum) local au sens strict en D * x ∈ si et seulement s’il existe un voisinage *) x ( Vε de x*, tel que : ) x ( f *) x ( f *, x x *), x ( V x < ≠ ∈ ∀ ε (resp. ) x ( f *) x ( f > ) c) Minimum ou maximum global: f admet un minimum (resp. maximum) global (ou absolu) en D * x ∈ si : ) x ( f *) x ( f , D x ≤ ∈ ∀ (resp. ) x ( f *) x ( f ≥ ) Si les inégalités sont strictes, on obtient la définition d’un minimum (resp. maximum) global strict. f(x) x Maximum global strict Minimum global strict Maximum local Maximum local Minimum local strict Chapitre 1. Rappels mathématiques N. DJEGHALI 7 1.5 Minima des fonctions convexes Soit f une fonction R D : f → , n R D ⊂ est convexe : • Si f est convexe sur D, alors tout minimum local est un minimum global. • Si f est strictement convexe, alors tout minimum local devient non seulement global mais aussi unique. 1.6 Gradient et Hessien d’une fonction 1.6.1 Gradient : Soit , R R : f n → le gradient de f noté ) x ( f ∇ est donné par :            uploads/Voyage/ optimisation-chapitre-1.pdf