optimisation mathématique

Considérons la notation suivante :

Cela désigne la valeur minimale de la fonction objectif , lorsqu'on choisit

De même, la notation

On demande la valeur maximale de la fonction objectif où

Considérons la notation suivante :

ou de manière équivalente

Cela représente la ou les valeurs de l' argument qui minimisent la fonction objectif (la valeur minimale réelle de cette fonction n'est pas celle demandée par le problème). Dans ce cas, la réponse est , car dire qu'il n'appartient pas à l' ensemble des solutions admissibles .

De la même manière,

ou de manière équivalente

représente la paire (ou les paires) qui maximise (ou maximise) la valeur de la fonction objectif , avec la contrainte supplémentaire que (là encore, la valeur maximale exacte de l'expression n'a pas d'importance). Dans ce cas, les solutions sont les paires de la forme } et } , où et et B. Dantzig , bien qu’une grande partie de la théorie ait été introduite par Leonid Kantorovich en 1939. ( Dans ce contexte, le terme « programmation » ne désigne pas la programmation informatique , mais provient de l’usage qu’en faisait l’ armée américaine pour désigner les plans d’entraînement et de logistique proposés , problèmes que Dantzig étudiait à l’époque.) Dantzig publia l’ algorithme du simplexe en 1947, et John von Neumann ainsi que d’autres chercheurs travaillèrent sur les aspects théoriques de la programmation linéaire (comme la théorie de la dualité ) à peu près à la même époque.

Parmi les autres chercheurs notables en optimisation mathématique, on peut citer :

Ajouter plusieurs objectifs à un problème d'optimisation le complexifie. Par exemple, pour optimiser une structure, on recherche une structure à la fois légère et rigide. Lorsque deux objectifs sont contradictoires, un compromis doit être trouvé. Il peut exister une structure la plus légère, une structure la plus rigide, et une infinité de structures représentant un compromis entre poids et rigidité. L'ensemble des structures optimales, qui améliorent un critère au détriment d'un autre, est appelé ensemble de Pareto . La courbe représentant le poids en fonction de la rigidité des meilleures structures est appelée frontière de Pareto .

Un plan est considéré comme « Pareto optimal » (ou, de manière équivalente, « Pareto efficace » ou appartenant à l'ensemble de Pareto) s'il n'est dominé par aucun autre plan : s'il est pire qu'un autre plan à certains égards et pas meilleur à aucun autre égard, alors il est dominé et n'est pas Pareto optimal.

Le choix de la solution optimale au sens de Pareto parmi les solutions retenues est laissé au décideur. Autrement dit, formuler le problème comme une optimisation multiobjectif indique qu'il manque des informations : les objectifs souhaitables sont donnés, mais leurs combinaisons ne sont pas hiérarchisées. Dans certains cas, ces informations manquantes peuvent être obtenues par des échanges avec le décideur.

Les problèmes d'optimisation multi-objectifs ont été généralisés davantage en problèmes d'optimisation vectorielle où l'ordre (partiel) n'est plus donné par l'ordre de Pareto.

Les problèmes d'optimisation sont souvent multimodaux ; autrement dit, ils admettent plusieurs solutions satisfaisantes. Ces solutions peuvent toutes être globalement satisfaisantes (même valeur de fonction de coût) ou il peut exister un mélange de solutions globalement et localement satisfaisantes. L'objectif d'un optimiseur multimodal est d'obtenir toutes (ou au moins une partie) de ces solutions multiples.

Les techniques d'optimisation classiques, du fait de leur approche itérative, ne donnent pas de résultats satisfaisants lorsqu'elles sont utilisées pour obtenir plusieurs solutions, car il n'est pas garanti que des solutions différentes seront obtenues même avec des points de départ différents lors de plusieurs exécutions de l'algorithme.

Les approches courantes des problèmes d'optimisation globale , où plusieurs extrema locaux peuvent être présents, comprennent les algorithmes évolutionnaires , l'optimisation bayésienne et le recuit simulé .

Le problème de satisfaisabilité , également appelé problème de faisabilité , consiste simplement à trouver une solution réalisable quelconque , indépendamment de la valeur de la fonction objectif. On peut le considérer comme un cas particulier d'optimisation mathématique où la valeur de la fonction objectif est identique pour toute solution, et où, par conséquent, toute solution est optimale.

De nombreux algorithmes d'optimisation nécessitent un point de départ admissible. Une méthode pour obtenir ce point consiste à assouplir les conditions d'admissibilité à l'aide d'une variable d'écart ; avec un écart suffisant, tout point de départ devient admissible. Il faut ensuite minimiser cette variable d'écart jusqu'à ce qu'elle soit nulle ou négative.

Le théorème des valeurs extrêmes de Karl Weierstrass stipule qu'une fonction continue à valeurs réelles sur un compact atteint ses valeurs maximales et minimales. Plus généralement, une fonction semi-continue inférieurement sur un compact atteint son minimum ; une fonction semi-continue supérieurement sur un compact atteint son maximum.

Un des théorèmes de Fermat stipule que les optima des problèmes non contraints se trouvent aux points stationnaires , où la dérivée première ou le gradient de la fonction objectif est nul (voir le test de la dérivée première ). Plus généralement, ils peuvent se trouver aux points critiques , où la dérivée première ou le gradient de la fonction objectif est nul ou indéfini, ou encore à la frontière de l'ensemble des solutions possibles. Une équation (ou un ensemble d'équations) affirmant que la ou les dérivées premières sont nulles en un optimum intérieur est appelée « condition du premier ordre » ou ensemble de conditions du premier ordre.

Les optima des problèmes avec contraintes d'égalité peuvent être trouvés par la méthode des multiplicateurs de Lagrange . Les optima des problèmes avec contraintes d'égalité et/ou d'inégalité peuvent être trouvés à l'aide des conditions de Karush-Kuhn-Tucker .

Bien que le test de la dérivée première permette d'identifier les points susceptibles d'être des extrema, il ne distingue pas un minimum d'un maximum ou d'un point qui n'est ni l'un ni l'autre. Lorsque la fonction objectif est deux fois différentiable, ces cas peuvent être distingués en vérifiant la dérivée seconde ou la matrice des dérivées secondes (appelée matrice hessienne ) dans les problèmes sans contraintes, ou la matrice des dérivées secondes de la fonction objectif et des contraintes (appelée matrice hessienne bordée ) dans les problèmes avec contraintes. Les conditions qui distinguent les maxima, ou les minima, des autres points stationnaires sont appelées « conditions du second ordre » (voir « Test de la dérivée seconde »). Si une solution candidate satisfait les conditions du premier ordre, la satisfaction des conditions du second ordre suffit à établir au moins l'optimalité locale.

Le théorème de l'enveloppe décrit comment la valeur d'une solution optimale évolue lorsqu'un paramètre sous-jacent change. Le processus de calcul de cette évolution est appelé statique comparative .

Le théorème du maximum de Claude Berge (1963) décrit la continuité d'une solution optimale en fonction des paramètres sous-jacents.

Pour les problèmes sans contrainte avec des fonctions deux fois différentiables, certains points critiques peuvent être identifiés en trouvant les points où le gradient de la fonction objectif est nul (c'est-à-dire les points stationnaires). Plus généralement, un sous-gradient nul indique qu'un minimum local a été trouvé pour les problèmes de minimisation avec des fonctions convexes et d'autres fonctions localement lipschitziennes , qui convergent lors de la minimisation de la fonction de perte du réseau de neurones. L'estimation du moment positif-négatif permet d'éviter le minimum local et de converger vers le minimum global de la fonction objectif.

De plus, les points critiques peuvent être classés en fonction de la définition de la matrice hessienne : si la matrice hessienne est définie positive en un point critique, alors le point est un minimum local ; si la matrice hessienne est définie négative, alors le point est un maximum local ; enfin, si elle est indéfinie, alors le point est une sorte de point selle .

Les problèmes avec contraintes peuvent souvent être transformés en problèmes sans contraintes grâce aux multiplicateurs de Lagrange . La relaxation lagrangienne peut également fournir des solutions approchées à des problèmes avec contraintes complexes.

Lorsque la fonction objectif est convexe , tout minimum local est également un minimum global. Il existe des techniques numériques efficaces pour minimiser les fonctions convexes, telles que les méthodes de points intérieurs .

Plus généralement, si la fonction objectif n'est pas quadratique, de nombreuses méthodes d'optimisation utilisent d'autres techniques pour garantir la convergence d'une sous-suite d'itérations vers une solution optimale. La première méthode, encore largement répandue, repose sur la recherche linéaire , qui optimise une fonction selon une dimension. Une seconde méthode, de plus en plus utilisée, utilise les régions de confiance . La recherche linéaire et les régions de confiance sont toutes deux employées dans les méthodes modernes d' optimisation non différentiable . Un optimiseur global étant généralement beaucoup plus lent qu'un optimiseur local avancé (comme BFGS ), on peut souvent obtenir un optimiseur global efficace en initialisant l'optimiseur local à partir de différents points de départ.

Les méthodes itératives utilisées pour résoudre les problèmes de programmation non linéaire diffèrent selon qu'elles évaluent la matrice hessienne , le gradient ou uniquement les valeurs de la fonction. Si l'évaluation de la matrice hessienne (H) et du gradient (G) améliore la vitesse de convergence, pour les fonctions pour lesquelles ces quantités existent et varient de manière suffisamment continue, ces évaluations augmentent la complexité de calcul (ou le coût de calcul) de chaque itération. Dans certains cas, cette complexité peut devenir excessive.

Un critère majeur pour les optimiseurs est le nombre d'évaluations de fonction requises, car cela représente souvent un effort de calcul considérable, généralement bien supérieur à celui de l'optimiseur lui-même, qui opère principalement sur les N variables. Les dérivées fournissent des informations détaillées à ces optimiseurs, mais sont encore plus difficiles à calculer ; par exemple, l'approximation du gradient nécessite au moins N+1 évaluations de fonction. Pour les approximations des dérivées secondes (regroupées dans la matrice hessienne), le nombre d'évaluations de fonction est de l'ordre de N². La méthode de Newton requiert les dérivées secondes ; ainsi, à chaque itération, le nombre d'appels de fonction est de l'ordre de N², tandis que pour un optimiseur de gradient pur plus simple, il n'est que de N. Cependant, les optimiseurs de gradient nécessitent généralement plus d'itérations que l'algorithme de Newton. Le choix de la méthode la plus performante en termes de nombre d'appels de fonction dépend du problème lui-même.

• Méthodes d'évaluation des matrices hessiennes (ou d'approximation des matrices hessiennes, par différences finies ) :
  • La méthode de Newton
  • Programmation quadratique séquentielle : une méthode de type Newton pour les problèmes contraints de petite et moyenne taille . Certaines versions peuvent traiter des problèmes de grande dimension.
  • Méthodes de points intérieurs : Il s'agit d'une vaste classe de méthodes d'optimisation sous contraintes, dont certaines utilisent uniquement des informations de (sous-)gradient et d'autres nécessitent l'évaluation des hessiennes.
• Méthodes qui évaluent les gradients, ou qui les approximent d'une manière ou d'une autre (ou même des sous-gradients) :
  • Méthodes de descente de coordonnées : algorithmes qui mettent à jour une seule coordonnée à chaque itération.
  • Méthodes du gradient conjugué : méthodes itératives pour les problèmes de grande taille. (En théorie, ces méthodes convergent en un nombre fini d’étapes avec des fonctions objectives quadratiques, mais cette convergence n’est pas observée en pratique sur les ordinateurs à précision finie.)
  • Descente de gradient (ou « descente la plus raide » ou « ascension la plus raide ») : une méthode (lente) d'intérêt historique et théorique, qui a connu un regain d'intérêt pour la recherche de solutions approximatives à d'énormes problèmes.
  • Méthodes de sous-gradient : une méthode itérative pour les grandes fonctions localement lipschitziennes utilisant des gradients généralisés . D'après Boris T. Polyak, les méthodes de sous-gradient-projection sont similaires aux méthodes de gradient conjugué.
  • Méthode de descente par faisceaux : une méthode itérative pour les problèmes de petite à moyenne taille avec des fonctions localement lipschitziennes, en particulier pour les problèmes de minimisation convexe (similaire aux méthodes de gradient conjugué).
  • Méthode de l'ellipsoïde : Méthode itérative adaptée aux petits problèmes à fonction objectif quasi-convexe , présentant un grand intérêt théorique, notamment pour établir la complexité polynomiale de certains problèmes d'optimisation combinatoire. Elle présente des similarités avec les méthodes quasi-Newton.
  • La méthode du gradient conditionnel (Frank-Wolfe) est utilisée pour la minimisation approchée de problèmes structurés avec contraintes linéaires , notamment les réseaux de trafic. Pour les problèmes généraux sans contraintes, cette méthode se réduit à la méthode du gradient classique, considérée comme obsolète (pour la quasi-totalité des problèmes).
  • Méthodes quasi-Newton : Méthodes itératives pour les problèmes de taille moyenne à grande (par exemple N<1000).
  • Méthode d'approximation stochastique par perturbation simultanée (SPSA) pour l'optimisation stochastique ; utilise une approximation de gradient aléatoire (efficace).
• Méthodes qui évaluent uniquement les valeurs de la fonction : si un problème est continûment différentiable, alors les gradients peuvent être approximés à l’aide de différences finies, auquel cas une méthode basée sur le gradient peut être utilisée.
  • Méthodes d'interpolation
  • Les méthodes de recherche de motifs , qui ont de meilleures propriétés de convergence que l' heuristique de Nelder-Mead (avec simplexes) , sont énumérées ci-dessous.
  • Descente en miroir

Les problèmes de dynamique des corps rigides (en particulier des corps rigides articulés) nécessitent souvent des techniques de programmation mathématique, car on peut considérer la dynamique des corps rigides comme la résolution d'une équation différentielle ordinaire sur une variété contrainte ; les contraintes sont diverses contraintes géométriques non linéaires telles que « ces deux points doivent toujours coïncider », « cette surface ne doit pénétrer aucune autre » ou « ce point doit toujours se situer quelque part sur cette courbe ». De plus, le calcul des forces de contact peut être abordé en résolvant un problème de complémentarité linéaire , qui peut également être vu comme un problème de programmation quadratique (PQ).

De nombreux problèmes de conception peuvent être formulés sous forme de programmes d'optimisation. Cette application est appelée optimisation de conception. L' optimisation en ingénierie en est un sous-ensemble, tandis que l'optimisation de conception multidisciplinaire , un sous-ensemble plus récent et en pleine expansion , a été particulièrement appliquée aux problèmes d'ingénierie aérospatiale .

Cette approche peut être appliquée en cosmologie et en astrophysique.

L'économie est si étroitement liée à l'optimisation des agents qu'une définition influente la décrit comme « l'étude du comportement humain en tant que relation entre des fins et des moyens rares », avec des applications alternatives. La théorie moderne de l'optimisation englobe la théorie traditionnelle, mais recoupe également la théorie des jeux et l'étude des équilibres économiques . Le Journal of Economic Literature ( JEL) classe la programmation mathématique, les techniques d'optimisation et les sujets connexes sous les codes JEL : C61-C63 .

En microéconomie, le problème de maximisation de l'utilité et son dual , le problème de minimisation des dépenses , sont des problèmes d'optimisation économique. Dans la mesure où leur comportement est cohérent, on suppose que les consommateurs maximisent leur utilité , tandis que les entreprises maximisent généralement leur profit . De plus, les agents sont souvent modélisés comme étant averses au risque , préférant ainsi l'éviter. Les prix des actifs sont également modélisés à l'aide de la théorie de l'optimisation, bien que les calculs mathématiques sous-jacents reposent sur l'optimisation de processus stochastiques plutôt que sur l'optimisation statique. La théorie du commerce international utilise également l'optimisation pour expliquer les échanges commerciaux entre les nations. L'optimisation de portefeuilles est un exemple d'optimisation multi-objectif en économie.

Depuis les années 1970, les économistes modélisent les décisions dynamiques dans le temps à l'aide de la théorie du contrôle . Par exemple, les modèles de recherche dynamique servent à étudier le comportement du marché du travail . Une distinction cruciale s'opère entre les modèles déterministes et les modèles stochastiques . Les macroéconomistes élaborent des modèles d'équilibre général stochastique dynamique (EGSD) qui décrivent la dynamique de l'ensemble de l'économie comme le résultat des décisions d'optimisation interdépendantes des travailleurs, des consommateurs, des investisseurs et des gouvernements

Parmi les applications courantes des techniques d'optimisation en génie électrique, on peut citer la conception de filtres actifs , la réduction des champs parasites dans les systèmes de stockage d'énergie magnétique supraconducteurs, la conception par cartographie spatiale des structures micro-ondes , les antennes de téléphones portables et la conception basée sur l'électromagnétisme. L'optimisation de la conception des composants et antennes micro-ondes, validée électromagnétiquement, a largement recours à un modèle de substitution physique ou empirique approprié et à des méthodologies de cartographie spatiale depuis la découverte de cette dernière en 1993 Les techniques d'optimisation sont également utilisées dans l'analyse des flux de puissance .

L'optimisation est largement utilisée en génie civil. La gestion de la construction et le génie des transports figurent parmi les principales branches du génie civil qui s'appuient fortement sur l'optimisation. Les problèmes de génie civil les plus courants résolus par l'optimisation sont les travaux de terrassement routier, l'analyse du cycle de vie des ouvrages et infrastructures , le nivellement des ressources , la répartition des ressources en eau , la gestion du trafic et l'optimisation des échéanciers.

Un autre domaine qui utilise largement les techniques d'optimisation est la recherche opérationnelle . Celle-ci recourt également à la modélisation et à la simulation stochastiques pour améliorer la prise de décision. De plus en plus, la recherche opérationnelle utilise la programmation stochastique pour modéliser des décisions dynamiques qui s'adaptent aux événements ; ces problèmes peuvent être résolus par des méthodes d'optimisation à grande échelle et d'optimisation stochastique .

L'optimisation mathématique est largement utilisée dans la conception des systèmes de contrôle modernes. Les systèmes de contrôle de haut niveau, tels que la commande prédictive (MPC) ou l'optimisation en temps réel (RTO), font appel à l'optimisation mathématique. Ces algorithmes s'exécutent en ligne et déterminent de manière itérative les valeurs des variables de décision, comme l'ouverture des vannes d'étranglement dans une installation de traitement, en résolvant un problème d'optimisation mathématique intégrant des contraintes et un modèle du système à contrôler.

Les techniques d'optimisation sont couramment utilisées pour l'estimation des paramètres géophysiques . À partir d'un ensemble de mesures géophysiques, comme des enregistrements sismiques , il est fréquent de déterminer les propriétés physiques et la géométrie des roches et fluides sous-jacents. La plupart des problèmes en géophysique sont non linéaires, et les méthodes déterministes comme stochastiques sont largement employées.

Les techniques d'optimisation sont utilisées dans de nombreux domaines de la biologie des systèmes computationnels, tels que la modélisation, la conception expérimentale optimale, l'ingénierie métabolique et la biologie synthétique. La programmation linéaire a été appliquée pour calculer les rendements maximaux possibles des produits de fermentation et pour inférer les réseaux de régulation génique à partir de multiples jeux de données de puces à ADN , ainsi que les réseaux de régulation transcriptionnelle à partir de données à haut débit. La programmation non linéaire a été utilisée pour analyser le métabolisme énergétique et a été appliquée à l'ingénierie métabolique et à l'estimation des paramètres des voies biochimiques.