Probabilités et statistiquesMéthode · Glossaire
algorithme primal dual
Algorithme utilisé en recherche opérationnelle, en particulier pour résoudre des problèmes de programmation linéaire. Il exploite la dualité entre un problème d'optimisation (dit primal) et son problème dual associé : lorsque les hypothèses de dualité forte sont satisfaites, les valeurs optimales du primal et du dual sont égales, même si leurs vecteurs solutions diffèrent. Selon la variante, l'algorithme construit conjointement des candidats primal et dual et peut maintenir leur faisabilité ou certaines relations de complémentarité ; ces propriétés ne sont pas universelles et peuvent n'être réunies qu'à l'arrêt.
Sommaire
Ce que vous allez apprendre
- Relier un programme primal à son dual.
- Reconnaître les conditions qui certifient l'optimalité.
- Vérifier sur un exemple que les deux objectifs valent 10.
- Distinguer la méthode, la dualité forte et une métaheuristique.
En clair
Imaginez deux personnes qui encadrent le même coût. La première construit une solution au problème de départ ; la seconde cherche une borne qui prouve qu'aucune meilleure solution n'est possible. Tant qu'un écart subsiste, leurs informations indiquent où progresser.
Un algorithme primal-dual fait dialoguer ces deux points de vue. Lorsque les deux solutions sont admissibles et donnent la même valeur, le calcul s'arrête : la solution construite est optimale et l'autre fournit un certificat vérifiable.
Définition
Un algorithme primal-dual est une méthode d'optimisation qui travaille avec un problème primal et son dual. Dans le cadre standard de la programmation linéaire, une solution duale réalisable donne une borne à toute solution primale réalisable. Pour un primal de maximisation et un dual de minimisation, la valeur primale ne dépasse donc jamais la valeur duale.
Quand les deux problèmes sont réalisables et possèdent une valeur optimale finie, la dualité forte garantit l'égalité de leurs valeurs optimales. Elle ne dit pas que leurs vecteurs solutions sont identiques : ils peuvent avoir des dimensions différentes. L'optimalité se reconnaît grâce à la faisabilité des deux côtés, à l'égalité des valeurs et, sous la forme usuelle, aux conditions de complémentarité. Celles-ci imposent qu'une variable strictement positive corresponde à une contrainte opposée saturée ; réciproquement, un écart strict force la variable associée à être nulle.
Le nom recouvre une famille de procédures. Selon la variante, les itérations conservent la faisabilité d'un côté, des deux côtés, ou s'en approchent progressivement. Le trait commun est d'utiliser l'information duale pour choisir une amélioration primale, et l'information primale pour resserrer le certificat dual, jusqu'au critère d'arrêt prévu.
Le principe
Dans un programme linéaire primal de maximisation associé à un dual de minimisation, procédez ainsi : construisez des candidats en respectant l'invariant de faisabilité prévu par la variante ; repérez les contraintes serrées ; modifiez les variables primales ou duales guidées par ces contraintes ; puis recommencez.
L'arrêt est justifié lorsque les deux candidats sont réalisables et complémentaires. Leurs valeurs sont alors égales : la dualité faible interdit qu'une solution primale ait une valeur supérieure, et l'égalité certifie donc l'optimalité des deux candidats.
Quand l'utiliser
La méthode s'applique lorsqu'un problème d'optimisation possède un dual exploitable, notamment en programmation linéaire. Il faut connaître les variables, l'objectif et les contraintes des deux problèmes, ainsi que la correspondance entre variables et contraintes opposées.
Trois vérifications commandent le certificat final : le candidat primal satisfait toutes ses contraintes ; le candidat dual satisfait les siennes ; les produits de complémentarité sont nuls. L'égalité des valeurs découle alors de ces conditions. Pour invoquer directement la dualité forte avec des valeurs finies, les deux programmes doivent admettre des solutions optimales.
Si le primal est irréalisable, aucune itération ne peut produire le candidat primal exigé. Il faut alors rechercher un certificat d'irréalisabilité ou employer une procédure qui traite explicitement cette phase, au lieu de conclure à l'optimalité.
Un exemple, pas à pas
Un atelier choisit des quantités abstraites x et y afin de maximiser un score. La figure associée rend visibles les deux domaines réalisables et les deux points qui certifient l'optimum.
Données. Les variables x et y sont non négatives. Leur somme ne dépasse pas 4, et x ne dépasse pas 2. Le score à maximiser est 3x + 2y.
Le problème primal et son dual, dont les variables non négatives sont u et v, s'écrivent :
1. Choisissez x = 2 et y = 2. Les contraintes donnent 2 + 2 = 4 et 2 ≤ 2 : le candidat primal est réalisable.
2. Choisissez u = 2 et v = 1. Les contraintes donnent 2 + 1 = 3 et 2 ≥ 2 : le candidat dual est réalisable.
3. Calculez les objectifs : 3 × 2 + 2 × 2 = 10, tandis que 4 × 2 + 2 × 1 = 10.
4. Contrôlez la complémentarité : les quatre contraintes correspondantes sont saturées aux variables positives.
2. Choisissez u = 2 et v = 1. Les contraintes donnent 2 + 1 = 3 et 2 ≥ 2 : le candidat dual est réalisable.
3. Calculez les objectifs : 3 × 2 + 2 × 2 = 10, tandis que 4 × 2 + 2 × 1 = 10.
4. Contrôlez la complémentarité : les quatre contraintes correspondantes sont saturées aux variables positives.
Les deux valeurs égales à 10 encadrent exactement l'optimum. Pour refaire le contrôle, prenez n'importe quel point primal admissible : la dualité faible borne son score par la valeur duale 10. Le point (2, 2) atteint déjà cette borne.
En pratique
En programmation linéaire, le point de vue primal-dual est utile lorsqu'on veut obtenir à la fois une solution et une preuve numérique de sa qualité. On suit alors l'écart entre les deux objectifs ; un écart nul avec deux candidats réalisables certifie l'optimum.
En optimisation combinatoire, certaines structures permettent d'interpréter les variables duales comme des prix ou des potentiels. Une procédure spécialisée est préférable lorsqu'elle transforme les contraintes serrées en choix combinatoires directement vérifiables.
Si l'on cherche surtout une bonne solution rapidement sans certificat exact, une métaheuristique peut être plus adaptée. Si la preuve d'optimalité est indispensable et que le dual reste calculable, l'approche primal-dual apporte précisément ce certificat.
À ne pas confondre
Dualité forte. C'est un résultat d'égalité entre valeurs optimales sous les hypothèses appropriées, et non un algorithme. Dans l'exemple, l'égalité 10 = 10 illustre le théorème ; les étapes qui construisent les candidats relèvent de la méthode primal-dual.
Méthode du simplexe. Elle se déplace entre des sommets du domaine primal, même si les informations duales peuvent y jouer un rôle. Une procédure qui ajuste explicitement les deux points de vue selon des conditions de complémentarité est qualifiée de primal-dual.
Métaheuristique. Elle vise généralement une solution de bonne qualité sans exiger un certificat dual exact. Une égalité vérifiée entre bornes primale et duale distingue au contraire la conclusion certifiée d'un algorithme primal-dual exact.
Limites et pièges
Égalité sans faisabilité. Deux valeurs numériques identiques ne suffisent pas si l'un des candidats viole une contrainte. Le symptôme est une borne apparemment parfaite accompagnée d'une inégalité fausse ; il faut contrôler chaque contrainte avant de conclure.
Optimum non fini ou problème irréalisable. La formule « valeurs optimales égales » ne s'applique pas lorsqu'une valeur finie manque. Une recherche qui ne trouve jamais de candidat admissible ou dont l'objectif s'améliore sans borne exige un diagnostic d'irréalisabilité ou de non-bornitude.
Optimum non unique. Un écart primal-dual nul certifie une valeur optimale, pas l'unicité des solutions. Si plusieurs candidats distincts atteignent la même valeur, il faut les décrire comme plusieurs optima plutôt que parler de « la » solution.
Complémentarité isolée. Des produits nuls ne prouvent rien sans les contraintes de faisabilité. Dans l'exemple, le cas charnière est un écart d'objectif égal à 0 avec les deux systèmes satisfaits ; si l'écart est strictement positif, le certificat d'optimalité n'est pas acquis.
Pour aller plus loin
Algorithme — Situer la méthode primal-dual dans la notion générale de procédure finie et organisée.
Les métaheuristiques — Comparer un certificat exact d'optimalité avec des stratégies de recherche qui privilégient la qualité pratique d'une solution.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres