Optimization Toolbox

Principales fonctionnalités

  • Optimisation non linéaire et multi-objectif
  • Solveurs par moindres carrés non linéaires, pour l’ajustement de données et les équations non linéaires
  • Programmation quadratique et linéaire
  • Programmation linéaire d’entiers mixtes
  • Une application (‘Optimization’) permettant de définir et de résoudre des problèmes d’optimisation, en visualisant l’évolution de la solution
  • Accélération des solveurs non linéaires contraints grâce à la Parallel Computing Toolbox™
Utilisation d’un problème de programmation linéaire d’entiers mixtes pour déterminer le meilleur moyen de fournir les sites de vente à partir des entrepôts et des usines.
Utilisation d’un problème de programmation linéaire d’entiers mixtes pour déterminer le meilleur moyen de fournir les sites de vente à partir des entrepôts et des usines.

Définition et résolution de problèmes d’optimisation

Définition d’un problème d’optimisation

Les techniques d’optimisation sont utilisées pour trouver l’ensemble de paramètres dit de ‘conception’, qui offrent le meilleur résultat possible. Les deux composants clés d’un problème d’optimisation sont:

La fonction objective calcule la quantité à minimiser ou à optimiser. Des contraintes de limitations des (valeurs des) paramètres de conception peuvent être imposées.

Modélisation mathématique avec optimisation, 1ère partie 8:51
Transformer une description de problème en programme mathématique pouvant être résolu par l'intermédiaire de l'optimisation, en utilisant un exemple d'usine de production d'énergie thermique et électrique.

Modélisation mathématique avec optimisation, 2ème partie 10:46
Résoudre un programme linéaire en utilisant les solveurs d'Optimization Toolbox™, en utilisant un exemple d'usine de production d'énergie thermique et électrique.

Utilisation de l’application Optimization

L’accès aux fonctions de l’Optimization Toolbox et aux options du solveur de façon peut se faire sous forme de programmes ou par l’intermédiaire de l’application ‘Optimization’.

L’application ‘Optimization’ simplifie les tâches communes d’optimisation, à savoir:

  • Sélectionner un solveur et définir un problème d’optimisation
  • Définir et inspecter les options d’optimisation et leurs valeurs par défaut
  • Lancer la résolution de problèmes et visualiser les résultats intermédiaires et finaux
  • Consulter la documentation du solveur dans une fenêtre optionnelle de recherche rapide
  • Importer et exporter les définitions de problème, les options d’algorithme et les résultats entre l’espace de travail MATLAB® et l’application
  • Générer automatiquement le code MATLAB pour enregistrer le travail et automatiser les tâches
  • Accéder aux solveurs de la Global Optimization Toolbox

Introduction à Optimization Tool 6:08
Configurez et exécutez des problèmes d'optimisation puis visualisez les résultats intermédiaires et finaux.

Choix d’un solveur

L’Optimization Toolbox propose différents solveurs pour différents types d’objectifs et de contraintes. Un tableau d’aide à la décision (Optimization Decision Table), assiste le choix du solveur le plus adapté à votre problème.

Paramétrage d’options

Les options du solveur vous permettent de mettre au point ou de modifier le processus d’optimisation et de visualiser la progression du solveur. Le paramétrage d’options peut être effectué sous forme de programme ou par l’intermédiaire de l’application ‘Optimization’.

Setting Options for Optimizations 4:48
Set options with optimoptions in Optimization Toolbox TM to tune solvers and monitor optimization progress.

Optimisation non-linéaire

L’Optimization Toolbox™ fournit des algorithmes utilisés pour la résolution de problèmes de programmation non linéaire dans MATLAB. Elle englobe des solveurs pour l’optimisation linéaire avec/sans contraintes ainsi que des solveurs pour de l’optimisation par moindres carrés.

Optimisation non linéaire sans contrainte

L’Optimization Toolbox utilise trois algorithmes pour résoudre les problèmes de minimisation non linéaire sans contrainte :

  • L’algorithme Quasi-Newton utilise une procédure mixte par recherche de ligne quadratique et cubique, ainsi que la formule de Broyden-Fletcher-Goldfarb-Shanno (BFGS) pour actualiser l’approximation de la matrice Hessienne.
  • L’algorithme Nelder-Mead (ou downhill simplex) est une méthode de recherche directe qui utilise exclusivement les valeurs de fonction (elle n’exige pas de dérivées) et traite les fonctions-objectives non lisses. La Global Optimization Toolbox propose des algorithmes d’optimisation sans dérivée supplémentaires.
  • L’algorithme zone de confiance est appliqué dans le cas de problèmes sans contraintes non linéaires et est particulièrement utile pour les problèmes à grande échelle pour lesquels il est possible d’exploiter la faible dispersion ou la structure.
Ermittlung der optimalen Effizienz in einem Motorkennfeld durch nichtlineare Optimierung ohne Nebenbedingungen.

Optimisation non linéaire sans contrainte de recherche du pic d’efficacité dans un map de performance de moteur

Optimisation non linéaire avec contrainte

Les problèmes d’optimisation non linéaire avec contrainte se composent de fonction objective linéaire ou non linéaire et peuvent être soumis à des contraintes linéaires et non linéaires. L’Optimization Toolbox utilise quatre algorithmes pour résoudre ces problèmes :

  • L’algorithme point intérieur (interior-point) est utilisé pour l’optimisation non linéaire générale. Particulièrement utile pour les problèmes grande échelle avec structure ou une faible dispersion, il tolère les échecs des objectifs définis par l’utilisateur et des fonctions de contraintes. cet algorithme utilise une fonction ‘barrière’ et assure, le cas échéant, la faisabilité de toutes les itérations par rapport aux limites durant l’optimisation.
  • L’algorithme SQP est utilisé pour l’optimisation non linéaire générale. Il respecte les limites de toutes les itérations et supporte les échecs d’objectifs définis par l’utilisateur et de fonctions de contraintes.
  • L’algorithme ensemble actif (active-set) est utilisé pour l’optimisation non linéaire générale.
  • L’algorithme de zone de confiance réflexif (trust-region reflective) est uniquement utilisé pour les problèmes avec contraintes liées ou d’égalités linéaires. Il est particulièrement utile pour les problèmes à grande échelle.

Les algorithmes point intérieur et zone de confiance réflexif vous permettent d’estimer les matrices Hessiennes en utilisant différentes approches.

Pour l’algorithme point intérieur:

  • BFGS (dense)
  • BFGS à mémoire limitée (pour les problèmes à grande échelle)
  • Fonction de multiplication Hessienne
  • Hessien réel (à faible ou haute dispersion)
  • Différence de gradients finie, sans connaissance à priori de la dispersion et structure

Pour l’algorithme de zone de confiance réflexif:

  • Différence de gradients finie, structure de dispersion de la matrice Hessienne
  • Hessien réel (à faible ou haute densité)
  • Fonction de multiplication Hessienne

De plus, ces algorithmes vous permettent de calculer, en une seule fonction, les multiplications entre les vecteurs temporels-Hessiens, sans besoin de définir explicitement la matrice Hessienne.

Optimisation non linéaire avec contraintes utilisée pour concevoir un système de suspension optimal
Optimisation non linéaire avec contraintes utilisée pour concevoir un système de suspension optimal

Programmation linéaire et quadratique

L’Optimization Toolbox peut résoudre des problèmes de programmation linéaires et quadratiques à grande échelle.

Programmation linéaire

Les problèmes de programmation linéaire impliquent la minimisation ou maximisation d’une fonction-objectif linéaire avec limites, égalité linéaire et contraintes d’inégalité. La programmation linéaire est utilisée en finance, en énergie, en recherche opérationnelle et dans d’autres applications dans lesquelles les relations entre variables peuvent être exprimées de façon linéaire.

L’Optimization Toolbox propose trois algorithmes utilisés pour résoudre les problèmes de programmation linéaires :

  • L’algorithme simplex est une procédure systématique (la plus utilisée) servant à générer et tester les solutions applicables à un programme linéaire.
  • L’algorithme point intérieur, qui repose sur un algorithme ‘primal-dual’ de type prédicteur-correcteur. La méthode point intérieur est particulièrement utile pour les problèmes à grande échelle avec structure ou définis par des matrices de dispersion.
  • L’algorithme ensemble actif (active-set) minimise l’objectif à chaque itération de l’ensemble actif (ou sous-ensemble de contraintes actives localement) jusqu’à ce qu’une solution soit atteinte.
Programmation linéaire utilisée dans la conception d’une usine de production d’énergie thermique et électrique
Programmation linéaire utilisée dans la conception d’une usine de production d’énergie thermique et électrique

Programmation quadratique

La programmation quadratique implique la minimisation d’une fonction quadratique multi variée soumise à des contraintes de limite, d’égalité et d’inégalité linéaire. La programmation quadratique est utilisée pour l’optimisation de portefeuille en finance, pour l’optimisation de la génération d’énergie dans les infrastructures électriques, pour l’optimisation de conceptions dans l’ingénierie et dans d’autres applications.

L’Optimization Toolbox inclut trois algorithmes pour la résolution des problèmes de programmation quadratique :

  • L’algorithme de point intérieur convexe résout les problèmes convexes avec n’importe quelle combinaison de contraintes.
  • L’algorithme de zone de confiance réflexif résout les problèmes avec contraintes liées ou d’égalités linéaires.
  • L’algorithme ensemble actif résout les problèmes soumis à n’importe quelle combinaison de contraintes.

Optimization in MATLAB: An Introduction to Quadratic Programming 36:35
In this webinar, you will learn how MATLAB can be used to solve optimization problems using an example quadratic optimization problem and the symbolic math tools in MATLAB.

Les algorithmes point intérieur convexe et zone de confiance réflexif sont à grande échelle, et donc peuvent gérer des problèmes ‘rares’. De plus, l’algorithme point intérieur convexe incorpore des routines d’algèbre linéaire optimisées ainsi qu’un nouveau module de pré-résolution qui peut améliorer la vitesse, la stabilité numérique et la détection d’infaisabilité.

Programmation quadratique utilisée pour effectuer une analyse de rendements de trois fonds de placement communs différents.
Programmation quadratique utilisée pour effectuer une analyse de rendements de trois fonds de placement communs différents.

Programmation linéaire d’entiers mixtes

La programmation linéaire d’entiers mixtes étend le problème de programmation linéaire avec la contrainte supplémentaire que certaines ou toutes les variables de la solution optimale doivent être des entiers.

Pour certains problèmes d’optimisation, les variables ne peuvent pas avoir une forme décimale. Par exemple, si une variable représente le nombre de parts de marché à acheter, elle ne peut être que entière. De la même manière, si une variable représente l’état activé/désactivé d’un générateur, elle doit uniquement prendre en charge des valeurs binaires (0 ou 1). Le problème de programmation linéaire d’entiers mixtes permet de modéliser ce comportement en ajoutant une contrainte stipulant que les variables doivent uniquement prendre en compte des nombres entiers dans la solution optimale.

Programmation linéaire en nombre entier mixte 34:08
Apprenez à utiliser le nouveau solver d'optimisation à programmation linéaire en nombre entier mixte de la Version R2014a. Ce nouveau solver vous permet de résoudre des problèmes d'optimisation dans lequel une partie ou toutes les variables sont contraintes à prendre des valeurs entières.

L’Optimization Toolbox résout les problèmes de programmation linéaire d’entiers mixtes en utilisant un algorithme qui:

  • Lance un prétraitement de programmation d’entiers pour limiter la région dite ‘faisable’
  • Applique des plans de coupe pour réduire la région faisable
  • Utilise l’heuristique pour trouver des solutions d’entier faisables
  • Vérifie qu’il n’existe aucune autre solution faisable grâce à un algorithme de séparation et d’évaluation qui résout une série de problèmes de programmation linéaire par relaxation
Utilisation d’un problème de programmation d’entier pour déterminer les investissements à réaliser
Utilisation d’un problème de programmation d’entier pour déterminer les investissements à réaliser

Déploiement

Vous pouvez utiliser les solveurs de l’Optimization Toolbox avec MATLAB Compiler™ afin de créer et partager des outils d’aides à la décision avec des utilisateurs qui n’ont pas MATLAB. Ces applications indépendantes peuvent être déployées gratuitement à un nombre illimité d’utilisateurs. Vous pouvez également intégrer les algorithmes d’optimisation MATLAB avec d’autres langues, telles que Java® et .NET, en utilisant les différents MATLAB Builder™.

Optimisation multi-objectif

L’optimisation multi-objectif cherche à minimiser plusieurs fonctions-objectifs soumises à un ensemble de contraintes. Deux types de formulations multi-objectif sont supportés:

  • Les problèmes de type ‘goal attainment’ (ou atteinte d’objectifs) visant à réduire la valeur d’une fonction vectorielle linéaire ou non linéaire pour atteindre les résultats attendus prédéfinis dans un vecteur objectif. L’importance relative des objectifs est décrite dans un vecteur de pondération. Le problème d’atteinte d’objectifs peut également être soumis à des contraintes linéaires et non linéaires.
  • Le problème minimax implique la minimisation du cas extrême pour un ensemble de fonctions multi variées, pouvant être soumises à des contraintes linéaires et non linéaires.

L’Optimization Toolbox transforme les deux types de problèmes multi-objectifs en problèmes d’optimisation standard sous contraintes puis les résout en utilisant une approche ensemble actif (ou active-set).

La Global Optimization Toolbox inclut un solveur multi-objectif supplémentaire pour les problèmes de type ‘non lisses’.

Optimisation multi-objectif pour la conception d’un filtre passe-bas.
Optimisation multi-objectif pour la conception d’un filtre passe-bas.

Moindres carrés non linéaires, ajustement de données et équations non linéaires

L’Optimization Toolbox peut : résoudre des problèmes linéaires et non linéaires par moindres carrés, réaliser des ajustements des données et résoudre des équations non linéaires.

Optimisation par moindres carrés linéaire et non linéaire

Deux algorithmes sont proposés pour résoudre des problèmes de moindres carrés linéaires avec contraintes :

  • L’algorithme ensemble actif est utilisé pour résoudre des problèmes soumis à des limites et inégalités ou égalités linéaires.
  • L’algorithme de zone de confiance réflexif sert à résoudre des problèmes à grande échelle qui ont uniquement des contraintes sous limites.

La boîte à outils utilise deux algorithmes pour résoudre les problèmes de moindres carrés non linéaires :

  • L’algorithme de zone de confiance réflexif met en œuvre l’algorithme de Levenberg-Marquardt en utilisant une approche par zone de confiance. Il est utilisé pour les problèmes sans contrainte ou les problèmes avec contraintes aux limites.
  • L’algorithme Levenberg-Marquardt met en œuvre une méthode Levenberg-Marquardt standard. Il est utilisé pour les problèmes sans contrainte.
Ajuster une équation transcendante en utilisant les moindres carrés non linéaires
Ajuster une équation transcendante en utilisant les moindres carrés non linéaires

Ajustement des données

La toolbox propose une application/interface spécialisée aux problèmes d’ajustement de données, pour lesquels vous recherchez parmi une famille de fonctions non-linéaires, le meilleur candidat correspondant à l’ensemble de points de données. Les mêmes algorithmes que pour les problèmes de moindres carrés non linéaires sont utilisés.

Ajuster une équation exponentielle non linéaire par ajustement de courbes aux moindres carrés.
Ajuster une équation exponentielle non linéaire par ajustement de courbes aux moindres carrés.

Résolution d’équations non linéaires

L’Optimization Toolbox utilise un algorithme de zone de confiance en zigzag (‘dogleg trust-region’) permettant de résoudre un système d’équations non linéaires avec autant d’équations que d’inconnues. La toolbox peut également résoudre ce problème en utilisant les algorithmes de zone de confiance dit ‘réflexifs’ et de Levenberg-Marquardt.

Résolution d’une fonction Rosenbrock à <i>n</i> dimensions en utilisant le solveur d’équations non linéaires.
Résolution d’une fonction Rosenbrock à n dimensions en utilisant le solveur d’équations non linéaires.

Calcul parallèle et dérivées

Les solveurs de l’Optimization Toolbox pour problèmes non linéaires, utilisent des méthodes basées sur les gradients pour minimiser ou maximiser un objectif. Les informations sur le gradient de la fonction objective peuvent être estimées en utilisant des différences finies, ou apportées au solveur par l’utilisateur.

Calcul parallèle

L’Optimization Toolbox peut être utilisé par la Parallel Computing Toolbox pour paralléliser la résolution de certains problèmes. Le parallélisme permet de gagner significativement en temps de résolution, soit par activation du calcul parallèle intégré/local ou en définissant un déploiement personnalisé propre à votre problème d’optimisation.

En local, la possibilité de calcul parallèle avec l’Optimization Toolbox, vous permet d’accélérer l’estimation du pas de gradient des solveurs sélectionnés, pour les problèmes d’optimisation non linéaire avec contrainte et les problèmes du type atteinte d’objectifs, multi-objectifs et minimax.

Accélération du temps de résolution pour un problème électrostatique par calcul parallèle via un solveur d’optimisation non linéaire. La fonction intégrée est activée en spécifiant l’option <tt>UseParallel</tt> (à gauche) pour les fonctions-objectifs (au milieu à droite) et fonctions de contraintes (en bas à droite). La solution est affichée en haut à droite.
Accélération du temps de résolution pour un problème électrostatique par calcul parallèle via un solveur d’optimisation non linéaire. La fonction intégrée est activée en spécifiant l’option UseParallel (à gauche) pour les fonctions-objectifs (au milieu à droite) et fonctions de contraintes (en bas à droite). La solution est affichée en haut à droite.

Vous pouvez personnaliser une implémentation de calcul parallèle en définissant explicitement dans le problème d’optimisation d’utiliser la fonction de parallélisme. Vous pouvez définir dans une fonction-objectif ou une fonction de contrainte de réaliser un calcul parallèle, ce qui vous permet de réduire le temps requis pour évaluer l’objectif ou la contrainte.

Accélération du temps de résolution (en haut à droite) pour la conception de système de suspension (en bas à gauche et en bas à droite) avec incertitude en personnalisant la fonction objective via une simple modification d’une seule ligne de code (en haut à gauche).
Accélération du temps de résolution (en haut à droite) pour la conception de système de suspension (en bas à gauche et en bas à droite) avec incertitude en personnalisant la fonction objective via une simple modification d’une seule ligne de code (en haut à gauche).

Accélération des problèmes d'optimisation à l'aide du traitement parallèle 55:41
Résolvez plus rapidement les problèmes d'optimisation à l'aide de Parallel Computing Toolbox.

Calcul/estimation des dérivées

Les solveurs de l’Optimization Toolbox minimisent les fonctions non linéaires en estimant les dérivées partielles de la fonction objective par différences finies. Vous pouvez également définir les fonctions de calcul des valeurs des dérivées partielles, réduisant ainsi de manière significative, les coûts ‘liés’ à l’estimation de la dérivée.

Le calcul des dérivées partielles d’une fonction objective peut s’avérer fastidieux. En exprimant le problème de façon symbolique en utilisant la Symbolic Math Toolbox™, vous pouvez utiliser des fonctions intégrées pour calculer automatiquement les dérivées partielles de la fonction objective. Un code MATLAB peut ensuite être généré et être utilisé avec les solveurs de l’Optimization Toolbox.

Optimisation à l’aide de dérivées symboliques (Article technique)

Essayer Optimization Toolbox

Obtenir une version d'évaluation

Améliorez la performance de systèmes complexes avec Simulink et SimEvents

Visionner le webinar