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 2020 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.à. cE(x) = 0 cI(x) ≤0 x ∈X. On cherche un élément x∗∈F = {x ∈X/cE(x) = 0, cI(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 •cE : p contraintes d'égalité → fonction de Rn dans Rp x ∈Rn 7→cE(x) ∈Rp •cI : q contraintes d'inégalité → fonction de Rn dans Rq ∈Rn 7→cI(x) ∈Rq •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 : g : Rn − →Rn avec ∇f (x) = g(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) = g(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 : H : Rn − →Rn×n avec H(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) = dTg(x) •Dérivéé seconde : ϕ ′′(s) = dT∇2f (x + sd)d →ϕ ′′(0) = dTH(x)d La courbure de f en x dans la direction d est dé nie par: dT H(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 Exemples: Voyageur de commerce Kadrani Programmation Non Linéaire Problème d'optimisation Exemples: Moindres carrées Kadrani Programmation Non Linéaire Problème d'optimisation Exemples: Optimisation d'un portefeuille d'action (1) On possèede n actions, que l'on représente par des variables aléatoires R1, . . . , Rn Chaque action rapporte en moyenne à l'actionnaire ei = E(Ri) (espérance de Ri ) au bout d'un an. On investit une somme S donnée, et l'on note xi ∈R, la proportion de la somme investie dans l'action i , de sorte que n X i=1 xi = 1 Le portefeuille total est représenté par la variable aléatoire R = n X i=1 xiRi Rendement du portefeuille= E(R) = i=1 X n xiei. Risque du portefeuille= σ2(x) = E  (R −E(R))2 . Un calcul simple montre que σ2(x) = (x, Ax) avec A = (aij)1≤i,j≤n et ∀(i, j) ∈{1, . . . , n}2 , aij = E [Ri −E(Ri)] [Rj −E(Rj)] . Kadrani Programmation Non Linéaire Problème d'optimisation Exemples: Optimisation d'un portefeuille d'action (2) Le rendement se réécrit n X i=1 xiei = (e, x) On pose u = (1, . . . , 1). La somme des proportions d'actions = 1 = (x, u) On dit qu'un portefeuille x est e cient s'il assure à la fois un rendement maximal ϵ pour un risque donné σ et un risque minimal σ pour un rendement imposé ϵ. Pour ϵ ∈R et σ ∈R+ donnés, on dé nit les ensembles: C1(ϵ) = {x ∈Rn : (u, x) = 1 et (e, x) = ϵ} , C2(σ) =  x ∈Rn : (u, x) = 1 et 1 2(Ax, x) = σ . On cherche à résoudre les problèmes (P−) inf x∈C1(ϵ) 1 2(Ax, x) et (P+) sup x∈C2(σ) (e, x) Kadrani Programmation Non Linéaire Problème d'optimisation Exemples: Optimisation de forme (1) Kadrani Programmation Non Linéaire Problème d'optimisation Exemples: Optimisation de forme (2) Mathématiquement, le problème à résoudre est très proche du problème isopérimétrique: Déterminer Ω, un domaine plan solution du problème d'optimisation  maximiser aire(Ω) sachant que le périmètre(Ω) = 4km. Le problème consiste à trouver la courbe plane de longueur ℓ xée qui enclot avec le segment reliant ses deux extrémités, la portion plane d'aire maximale, autrement dit, on résout pour b > a ≥0, sup y∈Γ Z b a y(x)dx où Γ = ( y ∈Y | Z b a q 1 + y ′2(x)dx = ℓet y(a) = y(b) = 0 ) avec Y , un espace fonctionnel donné (choisi par exemple de sorte que ce problème possède une solution). Kadrani Programmation Non Linéaire Problème d'optimisation Formulation (1) On se donne: un ensemble admissible X et une fonction objectif f : uploads/Voyage/ chap1.pdf

Documents similaires

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

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

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

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

• Détails
• Publié le Apv 05, 2022
• Catégorie Travel / Voayage
• Langue French
• Taille du fichier 1.6996MB