Optimisation convexe

L'optimisation convexe est l'étude de la minimisation de fonctions convexes sur des ensembles convexes, une classe de problèmes pour laquelle les optima locaux sont globaux et des algorithmes efficaces existent.

Definition

Un problème d'optimisation convexe minimise une fonction objectif convexe sous des contraintes d'inégalité convexes et des contraintes d'égalité affines ; l'ensemble admissible est convexe, ce qui garantit que tout minimum local est également un minimum global.

Scope

Ce domaine couvre les ensembles et fonctions convexes, la reconnaissance et la modélisation des problèmes convexes, les programmes linéaires, quadratiques, à cône de second ordre et semi-définis, la dualité lagrangienne et les conditions de Karush-Kuhn-Tucker pour les problèmes convexes, ainsi que les algorithmes de point intérieur et de premier ordre avec leurs garanties de complexité.

Core questions

• Comment un problème peut-il être reconnu ou reformulé comme convexe ?
• Pourquoi la convexité garantit-elle que les optima locaux sont globaux ?
• Que révèle la dualité sur un problème convexe et sa solution ?
• Quels algorithmes résolvent les problèmes convexes efficacement et avec quelles garanties ?

Key theories

Optimalité globale des problèmes convexes

Puisqu'une fonction convexe sur un ensemble convexe n'a pas de minima locaux superflus, tout point localement optimal est globalement optimal, rendant les problèmes convexes résolubles de manière fiable.

Dualité lagrangienne et conditions KKT

Chaque problème convexe a un problème dual associé fournissant des certificats d'optimalité, et sous certaines conditions de qualification des contraintes, les conditions de Karush-Kuhn-Tucker sont nécessaires et suffisantes pour l'optimalité.

Méthodes de point intérieur

Les méthodes de point intérieur suivent un chemin central à travers l'intérieur de la région admissible, résolvant des problèmes convexes, y compris les programmes semi-définis, en temps polynomial prouvable.

Clinical relevance

L'optimisation convexe est omniprésente dans l'apprentissage automatique, le traitement du signal et de l'image, le contrôle, la finance et la conception en ingénierie, car de nombreux problèmes d'estimation et de décision peuvent être formulés comme des programmes convexes et résolus de manière fiable à grande échelle.

History

Le domaine repose sur l'analyse convexe systématisée par Rockafellar vers 1970. La méthode de point intérieur de Karmarkar de 1984 et la théorie subséquente de Nesterov et Nemirovski ont montré que de larges classes de problèmes convexes sont solubles en temps polynomial, déclenchant l'approche moderne de l'optimisation convexe, axée sur la modélisation.

Key figures

• R. Tyrrell Rockafellar
• Stephen Boyd
• Yurii Nesterov
• Narendra Karmarkar

Seminal works

• boyd2004
• rockafellar1970

Frequently asked questions

Pourquoi préférer les modèles convexes lorsque c'est possible ?

Les problèmes convexes sont assortis d'une garantie que toute solution trouvée est globalement optimale et s'accompagnent d'algorithmes matures et efficaces. Les modèles non convexes peuvent piéger les solveurs dans des optima locaux inférieurs, c'est pourquoi une grande partie du travail appliqué consiste à reformuler les problèmes de manière convexe.

La programmation linéaire est-elle une forme d'optimisation convexe ?

Oui. Un programme linéaire minimise une fonction objectif linéaire sur un polyèdre, et les fonctions linéaires ainsi que les polyèdres sont convexes, donc la programmation linéaire est un cas particulier, particulièrement bien compris, de l'optimisation convexe.