Remerciez-le!

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

Outils Mathématiques en Optimisation differentielle convexe ECC Abdelilah Hakim

Outils Mathématiques en Optimisation differentielle convexe ECC Abdelilah Hakim Laboratory of Applied Mathematics and Computer Science Faculty of Science and Techniques Cady Ayyad University 19/09/2022 (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 1 / 71 Définition et Domaines d’application Definition de l’optimisation : Choisir parmi plusieurs possibilités une solution d’un problème mathématique qui répond le mieux à certains critères Domaines d’applications Optimisation des ressources : Gains, coùt dans l’industrie Transports : trafic aérien, ferroviaire, routier Domaines millitaire : Couverture radar, réactivité d’intervention, Gestions de stocks et des troupes Sciences dures : Physique, chimie, informatique, automatique, traitement du signal, Intelligence artificielle etc... (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 2 / 71 Objectifs du cours Principales notion : Espace de Hilbert, Differentiabilité, Convexité... Résultats théoriques : Existence de solution et Unicité Conditions d’optimalité : Problèmes sans contraintes, Problèmes avec contraintes, Conditions d’Euler, Conditions Euler Legendre Algorithmes : Gradient de décentes et ses variantes, Méthode de Newton (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 3 / 71 Qu’est ce que l’optimisation ? Forme Abstraite d’un problème d’optimisation E un ensemble K un sous ensemble de E une application J : E − →R Formulation Mathématique de problème on veut résoudre le problème (P) ( x∗∈K J (x∗) = inf x∈K J(x) (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 4 / 71 Questions traitées dans un problème de minimisation Est-ce que inf x∈K J(x) existe ? c.à.d. est-ce que J est bornée inférieurement ? Est-ce que l’infimum est atteint dans K ? c.à.d. est-ce qu’il existe x∗∈K vérifiant J (x∗) = min J(x)? Est-ce que l’infimum est atteint dans K ? c.à.d. est-ce qu’il existe x∗∈K vérifiant J (x+) = minx∈K J(x)? (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 5 / 71 Questions traitées dans un problème de minimisation Est-ce que x∗est unique ? Sinon, quelle est la taille de l’ensemble des solutions ? Est-ce que l’on peut caractériser x∗? c.à.d. peut-on trouver des conditions nécessaires et suffisantes pour caractériser un minimum. Trouver un algorithme d’optimisation pour déterminer la, resp. les, solutions de (P). (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 6 / 71 Résolution d’un problème d’optimisation la structure de E : espace vectoriel, muni d’une norme, d’un produit scalaire, de dimension finie ou infinie, ... les propriétés de K ⊂E : fermé, borné, convexe, compacte... les propriétés de J : E − →R : continuité, différentiabilité, coercivité, convexité,... (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 7 / 71 Est-il vraiment nécessaire d’étudier l’optimisation dans un espace de Hilbert de dimension infinie ? On pourrait croire que non : Beaucoup de problèmes d’optimisation sont posés en dimension finie, V = Rn, Après "discrétisation" tout se ramène à la dimension finie, C’est beaucoup plus simple en dimension finie. Néanmoins, la dimension infinie est essentielle : Souvent la variable d’optimisation est une fonction (comme en contrôle optimal), donc il faut travailler en dimension infinie, Même en dimension finie, si la dimension est grande, le point de vue et les méthodes de la dimension infinie sont très utiles, Les espaces de Hilbert sont les plus simples en dim. infinie. (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 8 / 71 Types de problèmes en optimisation L’optimisation se scinde essentiellement en deux disciplines dont les outils et méthodes sont complètement differents. Il s’agit de l’optimisation discrète et l’optimisation continue. Si K est discret (K ⊂Z n, fini ou dénombrable),on parle d’optimisation combinatoire.Les outils proviennent des mathématiques discrètes ( Théorie de graphe ) Si K est continue, et J est continue, on parle d’optimisation continue. Les outils proviennent essentiellement de l’analyse ( Calcul différentiel, Convexité, Algèbre linéaire ) (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 9 / 71 Classes de problèmes d’optimisation continues la classe des problemes d’optimisation continue est bien trop large pour espérer obtenir une méthode de résolution générale efficiente. On va restreindre cette classe de problèmes à des sous-classes, K = {(x1, x2, . . . , xn) ∈U ⊂Rn | φi (x1, . . . , xn) ⩽0, i = 1, . . . , p | {z } contraintes inégalitaires , ψj (x1, . . . , xn) = 0, j = 1, . . . , q | {z } contraintes égalitaires } (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 10 / 71 Classes de problèmes d’optimisation continues Programmation linéaire : lorsque J, φ1, . . . , φp, ψ1, . . . , ψq sont des applications affines et, U = Rn. Programmation quadratique : lorsque J est une application quadratique, φ1, . . . , . . . φp, ψ1, . . . , ψq sont, des applications affines et, U = Rn. Programmation convexe : problème de minimisaticn lorscue J et φ1, . . . , φp sont des applications convexes, ψ1, . . . , ψq sont des applications affines, et. U est convexe. (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 11 / 71 Problèmes typiques d’optimisation Résolution d’un système matriciel. A une matrice symétrique N × N définie positive b un vecteur de RN. La solution du système linéaire Ax = b est donnée par le point de minimum suivant : inf x∈RN 1 2(Ax, x) −(b, x) (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 12 / 71 Problèmes typiques d’optimisation Problème de transport. Exemple de programmation linéaire. But : Optimiser la livraison d’une marchandise (un problème classique en logistique). Problèmatique : On dispose de M entrepôts, indicés par 1 ≤i ≤M, disposant chacun d’un niveau de stocks si. Il faut livrer N clients, indicés par 1 ≤j ≤N, qui ont commandé chacun une quantité rj. Le coût de transport unitaire entre l’entrepôt i et le client j est donné par cij. Les variables de décision : les quantités vij de marchandise partant de l’entrepôt i vers le client j. Résolution : Minimiser le coût du transport tout en satisfaisant les commandes deas clients (on suppose que M X i=1 si ≥ N X j=1 rj ). inf (vij)   M X i=1 N X j=1 cijvij   Les contraintes de limites des stocks et de satisfaction des clients : N M (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 13 / 71 Problèmes typiques d’optimisation Problèmes de moindre carré : Problème en statistique ou bien en analyse de donnée. Probleme d’estimation de parametres d’un modele en fonction de données mesurées ou expérimentales. Problème de régression linéaire Formulation du problème : inf x∈Rn ∥Ax −b∥2, b ∈Rp les données du problème x ∈Rn les paramètres inconnus A, matrice réelle Exemple algebrique : Quotient de Rayleigh qui permet de calculer les valeurs et vecteurs proppres d’une matrice symétrique. (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 14 / 71 Problèmes typiques d’optimisation Première valeur propre A une matrice carré d’ordre n, symétrique Résolution du problème : inf x∈Rn,∥x∥=1 (Ax, x) où ∥x∥est la norme euclidienne de x. (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 15 / 71 Problèmes typiques d’optimisation Problèmes d’Entropie Notion en thérmodynamique, physique statistique et théorie de l’information. Problème de maximisation ( changement de signe ) Exemple : Entropie de Shannon en théorie de l’information inf p∈Rn + n X i=1 pi = 1 n X i=1 pi log pi ! (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 16 / 71 Problèmes typiques d’optimisation Minimisation d’une énergie mécanique Minimisation de l’energie mécanique d’une membrane ou bien l’energie électrostatique d’un conducteur. Ωun ouvert borné de RN et f une fonction continue sur ¯ Ω. Résolution du probleme de Dirichlet pour le Laplacien, Minimisation de l’energie J(v) : J(v) = 1 2 Z Ω |∇v|2dx − Z Ω fvdx v ∈V0 = n ϕ ∈C1(¯ Ω) tel que ϕ = 0 sur ∂Ω o . (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 17 / 71 Problèmes typiques d’optimisation Traitement des images On représente une image noir et blanc par une fonction définie sur un domaine Ωdu plan dont les valeurs indiquent un niveau de gris. Une image acquise, par exemple par un appareil photographique, f (x) est entachée de "bruit" qui correspond à des défauts du capteur Reduction du bruit : Technique de lissage et régularisation Préservation des contours Minimisation de la variation totale La régularisation u(x) de l’image originale f (x) : inf u(x):Ω→R J(u) = Z Ω |∇u|dx + ℓ Z Ω |f −u|2dx , où ℓ> 0 est un paramètre qui permet de moduler le lissage. (FSTG) Outils Mathématiques en Optimisation differentielle convexe 19/09/2022 18 / 71 Problèmes typiques d’optimisation Apprentissagemachine On dispose d’un très grand nombre de données (xi)1≤i≤n (des images, du texte, des mesures expérimentales, etc.) Données caractérisées par des vecteurs xi ∈Rd Un label yi, très souvent un booléen (ici, −1 ou +1 ), qui donne un type à la donnée xi On introduit une fonction affine, dite de prédiction, hw,τ(x) = w · x −τ où w ∈Rd et τ ∈R sont des paramètres à optimiser. On souhaite trouver des paramètres uploads/Science et Technologie/ ch1-outil-optim-ecc-sept22.pdf