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, 1ère Master en ELT Semestre : S1 ; Option : 1MAUT ______________________

Cours, 1ère Master en ELT Semestre : S1 ; Option : 1MAUT _________________________________________________________________________________________________________________ Cours d’Optimisation Prof. Lakhdar MOKRANI 1 Chapitre 1 Rappels Mathématiques et Formulation des Problèmes d’Optimisation I.1 Introduction Dans ce chapitre nous allons introduire quelques rappels mathématiques en relation étroite avec les méthodes d’optimisation différentielles (méthodes de programmation mathématique linéaire et non linéaire), à savoir : la positivité des matrices, la convexité des fonctions multi-variables, les extrema (minimums / maximums) de ce genre de fonctions, le gradient et la matrice hessienne de ces mêmes fonctions. Avant de présenter ces rappels, nous allons tout d’abord introduire une formulation et une classification des différents problèmes d’optimisation (linéaires / non linéaires, contraints / non contraints, …). Nous nous limitons aux problèmes traitant des fonctions scalaires multi- variables continues et dérivables. I.2 Définition et formulation générale d’un problème d’optimisation Optimiser signifie chercher une conception optimale d’un système, c’est à dire, la meilleure combinaison des paramètres de conception du système et ceci, par rapport à un indexe (critère) de performance donné appelé ‘fonction objectif’. Cette opération passe par l’établissement d’un modèle mathématique représentatif du système (problème) à optimiser, puis choisir les variables de conception à optimiser, ensuite exprimer la fonction objectif à optimiser et l’ensemble des contraintes à respecter. En général, un problème d’optimisation ‘mon-objectif’ peut être formulé ainsi : 0 = (X) h 0 (X) g : à sujette X X) f / n ≤ ℜ ∈ ( min max Où : f(X) est la fonction scalaire à optimiser (X) g est l'ensemble de p contraintes inégalités (X) h est l'ensemble de m contraintes égalités f est appelée fonction de coût, fonction objectif, ou bien critère d’optimisation. Dans certains cas : ℜ ⊂ Ω ∈ n X où Ω est l’ensemble ou espace de recherche admissible ou encore ensemble admissible. Cours, 1ère Master en ELT Semestre : S1 ; Option : 1MAUT _________________________________________________________________________________________________________________ Cours d’Optimisation Prof. Lakhdar MOKRANI 2 I.3 Classification des problèmes d’optimisation Les problèmes d’optimisation peuvent être classés selon plusieurs angles de vue : I.3.1 Classification selon les propriétés de la fonction ‘objectif’ Dans ce cas, on distingue les classes suivantes des problèmes d’optimisation : – Les problèmes unidimensionnels pour les fonctions à une seule variable ; – Les problèmes multidimensionnels pour les fonctions à plusieurs variables ; – Les problèmes mono-objectifs pour les fonctions scalaires ; – Les problèmes multi-objectifs pour les fonctions vectorielles ; – Les problèmes d’optimisation ou programmation mathématique, linéaires pour les fonctions linéaires ; – Les problèmes d’optimisation ou programmation mathématique, non linéaires pour les fonctions non linéaires ; – Les problèmes d’optimisation quadratique pour les fonctions quadratiques ; – Les problèmes d’optimisation (non) convexes pour les fonctions (non) convexes ; – Les problèmes d’optimisation concernant les fonctions continûment dérivables ; – Les problèmes d’optimisation concernant les fonctions non dérivables (à variables discrètes par exemple) ; – Les problèmes d’optimisation combinatoire concernant les fonctions à variables entières. I.3.1 Classification selon l’existence et les propriétés des contraintes Dans ce cas, on distingue les classes principales suivantes des problèmes d’optimisation : – Les problèmes d’optimisation non contraints ou sans contraintes s’il n’y a pas de contraintes ; – Les problèmes d’optimisation contraints ou avec contraintes s’il y a au moins une contrainte ; – Les problèmes d’optimisation aux bornes si les contraintes sont de simples bornes sur les variables ; – Les problèmes d’optimisation ou de programmation mathématique contraints et linéaires si (en plus de la fonction objectif) les contraintes sont aussi des fonctions linéaires ; – Les problèmes d’optimisation ou programmation mathématique contraints et non-linéaires si (la fonction objectif ou bien) au moins l’une des contraintes est une fonction non linéaire. Cours, 1ère Master en ELT Semestre : S1 ; Option : 1MAUT _________________________________________________________________________________________________________________ Cours d’Optimisation Prof. Lakhdar MOKRANI 3 I.4 Formulation de quelques classes de problèmes d’optimisation Dans cette section, nous allons donner la formulation de quelques classes de problèmes d’optimisation : I.4.1 Programmation linéaire Cette classe de problèmes est définie en général, ainsi : ( ) { 2 2 1 1 & b X A b X A X X C X f T = ≤ = Ω = I.4.2 Programmation quadratique Cette classe de problèmes est définie en général, comme suit : ( ) { 2 2 1 1 & : 2 1 d X C d X C X A A avec X b AX X X f T T T = ≤ = Ω = − = I.4.3 Programmation non linéaire Dans ce cas, la fonction objectif f(X) et/ou au moins l’une des contraintes inégalités g(X) ou égalités h(X) sont non linéaires. I.4.4 Programmation convexe Dans ce cas, la fonction objectif f(X) et le domaine de faisabilité Ω sont convexes. I.5 Rappels mathématiques Dans cette partie du chapitre nous allons exposer quelques rappels mathématiques en relation étroite avec les problèmes d’optimisation différentielle (positivité des matrices ; convexité des fonctions multi-variables ; extrema (minimums / maximums), gradient et matrice hessienne des fonctions multi-variables). I.5.1 Positivité des matrices On dit qu’une matrice carrée et symétrique qu’elle est définie positive (A=AT>0) si et seulement si : xTAx>0 et ceci . 0 ≠ ∈ ∀ x et R x n Cours, 1ère Master en ELT Semestre : S1 ; Option : 1MAUT _________________________________________________________________________________________________________________ Cours d’Optimisation Prof. Lakhdar MOKRANI 4 Donnons dans ce qui suit quelques propriétés des matrices symétriques et définies positives. Soit :                 = nn n n a a a a A . . . . . . . . . . . . . . . 1 1 11 A est définie positive si : - Ses valeurs propres λi=1,…n (calculées d’après det(A-λIn)=0 )sont positives. - Si les déterminant des sous-matrices suivantes sont positifs : det{Ak}>0 pour k=1, … , n ; avec : A=a11 ;       = 22 21 12 11 2 a a a a A ;           = 33 32 31 23 22 21 13 12 11 2 a a a a a a a a a A ; … et An=A. - Si les éléments (lii=1,n) de la diagonale de la matrice L issue de la décomposition de Cholesky de la matrice A (avec LTL=A) sont tous positifs. I.5.2 Convexité des ensembles et des fonctions I.5.2.1 Convexité des ensembles Un ensemble c est dit convexe si Ω ∈ ∀ y x, on alors : Ω ∈ ] , [ y x . C’est-à-dire quelque soit deux points dans Ω, tout le segment qui les lie est dans Ω. I.5.2.2 Convexité des fonctions On dit qu’une fonction scalaire et multi-variable f(X) définie sur un ensemble convexe ℜ ⊂ Ω n qu’elle est convexe, si et seulement si son épigraphe est convexe (voir figure suivante) En d’autres termes, cette même fonction est dite convexe si : Cours, 1ère Master en ELT Semestre : S1 ; Option : 1MAUT _________________________________________________________________________________________________________________ Cours d’Optimisation Prof. Lakhdar MOKRANI 5 Ω ∈ ∀ y x, et ] 1 , 0 [ ∈ ∀α alors : ( ) ( ) ( ) ( ) ( ) y f x f y x f α α α α − + ≤ − + 1 1 ; comme l’illustre bien la figure ci-après : Notes : - On dit qu’une fonction f(X) est concave si -f(X) est convexe. - Un fonction peut ne pas être ni convexe ni concave. I.5.3 Extrémums d’une fonction multi-variable Les extrémums d’une fonction multi-variable sont ces minimums et maximums. On distingue plusieurs types de minimums (maximums) : - On dit que Ω ∈ * x est un minimum global de f(X) si : Ω ∈ ∀x alors ( ) ( ) * x f x f ≤ . - On dit que Ω ∈ * x est un minimum local de f(X) si : ( ) * x V x ∈ ∀ alors ( ) ( ) * x f x f ≤ , où ( ) * x V est un voisinage de * x . - On dit que Ω ∈ * x est un minimum de f(X) si Ω ∈ * x est un minimum de -f(X). Voici une figure qui illustre ces différentes situations : Note : Si f(X) est une fonction convexe (concave), alors tout minimum (maximum) local de f(X) est un minimum (maximum) global de f(X). I.5.4 Gradient d’une fonction multi-variable Le gradient d’une fonction multi-variable est un vecteur indiquant la direction de la variation extrémale d’une fonction multi-variable. Il est exprimé par : Cours, 1ère Master en ELT Semestre : S1 ; Option : 1MAUT _________________________________________________________________________________________________________________ Cours d’Optimisation Prof. Lakhdar MOKRANI 6 ( ) ( ) ( ) ( ) T n 1 T T x X f ... x X f = X f X g       ∂ ∂ ∂ ∂ ∇ = . I.5.5 Matrice hessienne d’une fonction multi-variable La matrice hessienne d’une fonction multi-variable est exprimée par : ( uploads/Voyage/ chapitre-1-optimisation-1mauts.pdf