⚡ electrical engineering

Conformal Predictive Programming for Chance Constrained Optimization

Cet article introduit la Programmation Prédictive Conforme (CPP), un cadre qui transforme l'optimisation sous contraintes de probabilité en un problème déterministe en utilisant le lemme du quantile de la prédiction conforme et une étape de calibration indépendante afin de fournir des garanties a posteriori robustes, même dans des contextes où les hypothèses standards échouent ou lorsque des décalages de distribution surviennent.

Auteurs originaux : Yiqi Zhao, Xinyi Yu, Matteo Sesia, Jyotirmoy V. Deshmukh, Lars Lindemann

Publié 2026-07-10

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yiqi Zhao, Xinyi Yu, Matteo Sesia, Jyotirmoy V. Deshmukh, Lars Lindemann

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de programmer un robot pour naviguer dans un labyrinthe. Vous voulez qu'il suive le chemin le plus court possible, mais il y a un piège : les capteurs du robot sont un peu imprécis. Parfois, il voit un mur là où il n'y en a pas, et parfois, il rate un mur qui est pourtant bien présent. Vous devez établir un plan qui garantit que le robot ne s'écrasera pas, même si vous ne savez pas exactement à quel point les capteurs sont « imprécis ».

C'est le problème de l'Optimisation sous Contraintes de Chance. C'est comme essayer de trouver l'itinéraire le plus efficace tout en disant : « Je veux être sûr à 90 % de ne pas heurter un mur », sans connaître exactement les règles du labyrinthe.

L'ancienne méthode : Deviner avec des scénarios

Traditionnellement, les ingénieurs ont utilisé une méthode appelée « Approche par Scénarios ». Imaginez que vous demandiez à un groupe d'amis de deviner où pourraient se trouver les murs. Vous construisez ensuite un chemin qui évite chaque mur que vos amis ont deviné. Si vous interrogez suffisamment d'amis, vous aurez peut-être de la chance et trouverez un chemin sûr.

Mais voici le problème : si vos amis se trompent sur le type de murs (par exemple, ils pensent que les murs sont toujours droits, alors qu'en réalité, ils sont courbes), votre chemin pourrait échouer. De plus, si le labyrinthe est immense et complexe, interroger assez d'amis pour être en sécurité devient un cauchemar mathématique qui prend un temps infini à résoudre. L'article soutient que ces anciennes méthodes reposent souvent sur des règles strictes concernant la forme du labyrinthe (comme le fait qu'il doive être parfaitement rond ou lisse) qui ne correspondent pas toujours à la réalité du terrain.

La nouvelle idée : La Programmation Prédictive Conforme (CPP)

Les auteurs de cet article proposent un nouvel outil appelé Programmation Prédictive Conforme (CPP). Voyez la CPP comme un processus de « test et certification » en deux étapes qui fonctionne même lorsque vous ne connaissez pas les règles exactes du jeu.

Étape 1 : L'entraînement (Optimisation)
D'abord, le robot effectue une simulation en utilisant un ensemble de données d'entraînement (disons 200 essais). Il essaie de trouver le meilleur chemin pour éviter les murs dans ces essais spécifiques. C'est comme si le robot disait : « D'après ces 200 essais, cela semble être la meilleure route ».

Étape 2 : Le contrôle de sécurité (Calibration)
C'est ici que la CPP devient ingénieuse. Au lieu de simplement faire confiance à l'entraînement, le robot utilise un deuxième ensemble de données, complètement distinct (200 essais supplémentaires), pour agir comme un arbitre. Il vérifie le chemin trouvé à l'étape 1 par rapport à ces nouvelles données de l'arbitre.

En utilisant un astuce statistique appelée le « Lemme des Quantiles », la CPP calcule une marge de sécurité. Elle se demande : « À quelle fréquence ce chemin a-t-il échoué dans les données de l'arbitre ? » S'il a trop échoué, le chemin est rejeté. S'il a réussi suffisamment de fois, le système délivre un « certificat » disant : « Nous sommes sûrs à 90 % que ce chemin est sûr ».

Pourquoi c'est une avancée majeure

L'article souligne trois super-pouvoirs de la CPP :

Elle n'a pas besoin de connaître les règles : Contrairement aux anciennes méthodes, la CPP n'a pas besoin de supposer que le labyrinthe est un cercle parfait ou que les murs sont lisses. Elle fonctionne même si les données sont bizarres, désordonnées ou non convexes (tourmentées et sinueuses).
Elle possède un « filet de sécurité » pour l'avenir : L'article montre que la CPP peut vous donner une garantie a posteriori (après coup). C'est comme construire un pont, le tester avec un camion très lourd, puis dire : « D'accord, maintenant nous savons avec certitude que ce pont peut supporter 10 tonnes ». L'article précise explicitement que pour de nombreux problèmes complexes, les anciennes méthodes ne pouvaient pas fournir ce type de garantie « après coup » sans effectuer des calculs impossibles.
Elle s'adapte aux changements : Les auteurs montrent que la CPP peut gérer les « décalages de distribution » (distribution shifts). Imaginez que le robot soit entraîné dans un labyrinthe ensoleillé mais doive conduire dans un labyrinthe sous la pluie. La version « Robust CPP » de l'outil peut ajuster la marge de sécurité pour tenir compte de la pluie, garantissant ainsi que le robot reste en sécurité même lorsque les conditions changent.

Ce que disent les chiffres

Les auteurs n'ont pas seulement théorisé ; ils ont réalisé des simulations pour prouver que cela fonctionne.

Dans un cas de test convexe (lisse), ils ont mené 300 expériences. La nouvelle méthode a réussi à maintenir le robot en sécurité environ 91 % du temps (correspondant à leur cible de 90 % de sécurité), tandis que l'ancienne méthode de « rejet » n'a atteint que 87 %.
Dans un cas de test non convexe (tourmenté), beaucoup plus difficile, la nouvelle méthode a tout de même atteint des taux de sécurité de 90 % et 89 %.
Ils ont également testé un scénario de « Contrôle Optimal Stochastique » (un robot se déplaçant dans un espace 2D). Lorsqu'ils ont introduit un « décalage de distribution » (simulant un passage d'une variance de 0,012 à 0,013), la méthode standard a échoué à couvrir la cible de sécurité (seulement 80 %), mais la nouvelle méthode « Robust CPP » a atteint 96 %.

Ce qu'ils ne prétendent pas

Il est important de noter ce que cet article ne dit pas. Il ne prétend pas avoir résolu tous les problèmes d'optimisation de l'univers. Il précise explicitement que si vous ne disposez pas d'un second ensemble de données pour l'étape de l'« arbitre », vous ne pouvez pas obtenir ces garanties spécifiques. De plus, bien que la méthode soit efficace, elle nécessite toujours deux ensembles de données (un pour la planification, un pour la vérification), ce qui est un compromis par rapport aux méthodes qui tentent de tout faire en une seule étape.

L'essentiel

L'article suggère qu'en divisant le problème en une phase de « planification » et une phase de « calibration », nous pouvons construire des robots et des systèmes plus sûrs et plus fiables, même lorsque le monde est désordonné et imprévisible. C'est une façon de dire : « Nous n'avons pas besoin de tout savoir sur l'avenir pour établir un plan sûr aujourd'hui ; nous avons juste besoin d'une bonne façon de vérifier notre travail ».

Résumé technique : Programmation prédictive conforme pour l'optimisation sous contraintes de chance

Énoncé du problème
Le document traite des problèmes d'optimisation sous contraintes de chance (Chance Constrained Optimization - CCO), qui consistent à minimiser une fonction de coût $J(x)$ sous réserve que des contraintes soient satisfaites avec une probabilité élevée ( $1-\delta$ ) sur un vecteur aléatoire $Y$ . Formellement, le problème est :
$\min_{x \in X} J(x) \quad \text{sous réserve de} \quad P(f(x, Y) \leq 0) \geq 1 - \delta$
où $f$ est une fonction mesurable de Borel et $Y$ suit une distribution inconnue $P_Y$ . Le défi principal de la résolution d'un CCO réside dans le fait que la distribution $P_Y$ est généralement inconnue, et même si elle est connue, l'évaluation de la contrainte de probabilité nécessite de résoudre des intégrales complexes, souvent intraitables. Les approches existantes basées sur l'échantillonnage, telles que l'Approche par Scénarios (Scenario Approach - SA) et l'Approximation par Moyenne Échantillonnale (Sample Average Approximation - SAA), reposent souvent sur de fortes hypothèses structurelles (par exemple, la convexité de $J$ , $f$ et $X$ ) pour fournir des garanties a priori. Lorsque ces hypothèses ne sont pas vérifiées, ou lorsque les garanties a priori sont trop conservatrices ou coûteuses à calculer (par exemple, nécessitant l'identification des contraintes de support), les méthodes existantes peinent à fournir des garanties de faisabilité a posteriori fiables.

Méthodologie : Programmation prédictive conforme (CPP)
Les auteurs proposent la Programmation prédictive conforme (Conformal Predictive Programming - CPP), un cadre qui transforme le problème stochastique de CCO en un problème d'optimisation déterministe en utilisant la Prédiction Conforme (Conformal Prediction - CP). La CPP opère en deux phases distinctes :

Étape d'optimisation (Reformulation par quantile) :
Au lieu d'utiliser la contrainte de chance brute, la CPP la remplace par une contrainte de quantile définie sur un ensemble de données d'optimisation $\{Y^{(1)}, \dots, Y^{(K)}\}$ . Le problème est reformulé comme suit :
$\min_{x \in X} J(x) \quad \text{sous réserve de} \quad \hat{Q}_{\alpha(K)}(f(x, Y^{(1)}), \dots, f(x, Y^{(K)})) \leq 0$
Ici, $\hat{Q}_{\alpha(K)}$ est le quantile empirique à un niveau de confiance spécifique $\alpha(K)$ . Les auteurs démontrent que cette reformulation est une instanciation de la SAA, permettant à la CPP d'hériter des garanties a priori de la littérature SAA pour des classes de problèmes spécifiques (par exemple, les contraintes séparables).
Étape de calibration (Garanties a posteriori) :
Pour fournir des garanties de faisabilité a posteriori rigoureuses sans dépendre d'hypothèses structurelles comme la convexité, la CPP utilise un second ensemble de données de calibration indépendant $\{Y^{(K+1)}, \dots, Y^{(K+L)}\}$ .
- Garanties marginales : En utilisant le Lemme du Quantile de la CP, la CPP calcule un quantile $C_m$ sur les données de calibration. Le Théorème 3.4 établit que la solution $x^*(K)$ satisfait $P(f(x^*(K), Y) \leq C_m) \geq 1-\delta$ par rapport à la mesure produit des données.
- Garanties conditionnelles : En employant un niveau de confiance resserré lors du calcul du quantile (Lemme du Quantile Conditionnel), la CPP fournit des garanties qui tiennent avec une confiance élevée ( $1-\beta$ ) conditionnellement au jeu de données de calibration.
- Décalage de quantile (Quantile Shift) : Pour traiter les cas où le bornage $C$ calculé est positif, les auteurs proposent une méthode de « décalage de quantile » (Théorème 3.6). Celle-ci calcule une probabilité d'échec ajustée $\delta^*$ basée sur le nombre de contraintes satisfaites dans l'ensemble de calibration, garantissant que $P(f(x^*(K), Y) \leq 0) \geq 1-\delta^*$ avec une grande confiance.

Contributions clés

Nouveau cadre : L'introduction de la CPP en tant qu'approche basée sur l'échantillonnage qui nécessite des hypothèses structurelles limitées sur le problème de CCO.
Garanties statistiques : La fourniture de garanties de faisabilité a posteriori à la fois conditionnelles et marginales. Contrairement à la SA standard, ces garanties ne dépendent pas de la dimension de la variable de décision $n$ , ce qui réduit le conservatisme pour les problèmes de haute dimension.
Modularité et polyvalence : Le cadre est conçu pour intégrer facilement diverses variantes de la Prédiction Conforme. Les auteurs démontrent cela en étendant la CPP à :
- CPP Robuste (RCPP) : Gère les décalages de distribution (ex: écarts sim-to-real) en utilisant la prédiction conforme robuste et des ensembles d'ambiguïté.
- CPP de Mondrian (MCPP) : Traite les contraintes de chance conditionnelles par classe (MCCO), garantissant que les garanties de sécurité tiennent pour des sous-groupes spécifiques de la distribution de la variable aléatoire.
Connexion avec la théorie existante : Le document établit que la CPP hérite des garanties a priori de la SAA et que ses garanties conditionnelles a posteriori convergent asymptotiquement vers les bornes de Chernoff.

Résultats et études de cas
Les auteurs valident la CPP à travers des études de cas numériques impliquant des problèmes convexes et non convexes, ainsi qu'une tâche de contrôle optimal stochastique.

Optimisation convexe et non convexe : Dans les expériences comparant la CPP à l'Approche par Scénarios (SA) pour des problèmes non convexes, la CPP a démontré des performances compétitives. Notamment, alors que les méthodes SA non convexes (ex: [18, 26]) nécessitent des étapes coûteuses en calcul pour trouver des sous-ensembles de support irréductibles pour les garanties a posteriori (prenant environ 10 secondes dans l'étude), le calcul du décalage de quantile de la CPP est nettement plus rapide (temps linéaire).
Couverture empirique : Les expériences ont confirmé que la couverture empirique des solutions converge vers les bornes théoriques ( $1-\delta$ ou $1-\delta^*$ ). Les histogrammes des bornes calculées étaient centrés près de zéro, indiquant que la reformulation par quantile approxime efficacement la contrainte de chance originale.
Extensions Robustes et Mondrian : Dans un problème de contrôle optimal stochastique (navigation robotique), la RCPP a géré avec succès un décalage de distribution (simulant un changement de variance du bruit), atteignant une couverture empirique plus élevée (0,96) par rapport à la ligne de base CPP standard (0,80). De même, la CPP de Mondrian a réussi à maintenir les garanties de couverture pour des groupes spécifiques de magnitudes de perturbations là où la CPP standard a échoué.

Signification et affirmations
Le document affirme que la CPP offre un cadre efficace sur le plan computationnel et extensible pour les problèmes de CCO où les hypothèses standard (convexité, distributions connues) sont indisponibles ou difficiles à vérifier. Sa principale importance réside dans la fourniture de certificats de faisabilité indépendants de la dimension. Contra contrairement à l'Approche par Scénarios, où les garanties deviennent plus lâches à mesure que le nombre de variables de décision augmente, les garanties de la CPP restent robustes quelle que soit la dimensionnalité, à condition qu'un second jeu de données de calibration soit disponible. Les auteurs soulignent que cette approche comble le fossé entre la rigueur théorique de la prédiction conforme et les besoins pratiques du contrôle et de la planification sous incertitude, offrant une alternative pratique aux méthodes qui reposent sur des analyses structurelles complexes ou qui produisent des solutions excessivement conservatrices.