O P T I M I S AT I O N
NUMÉRIQUE
SEDDIK ILIAS INTTIC
INTRODUCTION GÉNÉRALE
Optimisation: la ou les procédures utilisées pour
faire un système ou conception aussi efficace ou
fonctionnel que possible
Euler: "Il n'y a rien dans le monde qui ne se réalise
sans la volonté de minimiser ou maximiser
quelque chose."
INTRODUCTION GÉNÉRALE
Problème d'optimisation = minimisation (ou maximisation) d'une fonction objectif (de coût)
Cette fonction comporte des paramètres et peut être soumise à des contraintes
En fonction des caractéristiques du problèmes (paramètres fortement variables, domaines
discrets, types de contraintes, etc.), le problème peut être difficile à résoudre
Nécessite des outils avancés pour la modélisation et la résolution
➥ Variables (paramètres)
➥ Fonction objectif
➥ Contraintes
INTRODUCTION GÉNÉRALE
Un problème d’optimisation consiste, étant donnée une fonction f : S →R, à trouver :
1. son minimum v (ou son maximum) dans S
2. un point x* ∈ S qui réalise ce minimum (ou maximum) i.e.
f(x*) = v.
Vocabulaire:
f est la fonction objectif
v est la valeur optimale
x* est la solution optimale
S = {solutions réalisables du problème}
écriture du problème : minx∈S f(x) équivalente à maxx∈S f(x)
INTRODUCTION GÉNÉRALE
Trouver la solution à un problème mathématique de cette forme :
x∗ ∈ S où f(x∗) ≤ f(x) ∀ x ∈ S
x∗: solution, f(x∗): valeur optimale de la fonction objectif
x∗ peut ne pas être unique comme il peut ne pas exister.
Maximize f(x) ≡ - Minimize - f(x)
INTRODUCTION GÉNÉRALE
Domaines d’application:
Économie et finance
Biologie
Réseaux / Télécommunications
Logistique / Transport
Défense
Robotique et intelligence artificielle
INTRODUCTION GÉNÉRALE
Exemple de problème:
Trouver un emplacement pour un arrêt de bus T sur le
segment de route QP, de sorte qu’il minimise la somme
des distances entre lui et les villes A et B.
INTRODUCTION GÉNÉRALE
Exemple de problème:
Interpolation de données afin de générer une fonction qui
modélise le mieux possible un phénomène.
INTRODUCTION GÉNÉRALE
Exemple de problème:
On dispose de containers de différentes tailles et de
produits de différentes tailles également à ranger dedans.
Objectif: trouver un arrangement pour minimiser le
nombre de containers.
INTRODUCTION GÉNÉRALE
Exemple de problème:
Comment configurer la topologie de réseaux
informatiques et de leurs sous-réseaux afin de
minimiser le nombre de points d’accès.
INTRODUCTION GÉNÉRALE
Exemple de problème:
Gestion du planning d’examens sachant que le
nombre de salle et de surveillants est limités, et
qu’un surveillant ne peut faire qu’une seule
surveillance en même temps.
INTRODUCTION GÉNÉRALE
Caractéristiques à prendre en compte:
La continuité de la fonction objectif et la linéarité de celle-ci.
Le domaine des variables à utiliser (continu, discret)
– Optimisation continue: Les variables sont typiquement réelles
– Optimisation discrète: Les variables peuvent être binaires, entières…etc mais pas
réelles
La présence ou non de contraintes et leurs types (linéaires, quadratiques…etc)
Les processus sont-ils déterministes ou stochastiques
– Stochastique: Tout ou une partie du problème est aléatoire, les contraintes sont souvent
définies par probabilités
– Déterministe: Le problème et les contraintes sont totalement déterministes
INTRODUCTION GÉNÉRALE
Types de solutions d’optimisation :
Minimum global (= meilleure solution dans l’absolu)
– x* minimum global de (PO) x ∈ X, f(x*) ≤ f(x)
– x* minimum global strict x ∈ X, f(x*) < f(x) si x ≠ x*
Minimum local (= meilleure solution dans un voisinage)
– x* minimum local de (PO) ∃ε > 0 / x ∈ X, ||x-x*|| < ε , f(x*) ≤ f(x)
– x* minimum local strict ∃ε > 0 / x ∈ X, ||x-x*|| < ε , f(x*) < f(x) si x ≠ x*
Où x* est la solution proposée
INTRODUCTION GÉNÉRALE
Types de solutions d’optimisation :
PROCESSUS D’OPTIMISATION
Phases :
Modélisation
Problème Modèle
Analyse du problème
Mise en œuvre
Modélisation et choix de méthode
Résolution
Résolution
Interprétation des résultats
Décision Solution
Interprétation
PROCESSUS D’OPTIMISATION
Analyse du problème:
Compréhension du système
Définition des objectifs, du champ de couverture
Obtention des données
PROCESSUS D’OPTIMISATION
Modélisation:
Choix d'un langage (formel), de la méthode
Traduction du problème : paramètres, domaines, contraintes, incertitude, . . .
Simplification : résultat d'un consensus entre acteurs
PROCESSUS D’OPTIMISATION
Résolution:
La résolution d’un problème d’optimisation peut-être:
– graphique: c’est-à-dire géométrique, mais devient impossible pour des problèmes à
plus de 3 variables
– Analytique: comme pour une optimisation multi-contraintes
– Numérique: programmation mathématique
Mise en œuvre algorithmique, utilisation d'un outil/solveur
Analyse de la robustesse, pertinence des résultats
PROCESSUS D’OPTIMISATION
Interprétation:
Interpréter les résultats dans le monde réel
Présenter aux acteurs
PROCESSUS D’OPTIMISATION
Mise en œuvre:
Mise en œuvre opérationnelle
Suivi des impacts, actions corrective
Peut donner lieu à la définition d'un nouveau problème !
MÉTHODES D’OPTIMISATION
Méthodes génériques:
Programmation linéaire (modélisation sous forme d'équations linéaires)
Programmation en nombres entiers (variables entières)
Programmation quadratique
Programmation dynamique
Méthodes énumératives (PPC) : SAT, CSP, Models
Méta-heuristiques (optimisation stochastique)
domaines de recherche/activité : recherche opérationnelle, intelligence artificielle, . . .
MÉTHODES D’OPTIMISATION
Programmation linéaire
Méthode du simplexe
Algorithme des points intérieurs
Programmation non linéaire
Méthodes de type gradient
Avec dérivées Méthodes de Newton et quasi-Newton
Gauss-Newton, Levenberg-Marquardt (pbs de moindres carrés)
(DFO, NEWUOA, MADS, NOMADS,...)
Méthodes heuristiques : Nelder-Mead, surfaces
Sans dérivées de réponses (réseaux de neurones, krigeage)
Méthodes stochastiques : méthodes à 2 phases, algos génétiques, algos évolutionnaires, recuit
simulé, recherche tabou
Sans contrainte
Méthodes de sous-gradient
Non-diff. Méthodes de faisceaux
Méthodes d’échantillonnage de gradient
Algorithmes proximaux
f(x) = g(x) + h(x) Algorithmes de splitting : descente de
avec g convexe diff gradient proximale (+variante accélérée)
h convexe non diff Douglas Rachford, ADMM
Gradient projeté, algorithme de Uzawa
Méthode SQP (Newton)
Avec contraintes Avec dérivées Points intérieurs
Méthodes de pénalisation, Lagrangien
augmenté
MÉTHODES D’OPTIMISATION
Optimisation numérique
Optimisation continue Optimisation combinatoire
Sans contrainte Avec contrainte Méthodes exactes Méthodes approchées
Linéaires Non linéaires
Descente de gradient, Heuristiques Métaheuristiques
méthodes
newtonniennes…etc
Programmation
dynamique, Hill climbing, recuit
Résolution géométrique, Lagrangien augmenté, Branch&Bound…etc simulé, algorithmes
simplexes…etc méthode d’Uzawa…etc évolutionnistes…etc
