Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Optimisation convexe
Résumé
vignette|320x320px|Optimisation convexe dans un espace en deux dimensions dans un espace contraint
L'optimisation convexe est une sous-discipline de l'optimisation mathématique, dans laquelle le critère à minimiser est convexe et l'ensemble admissible est convexe. Ces problèmes sont plus simples à analyser et à résoudre que les problèmes d'optimisation non convexes, bien qu'ils puissent être NP-difficile (c'est le cas de l'optimisation copositive).
La théorie permettant d'analyser ces problèmes ne requiert pas la différentiabilité des fonctions. Cette généralité est motivée par le fait que certaines méthodes de construction de problèmes d'optimisation convexe conduisent à des problèmes non différentiables (fonction marginale, dualisation de contraintes, etc). Si cette généralité est un atout, permettant de prendre en compte davantage de problèmes, l'abord de la théorie est également plus difficile.
L'optimisation convexe repose sur l'analyse convexe.
L'optimisation convexe est un type d'optimisation mathématique, c'est-à-dire une discipline qui étudie des problèmes du type : optimiser une fonction donnée dans un espace donné.
Elle généralise l'optimisation linéaire et l'optimisation semi-définie positive, mais aussi l'optimisation conique et l'optimisation copositive.
Soit un espace vectoriel. Un problème d'optimisation convexe consiste à minimiser une fonction convexe sur , ce que l'on écrit d'une des manières suivantes :
Si on note
le domaine (effectif) de , le problème est identique à celui de minimiser sur :
Si , c'est-à-dire si , cette expression est encore valable puisque, par convention, . L'intérêt d'avoir une fonction pouvant prendre la valeur est donc d'introduire des contraintes dans le problème de minimisation (on oblige la solution du problème à être dans ).
Une solution (globale) du problème est un point tel que
Clairement, si prend la valeur , on a ; et si n'est pas identiquement égale à , on a .
Si est un espace vectoriel topologique, est une solution locale du problème si
En réalité une solution locale est une solution globale au sens précédent.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.