Optimisation Mathématique
L'optimisation mathématique vise à trouver le meilleur élément, selon un certain objectif, parmi un ensemble d'alternatives réalisables, et fournit la théorie et les algorithmes pour y parvenir.
Definition
Un problème d'optimisation consiste à minimiser ou maximiser une fonction objectif sur un ensemble réalisable défini par des contraintes ; sa solution est un point réalisable où l'objectif atteint sa meilleure valeur, caractérisé par des conditions d'optimalité.
Scope
Ce domaine couvre l'optimisation sans contraintes et avec contraintes, la convexité et la dualité, la programmation linéaire, quadratique et non linéaire, les conditions d'optimalité de type Lagrange et Karush-Kuhn-Tucker, ainsi que les algorithmes, des méthodes du simplexe et des points intérieurs aux méthodes de gradient et de Newton, qui calculent les optima. Il s'étend à l'optimisation temporelle par le contrôle optimal.
Sub-topics
Core questions
- Un optimum existe-t-il, et est-il unique ou global ?
- Quelles conditions caractérisent un point optimal ?
- Comment la convexité rend-elle un problème traitable ?
- Quels algorithmes calculent les solutions de manière fiable et efficace ?
Key theories
- Conditions d'optimalité
- Les multiplicateurs de Lagrange et les conditions de Karush-Kuhn-Tucker caractérisent les optima sous contraintes par la stationnarité, la faisabilité et la complémentarité, généralisant la condition de gradient nul du cas sans contraintes.
- Convexité et dualité
- Pour les problèmes convexes, tout optimum local est global, et la dualité lagrangienne fournit des bornes et des certificats d'optimalité par le théorème de dualité forte.
- Algorithmes itératifs
- Les optima sont calculés par des schémas itératifs tels que les méthodes du simplexe et des points intérieurs pour les programmes linéaires et les méthodes de gradient, de Newton et de quasi-Newton pour les problèmes non linéaires, la convergence étant régie par la structure du problème.
Clinical relevance
L'optimisation est à la base de la recherche opérationnelle, de l'économie, de l'apprentissage automatique, de la conception en ingénierie, du contrôle et de la logistique, fournissant le cadre standard pour l'allocation des ressources, l'ajustement de modèles et la prise de décision sous contraintes.
History
L'optimisation a évolué à partir des multiplicateurs de Lagrange et du calcul des variations. La programmation linéaire a émergé dans les années 1940 avec les travaux de Kantorovich et Dantzig et la méthode du simplexe, les conditions de Kuhn-Tucker de 1951 ont unifié l'optimisation sous contraintes, et les méthodes des points intérieurs ont transformé le calcul à grande échelle à partir des années 1980.
Key figures
- Joseph-Louis Lagrange
- George Dantzig
- Leonid Kantorovich
- Harold Kuhn
- Albert Tucker
Related topics
Seminal works
- nocedal2006
- boyd2004
- bertsekas1999
Frequently asked questions
- Pourquoi la convexité est-elle si importante en optimisation ?
- Dans un problème convexe, tout minimum local est automatiquement un minimum global, et de puissantes garanties de dualité et algorithmiques s'appliquent. Cela rend les problèmes convexes résolubles de manière fiable, tandis que les problèmes non convexes généraux peuvent avoir de nombreux optima locaux et aucune garantie efficace de trouver le meilleur.
- Que sont les conditions de Karush-Kuhn-Tucker ?
- Ce sont les conditions nécessaires du premier ordre pour une solution d'un problème d'optimisation sous contraintes, généralisant les multiplicateurs de Lagrange aux contraintes d'inégalité. Elles combinent la stationnarité du Lagrangien, la faisabilité et une relation de complémentarité entre les multiplicateurs et les contraintes actives.