Cours d'Optimisation 16 novembre 2021 Chapitre 1 Rappels mathématiques 1.1 Intr

Cours d'Optimisation 16 novembre 2021 Chapitre 1 Rappels mathématiques 1.1 Introduction L'optimisation est une branche des mathématiques, dont le but est de chercher à résoudre analytiquement ou numériquement, la meilleur solution (l'optimale) à un problème donné. L'origine du mot optimale provient du Latin optimum qui signi e le meilleur. De nos jours, l'optimisation joue un rôle très important dans diérents domaines de la vie. Voici quelques domaines d'applications de l'optimisation :  Transport et livraisons.  Fabrication et production.  Agriculture et génie civil.  Finance, vente et marketing  Gestion de stock  Recherche et gestion des bases de données.  ... On distingue deux grandes familles de techniques d'optimisation, et cela suivant le problème posé :  Techniques d'optimisation sans contraintes.  Techniques d'optimisation sous contraintes. En optimisation, on parle souvent de la fonction coût (objectif). C'est la fonction à minimiser/maximiser. 1.1.1 Notations Dans ce qui suit, on considère la notation des variables suivantes :  n, m, p, ..., des scalaires qui indiquent souvant les dimensions,  x, y, t, λ, α..., des variables scalaires,  x, y, X, Y, ..., des vecteurs colonne,  A, M, P, ..., des matrices.  E, I, ..., ensembles ou intervalles 1 x y 0 Figure 1.1  Exemple d'une fonction coût 1.1.2 Vecteur Le vecteur réel X de dimension n, se met sous la forme : X =     x1 x2 ... xn     (1.1) ou encore de la manière suivante : X =  x1 x2 ... xn ′ (1.2)  deux vecteurs sont égaux ssi tous leurs éléments sont égaux.  Le produit scalaire de deux vecteurs X et Y est dé ni par : X′Y = Y′X = n X i=1 xiyi  Les deux vecteurs X et Y sont orthogonaux si : X′Y = 0  La norme d'un vecteur X est : |X| = √ X′X  L'inégalité de Cauchy-Schwarz est véri ée pour les deux vecteurs X et Y : |X′Y| ≤|X|.|Y| 2 1.1.3 Matrice Dans ce cours on ne considère que les matrice réelles. Une matrice A de dimension m × n est donnée par : A =     a11 a12 ... a1n a21 a22 ... a2n ... ... ... ... am1 am2 ... amn     (1.3) La matrice transposée de la matrice A qu'on note A′ ou AT, est de dimension n × m est la suivante : A =     a11 a21 ... am1 a12 a22 ... am2 ... ... ... ... a1n a2n ... amn     (1.4) La somme (diérence) de deux matrice de dimensions identiques est une matrice de même dimension, dont les élements sont égaux à la somme (diérence) des éléments de même position. Le produit de deux matrice A (m × p) et B (p × n) est une matrice C (m × n) dont les élements sont : cij = p X k=1 aikbkj i = 1, ..., m j = 1, ..., n La multiplication des matrices requière une attention partculière, le nombre de colonne de la première doit être égale au nombre de ligne de la deuxième. Prenant l'exemple illsutratif suivant : soit un vecteur X de dimension n alors, X′X =  x1 x2 ... xn      x1 x2 ... xn     = x2 1 + x2 2 + ... + x2 n Le résultat du produit X′X est un scalaire. 3 XX′ =     x1 x2 ... xn      x1 x2 ... xn  =     x2 1 x1x2 ... x1xn x2x1 x2 2 ... x2xn ... ... ... ... xnx1 xnx2 ... x2 n     Le résultat du produit XX′ est une matrice. Une matrice est dite carrée dans le cas particulier où n = m. On dé ni la matrice identité I de la manière suivante : I =     1 0 ... 0 0 1 ... 0 ... ... ... ... 0 0 ... 1     (1.5) Souvent on indique la dimension n de la matrice identité In. Exercice 1. Opérations sur les matrices et les vecteurs . Soit les deux vecteurs A = [1, 2, 3]′ et B = [−1, 0, 2]′. Eectuer les opérations sui- vantes : a. AB′. b. A′B. c. AB′B 1.1.4 Valeurs propres On appel le scalaire λ valeur propre de la matrice A s'il existe un vecteur non nul V tel que : AV = λV Le vecteur V est appelé vecteur propre de la matrice A associé à la valeur propre λ ( Exp. A = [3 2 ; 3 −2], V = [2 1]′, λ = 4). Les valeurs propres présentent la solution de l'équation caractéristique suivante : |A −λIn| = 0 4 Le déterminant d'une matrice A peut être donné par le produit de ses valeurs propres qu'on note {λi}n i=1. |A| = n Y i=1 λi Si la matrice carrée A est symétrique alors : 1. Les valeurs propres sont positifs. 2. Les vecteurs propres associées aux diérentes valeurs propres sont orthogonaux. 3. Il existe une base orthogonale où chaque élément présente un vecteur propre de A. La matrice carrée A est inversible si son déterminant est diérent de zéro. La matrice inverse est notée A−1, on a alors : AA−1 = In La trace de A est la somme de ses éléments diagonaux : Tr(A) = n X i=1 aii (1.6) La trace d'une matrice carrée est égale à la somme de ces valeurs propres Tr(A) = P λi. Une matrice est dite symétrique si elle véri e la condition : A = A′ (1.7) Dans ce qui suit on ne considère que le cas des matrices carrées et symétriques, sauf si on l'indique clairement. Exercice 2. Soit la matrice carrée A dont les valeurs propres sont : λ1 = 1, λ2 = 2 et λ3 = 5. 1. Quelles sont les dimensions de la matrice A ? 2. Que peut on dire sur la positivité de la matrice A ? 3. Comment déterminer l'équation caractéristique de A ? 4. Calculer le déterminant de A. 5. La matrice A est elle inversible ? Pourquoi ? 6. Calculer la trace de la matrice A. 5 1.2 Positivité 1.2.1 Dé nition  Une fonction f(x) est dite positive ssi f(x) > 0, ∀x ∈ℜ.  Une matrice symétrique A est dé nie positive ssi X′AX > 0, ∀X ̸= 0.  Une matrice symétrique A de dimension n est dé nie positive si toutes les valeurs propres sont positives λi > 0, ∀i = 1, ..., n.  Une matrice A de dimension n est dé nie positive si tous les mineurs principaux sont positifs. 1.2.2 Exemples 1. La fonction f(x) = x2 −4x + 5 est dé nie positive sur l'ensemble ℜ. 2. La matrice : A =  2 1 1 2  est dé nie positive, car ses valeurs propres sont po- sitives. Les valeurs propres sont les solutions de l'équation caractéristique |A − λI2| = 0. Exercice 3. Matrice positive . Déterminer parmi les matrices suivantes celles qui sont dé nies positives : a. A =  2 1 1 2  b. B =  2 −1 −1 2  Utiliser la dé nition ensuite les valeurs propres. 1.3 Convexité 1.3.1 Fonction convexe Soit la fonction f, dé nie sur un intervalle I de ℜn, telle que ∀(x1, x2) ∈I2 et ∀α ∈[0, 1], on dit que la fonction f est convexe (ou plus exactement strictement convexe) si elle véri e l'inégalité suivante : f(αx1 + (1 −α)x2) ≤αf(x1) + (1 −α)f(x2) (1.8) Remarque Si la fonction f(x) ∈ℜ, elle est convexe si on a f ′′(x) ≥0 sur le domaine de dé nition. 6 Figure 1.2  Exemple d'une fonction convexe 1.3.2 Ensemble convexe Un ensemble Ω⊂ℜn est dit convexe ssi : ∀u, v ∈Ω et ∀α ∈[0, 1], on a x = αu + (1 −α)v ∈Ω (1.9) Exercice 4. Démontrer que l'ensemble dé nie par Ω= { X ∈ℜn : a′X ≥β}, où a ∈ℜn et β ∈ℜ, est convexe, Ωest appelé demi-espace halfspace. Figure 1.3  Illustration d'ensembles convexes et non vonvexes 1.4 Le gradient Soit f(X) une fonction scalaire de n variables. Le gradient de la fonction f qu'on note ∇f est un vecteur ligne dont les élements sont les dérivées partielles de la fonction f suivant chaque variable. ∇f = ∂f ∂X = h ∂f ∂x1 ∂f ∂x2 ... ∂f ∂xn i (1.10) Exemple Trouver le gradient de la fonction f(x, y) = x2 + xy + y2. 7 Solution ∂f ∂x = 2x + y, ∂f ∂y = x + 2y, ∂f ∂X = [2x + y , x + 2y] 1.5 Le Hessien Soit f(X) une fonction scalaire de n variables. Le Hessien de la fonction f, qu'on note Hf est une uploads/Industriel/cours-d-x27-optimisation.pdf

Tags
Industrielfonction matrice problème cette solution
Documents similaires
  • 29
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager