Vocabulaire de l'Optimisation Numérique A-Kadrani Institut National de Statisti

Vocabulaire de l'Optimisation Numérique A-Kadrani Institut National de Statistique et Economie Appliquée (INSEA) Rabat, Mars 2021 Kadrani Programmation Non Linéaire Vocabulaire d'optimisation Dé nitions  Problème d'optimisation Outil mathématique et numérique pour déterminer la meilleure solution possible pour un problème. meilleure ⇒ critère solution ⇒ variables possible ⇒ contraintes. Permet de trouver des solutions qui augmentent l'e cacité d'une entreprise, tout en minimisant les coûts et en augmentant sa rentabilité. Kadrani Programmation Non Linéaire Vocabulaire d'optimisation Dé nitions  Classi cation des problèmes d'optimisation Optimisation fonctionnelle / paramétrique •Inconnues = fonctions → Optimisation fonctionnelle Optimisation en dimension in nie Commande optimale •Inconnues = entiers ou réels → Optimisation paramétrique Optimisation en dimension nie Programmation mathématique Programmation mathématique •Inconnues = entiers → Optimisation combinatoire Programmation en nombres entiers •Inconnues = réels → Optimisation continue Programmation linéaire (LP) Programmation non linéaire (NLP) •Inconnues = entiers et réels → Programmation mixte Kadrani Programmation Non Linéaire Vocabulaire d'optimisation Dé nitions  Formulation mathématique On se donne un ensemble X ⊆Rn et une fonction f : X ⊆Rn − →R. Formulation sans contraintes: min x∈Xf (x) On cherche un élément x∗∈X tel que f (x∗) ≤f (x) pour tout x ∈X x∗= arg min X f . Formulation avec contraintes:        min x∈Rnf (x) s.à. g(x) ≤0 h(x) = 0 x ∈X. On cherche un élément x∗∈F = {x ∈X/g(x) ≤0, h(x) = 0} tel que f (x∗) ≤f (x) pour tout x ∈F x∗= arg min F f . Kadrani Programmation Non Linéaire Vocabulaire d'optimisation Formulation Mathématique  Notations •x : n variables ou inconnues → vecteurs de Rn ou paramètres •f : critère ou fonction coût → fonction de Rn dans R ou fonction objectif x ∈Rn 7→f (x) ∈R •g : q contraintes d'inégalité → fonction de Rn dans Rq ∈Rn 7→g(x) ∈Rq •h : p contraintes d'égalité → fonction de Rn dans Rp x ∈Rn 7→h(x) ∈Rp •X : ensemble convexe X ⊆Rn → valeurs admissibles des variables Kadrani Programmation Non Linéaire Vocabulaire d'optimisation Optimisation continue Hypothèses •Continuité: → Fonctions continues de variables réelles Optimisation continue ̸= Optimisation combinatoire •Diérentiabilité → Fonctions diérentiables Méthodes à base de gradient ̸= Méthodes sans dérivées •Déterminisme → Données du problème connues ̸= Optimisation stochastique •Programmation Linéaire → Coût et contraintes linéaires •Programmation Quadratique → Coût quadratique et contraintes linéaires •Programmation Non Linéaire → Cas général, fonctions quelconques Kadrani Programmation Non Linéaire Vocabulaire d'optimisation Rappels mathématiques  Normes sur Rn Norme vectorielle • Fonction : ∥.∥: Rn →R véri ant        ∥x∥≥0 ∥x∥= 0 ⇔x = 0 ∥x + y∥≤∥x∥+ ∥y∥ ∥αx∥= |α| ∥x∥ • Norme p : ∥x∥p = p v u u t n X i=1 |xi|p • Norme ∞: ∥x∥∞= max i=1,··· ,n |xi| • Norme 2 : ∥x∥2 = v u u t n X i=1 x2 i (norme euclidienne) Norme matricielle • Norme induite sur Rm×n par la norme vectorielle ∥.∥ • Fonction ∥.∥m×n : Rm×n →R dé nie par ∥A∥m×n = max x∈Rn,x̸=0 ∥Ax∥ ∥x∥ Kadrani Programmation Non Linéaire Vocabulaire d'optimisation Rappels mathématiques  Suite dans Rn Suite dans Rn • Suite: {xk, k = 0, 1, 2, · · · } = {x0, x1, x2, · · · , xn, · · · } • Limite: lim k→∞xk = x∗⇔lim k→∞∥xk −x∗∥= 0 Vitesse de convergence • Convergence linéaire: ∥xk+1 −x∗∥≤c ∥xk −x∗∥ avec 0 ≤c < 1 →lente à partir d'un rang k0 • Convergence superlinéaire: ∥xk+1 −x∗∥≤ck ∥xk −x∗∥ avec lim k→∞ck = 0 →bonne à partir d'un rang k0 • Convergence d'ordre p: ∥xk+1 −x∗∥≤c ∥xk −x∗∥p avec 0 ≤c < 1 à partir d'un rang k0 • Convergence quadratique: Convergence d'ordre p avec p = 2 →rapide Kadrani Programmation Non Linéaire Vocabulaire d'optimisation Rappels mathématiques  Diérentiabilité d'ordre 1 Soit f : Rn − →R continue Dérivée partielle: fxi (x) = ∂f (x) ∂xi = lim s→0 f (x1, · · · , xi + s, · · · , xn) −f (x1, · · · , xi, · · · , xn) s Gradient de f en x,noté ∇f (x), est : ∇f : Rn − →Rn avec ∇f (x) = ∂f (x) ∂xi  i=1,··· ,n =     ∂f (x) ∂x1 . . . ∂f (x) ∂xn     Dérivée directionnelle de f en x dans la direction d ∈Rn : fd(x) = lim s→0 f (x + sd) −f (x) s si cette limite existe, alors fd(x) = ∇f (x)Td (dérivée directionnelle=produit scalaire avec le gradient) f diérentiable en x ⇔f admet une dérivée directionnelle pour tout d ∈Rn Kadrani Programmation Non Linéaire Vocabulaire d'optimisation Rappels mathématiques  Diérentiabilité d'ordre 2 Soit f : Rn − →R deux fois diérentiables Hessien de f en x,noté ∇2f (x), est : ∇2f : Rn − →Rn×n avec ∇2f (x) = ∂2f (x) ∂xi∂xj  i,j=1,··· ,n =    ∂2f (x) ∂x2 1 · · · ∂2f (x) ∂x1∂xn · · · · · · · · · ∂2f (x) ∂xn∂x1 · · · ∂2f (x) ∂x2 n    Courbure: On dé nit pour une direction d ∈Rn au point x la fonction ϕ à une variable : ϕ(s) = f (x + sd) •Dérivéé première : ϕ ′(s) = dT∇f (x + sd) →ϕ ′(0) = dT∇f (x) •Dérivéé seconde : ϕ ′′(s) = dT∇2f (x + sd)d →ϕ ′′(0) = dT∇2f (x)d La courbure de f en x dans la direction d est dé nie par: dT ∇2f (x)d dT d Kadrani Programmation Non Linéaire Vocabulaire d'optimisation Rappels mathématiques  Développement de Taylor Soient f : Rn − →R et d ∈Rn • Ordre 1 f continument diérentiable 1 fois au voisinage de x f (x + d) = f (x) + ∇f (x)Td + o (∥d∥) Il existe s ∈[0, 1] tel que: f (x + d) = f (x) + ∇f (x + sd)Td • Ordre 2 f continument diérentiable 2 fois au voisinage de x f (x + d) = f (x) + ∇f (x)Td + 1 2dT∇2f (x)d + o ∥d∥2
Il existe s ∈[0, 1] tel que: f (x + d) = f (x) + ∇f (x)Td + 1 2dT∇2f (x + sd)d Kadrani Programmation Non Linéaire Problème d'optimisation Formulation (1) On se donne: un ensemble admissible X et une fonction objectif f : X − →R. On cherche: un élément x∗∈X tel que f (x∗) ≤f (x) pour tout x ∈X x∗= arg min X f . Sous quelles formes présenter le problème d'optimisation? Formes standard ou canonique Exigences des algorithmes Nécessité de transformer le problème Kadrani Programmation Non Linéaire Problème d'optimisation Formulation (2) Fonction objectif min f (x) max f (x) Contraintes h(x) ≤cte h(x) ≥cte h(x) = cte Contraintes de bornes l ≤x ≤u Contraintes de signe x ≥0 Kadrani Programmation Non Linéaire Problème d'optimisation  Transformation min f (x) ⇌ −max(−f (x)) g(x) ≤0 ⇌ −g(x) ≥0 g(x) ≤0 ⇌  g(x) + y = 0 y ≥0 g(x) = 0 ⇌  g(x) ≤0 g(x) ≥0 x ∈R ⇌    x = y −z y ≥0 z ≥0 x ≥a ⇌  x = y + a y ≥0 Kadrani Programmation Non Linéaire Problème d'optimisation  Transformation                                                  max −x2 + sin y ⇌ −min x2 −sin y sujette à: 6x2 −y2 ≥1 ⇌ −6x2 + y2 + 1 ≤0 x + y2 = 3 ⇌ x + y2 −3 ≤0 −x −y2 + 3 ≤0 x ≥2 ⇌ x = x1 + 2 x1 ≥0 y ∈R ⇌ y = y1 −y2 y1 ≥0 y2 ≥0 Kadrani Programmation Non Linéaire Problème d'optimisation  Transformation                                                  −min(x1 + 2)2 −sin(y1 −y2) sujette à: −6(x1 + 2) + (y1 −y2)2 + 1 ≤0 (x1 + 2)2 + (y1 −y2)2 −3 ≤0 −(x1 + 2)2 −(y1 −y2)2 + 3 ≤0 x1 ≥0 y1 ≥0 y2 ≥0 Kadrani Programmation Non Linéaire Modèles d'optimisation Modèle linéaire 1 Une entreprise gagne 5DH chaque fois qu'elle vend 1 litre de produit chimique. Elle désire maximiser son pro t. . . . . . . . Observations: - Fonction objectif linéaire - Pas de contraintes - Solution in nie Commentaire: La solution est toujours in nie lorsque la fonction objectif est linéaire et qu'il n'y a pas de contraintes. Kadrani Programmation Non Linéaire Modèles d'optimisation Modèle linéaire 2 Un laboratoire uploads/Voyage/ chap1-pnl-2021.pdf

Documents similaires

Avant le départ Préparez votre séjour Avant le départ Préparez votre séjour Fic 0 0

Rapport : Atelier 3 : Mise en œuvre de la méthode de pénalisation Réalisé par : 0 0

Rapport : Atelier 3 : Mise en œuvre de la méthode de pénalisation Réalisé par : 0 0

1/8 Chap. : Programmation linéaire 1. La programmation linéaire La programmatio 0 0

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

Rapport : Atelier 3 : Mise en œuvre de la méthode de pénalisation Réalisé par : 0 0

Vocabulaire de l'Optimisation Numérique A-Kadrani Institut National de Statisti 0 0

• Détails
• Publié le Mai 11, 2021
• Catégorie Travel / Voayage
• Langue French
• Taille du fichier 1.3063MB