Ê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
Dualité (optimisation)
Résumé
En théorie de l'optimisation, la dualité ou principe de dualité désigne le principe selon lequel les problèmes d'optimisation peuvent être vus de deux perspectives, le problème primal ou le problème dual, et la solution du problème dual donne une borne inférieure à la solution du problème (de minimisation) primal. Cependant, en général les valeurs optimales des problèmes primal et dual ne sont pas forcément égales : cette différence est appelée saut de dualité. Pour les problèmes en optimisation convexe, ce saut est nul sous contraintes.
Le terme de problème dual renvoie généralement au problème dual de Lagrange mais d'autres existent – comme le problème dual de Wolfe ou de Fenchel. Le problème dual de Lagrange est obtenu en écrivant le Lagrangien d'un problème de minimisation avec des multiplicateurs de Lagrange positifs pour ajouter les contraintes à la fonction objectif puis en résolvant sur les variables primales qui minimisent la fonction objectif originale. Cette solution donne les variables primales comme fonctions des multiplicateurs de Lagrange, appelés variables duales, et le nouveau problème consiste à maximiser la fonction objectif sur les variables duales sont les contraintes dérivées sur ces variables duales (comptant au minimum les contraintes non négatives).
En général, avec deux paires d'espaces localement convexes séparés (X , X) et (Y , Y) et la fonction F : X → R ∪ {+∞} , on peut définir le problème primal ainsi : déterminer vérifiant
Ainsi, si existe, est le minimum de la fonction f et l'infimum (plus grand minorant) de la fonction est atteint.
S'il y a des contraintes, on peut modifier la fonction objectif f en avec I une fonction convenable sur X qui atteint son minimum, égal à 0, quand les contraintes sont satisfaites, ce qui permet de prouver que . Cette dernière condition est trivialement, mais pas toujours de façon idéale, satisfaite pour la fonction indicatrice (i.e. I(x) = 0 avec x satisfaisant les contraintes et I(x) = +∞ sinon). On étend alors en une fonction de perturbation F : X × Y → R ∪ {+∞} telle que .
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.