⚡ electrical engineering

Conformal Predictive Programming for Chance Constrained Optimization

Dit artikel introduceert Conformal Predictive Programming (CPP), een raamwerk dat kansgeconstreerde optimalisatie transformeert naar een deterministisch probleem met behulp van de kwantillema van conformal prediction en een onafhankelijke kalibratiestap om robuuste a posteriori garanties te bieden, zelfs in situaties waar standaardveronderstellingen falen of distributieverschuivingen optreden.

Oorspronkelijke auteurs: Yiqi Zhao, Xinyi Yu, Matteo Sesia, Jyotirmoy V. Deshmukh, Lars Lindemann

Gepubliceerd 2026-07-10

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yiqi Zhao, Xinyi Yu, Matteo Sesia, Jyotirmoy V. Deshmukh, Lars Lindemann

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een robot probeert te programmeren om door een doolhof te navigeren. Je wilt dat de robot de kortste route neemt, maar er is een addertje onder het gras: de sensoren van de robot zijn een beetje wazig. Soms ziet hij een muur waar er geen is, en soms mist hij een muur die er wel degelijk staat. Je hebt een plan nodig dat garandeert dat de robot niet botst, zelfs niet met die wazige sensoren, maar je weet niet precies hoe "wazig" de sensoren zijn.

Dit is het probleem van Chance Constrained Optimization (kansgestuurde optimalisatie). Het is als proberen de beste route te vinden terwijl je zegt: "Ik wil voor 90% zeker weten dat ik niet tegen een muur aanrijd," zonder dat je de exacte regels van het doolhof kent.

De oude manier: Gissen met scenario's

Traditioneel hebben ingenieurs een methode gebruikt genaamd de "Scenario Approach". Stel je voor dat je een groep vrienden vraagt waar de muren zouden kunnen staan. Je bouwt vervolgens een pad dat elke muur vermijdt die je vrienden hebben voorspeld. Als je genoeg vrienden vraagt, zul je misschien geluk hebben en een veilig pad vinden.

Maar hier is het probleem: als je vrienden het mis hebben over het type muren (bijvoorbeeld als zij denken dat muren altijd recht zijn, terwijl ze in werkelijkheid gebogen zijn), dan kan je pad falen. Ook, als het doolhof enorm groot en complex is, wordt het een wiskundige nachtmerrie die eeuwen duurt om op te lossen als je genoeg vrienden moet vragen om veilig te zijn. De paper betoogt dat deze oude methoden vaak steunen op strikte regels over de vorm van het doolhof (zoals het moet perfect rond of glad zijn) die in de echte wereld niet altijd voorkomen.

Het nieuwe idee: Conformal Predictive Programming (CPP)

De auteurs van deze paper stellen een nieuwe tool voor genaamd Conformal Predictive Programming (CPP). Zie CPP als een tweestaps "test en certificeer"-proces dat werkt, zelfs wanneer je de exacte regels van het spel niet kent.

Stap 1: De oefenronde (Optimalisatie)
Eerst voert de robot een simulatie uit met een set oefendata (laten we zeggen 200 oefenruns). De robot probeert de beste route te vinden die de muren in deze specifieke oefenruns vermijdt. Het is alsof de robot zegt: "Oké, op basis van deze 200 pogingen, lijkt dit de beste route te zijn."

Stap 2: De veiligheidscontrole (Kalibratie)
Hier wordt CPP slim. In plaats van alleen te vertrouwen op de oefenronde, pakt de robot een tweede, volledig gescheiden set data (nog eens 200 runs) om als scheidsrechter te fungeren. Hij controleert het pad dat in Stap 1 is gevonden tegen deze nieuwe scheidsrechterdata.

Met behulp van een statistische truc genaamd de "Quantile Lemma", berekent CPP een veiligheidsmarge. Het vraagt zich af: "Hoe vaak is dit pad gefaald in de scheidsrechterdata?" Als het te vaak is gefaald, wordt het pad afgekeurd. Als het voldoende vaak is geslaagd, geeft het systeem een "certificaat" met de tekst: "We zijn voor 90% zeker dat dit pad veilig is."

Waarom dit een grote zaak is

De paper benadrukt drie belangrijke superkrachten van CPP:

Het hoeft de regels niet te kennen: In tegen te diferencia van de oude methoden, heeft CPP geen aannames nodig dat het doolhof een perfecte cirkel is of dat de muren glad zijn. Het werkt zelfs als de data vreemd, rommelig of niet-convex (gedraaid en geknikt) is.
Het heeft een "veiligheidsnet" voor de toekomst: De paper laat zien dat CPP je een garantie kan geven achteraf (een "a posteriori" garantie). Het is als het bouwen van een brug, het testen van de brug met een zware vrachtwagen, en dan zeggen: "Oké, nu weten we zeker dat deze brug 10 ton kan dragen." De paper stelt expliciet dat voor veel complexe problemen de oude methoden je deze "achteraf"-garantie niet konden geven zonder onmogelijke wiskunde te verrichten.
Het past zich aan aan veranderingen: De auteurs laten zien dat CPP kan omgaan met "distributieverschuivingen" (distribution shifts). Stel je voor dat de robot getraind is in een zonnig doolhof, maar moet rijden in een regenachtig doolhof. De "Robust CPP"-versie van de tool kan de veiligheidsmarge aanpassen om rekening te houden met de regen, zodat de robot veilig blijft, zelfs wanneer de omstandigheden veranderen.

Wat de cijfers zeggen

De auteurs hebben het niet alleen theoretisch onderbouwd; ze hebben simulaties gedraaid om te bewijzen dat het werkt.

In een convexe (gladde) testcase hebben ze 300 experimenten uitgevoerd. De nieuwe methode hield de robot succesvol ongeveer 91% van de tijd veilig (wat overeenkomt met hun doel van 90% veiligheid), terwijl de oude "discard"-methode slechts 87% haalde.
In een niet-convexe (gedraaide) testcase, wat veel moeilijker is, behaalde de nieuwe methode nog steeds een veiligheidspercentage van 90% en 89%.
Ze hebben ook een "Stochastic Optimal Control"-scenario getest (een robot die beweegt in een 2D-ruimte). Toen ze een "distributieverschuiving" introduceerden (het simuleren van een verandering in variantie van 0,012 naar 0,013), faalde de standaardmethode om het veiligheidsdoel te halen (slechts 80%), maar de nieuwe "Robust CPP"-methode haalde 96%.

Wat ze niet beweren

Het is belangrijk om op te merken wat deze paper niet zegt. Het claimt niet dat het alle mogelijke optimalisatieproblemen in het universum heeft opgelost. Er wordt specifiek vermeld dat als je geen tweede set data hebt voor de "scheidsrechter"-stap, je deze specifieke garanties niet kunt krijgen. Bovendien, hoewel de methode efficiënt is, vereist het nog steeds twee datasets (één voor planning, één voor controle), wat een afweging is vergeleken met methoden die proberen alles in één keer te doen.

De kern van de zaak

De paper suggereert dat door het probleem op te splitsen in een "planningsfase" en een "kalibratiefase", we robots en systemen kunnen bouwen die veiliger en betrouwbaarder zijn, zelfs wanneer de wereld rommelig en onvoorspelbaar is. Het is een manier om te zeggen: "We hoeven niet alles over de toekomst te weten om een veilig plan te maken voor vandaag; we hebben alleen een goede manier nodig om ons werk te controleren."

Technische Samenvatting: Conformal Predictive Programming voor Chance Constrained Optimization

Probleemstelling
Het artikel behandelt Chance Constrained Optimization (CCO) problemen, waarbij een kostenfunctie $J(x)$ moet worden geminimaliseerd onder voorwaarden die met een hoge waarschijnlijkheid ( $1-\delta$ ) moeten gelden over een willekeurige vector $Y$ . Formeel is het probleem:
$\min_{x \in X} J(x) \quad \text{onder de voorwaarde dat} \quad P(f(x, Y) \leq 0) \geq 1 - \delta$
waarbij $f$ een Borel-meetbare functie is en $Y$ een onbekende distributie $P_Y$ volgt. De primaire uitdaging bij het oplossen van CCO is dat de distributie $P_Y$ doorgaans onbekend is, en zelfs als deze bekend is, vereist het evalueren van de waarschijnlijkheidsvoorwaarde het oplossen van complexe, vaak onhandelbare integralen. Bestaande steekproefgebaseerde benaderingen, zoals de Scenario Approach (SA) en Sample Average Approximation (SAA), vertrouwen vaak op sterke structurele aannames (bijv. convexiteit van $J$ , $f$ en $X$ ) om a priori garanties te bieden. Wanneer deze aannames niet standhouden, of wanneer a priori garanties te conservatief of computationeel te duur zijn om te berekenen (bijv. door de identificatie van ondersteunende beperkingen te vereisen), hebben bestaande methoden moeite met het bieden van betrouwbare a posteriori haalbaarheidsgaranties.

Methodologie: Conformal Predictive Programming (CPP)
De auteurs stellen Conformal Predictive Programming (CPP) voor, een raamwerk dat het stochastische CCO-probleem transformeert naar een deterministisch optimalisatieprobleem met behulp van Conformal Prediction (CP). CPP werkt in twee afzonderlijke fasen:

Optimalisatiefase (Kwantielherformulering):
In plaats van de ruwe kansvoorwaarde te gebruiken, vervangt CPP deze door een kwantielvoorwaarde gedefinieerd over een optimalisatiedataset $\{Y^{(1)}, \dots, Y^{(K)}\}$ . Het probleem wordt geherformuleerd als:
$\min_{x \in X} J(x) \quad \text{onder de voorwaarde dat} \quad \hat{Q}_{\alpha(K)}(f(x, Y^{(1)}), \dots, f(x, Y^{(K)})) \leq 0$
Hier is $\hat{Q}_{\alpha(K)}$ het empirische kwantiel op een specif kind niveau $\alpha(K)$ . De auteurs laten zien dat deze herformulering een instantie is van SAA, waardoor CPP de a priori garanties van de SAA-literatuur kan erven voor specifieke probleemklassen (bijv. scheidbare beperkingen).
Kalibratiefase (A Posteriori Garanties):
Om rigoureuze a posteriori haalbaarheidsgaranties te bieden zonder te vertrouwen op structurele aannames zoals convexiteit, maakt CPP gebruik van een tweede, onafhankelijke kalibratiedataset $\{Y^{(K+1)}, \dots, Y^{(K+L)}\}$ .
- Marginale garanties: Met behulp van de Quantile Lemma van CP berekent CPP een kwantiel $C_m$ over de kalibratiedata. Stelling 3.4 stelt vast dat de oplossing $x^*(K)$ voldoet aan $P(f(x^*(K), Y) \leq C_m) \geq 1-\delta$ met betrekking tot de productmaat van de data.
- Conditionele garanties: Door tijdens de kwantielberekening een aangescherpt betrouwbaarheidsniveau te gebruiken (Conditional Quantile Lemma), biedt CPP garanties die met een hoge betrouwbaarheid ( $1-\beta$ ) gelden, geconditioneerd op de kalibratiedataset.
- Kwantielverschuiving (Quantile Shift): Om gevallen aan te pakken waarin de berekende grens $C$ positief is, stellen de auteurs een "kwantielverschuwing"-methode voor (Stelling 3.6). Deze berekent een aangepaste foutkans $\delta^*$ op basis van het aantal vervulde beperkingen in de kalibratieset, waardoor $P(f(x^*(K), Y) \leq 0) \geq 1-\delta^*$ met hoge betrouwbaarheid wordt gegarandeerd.

Belangrijkste Bijdragen

Nieuw Raamwerk: De introductie van CPP als een steekproefgebaseerde benadering die weinig structurele aannames vereist voor CCO-problemen.
Statistische Garanties: Het bieden van zowel conditionele als marginale a posteriori haalbaarheidsgaranties. In tegen르게 van de standaard SA, zijn deze garanties niet afhankelijk van de dimensie van de beslissingsvariabele $n$ , wat de conservativiteit voor hoogdimensionale problemen vermindert.
Modulariteit en Veelzijdigheid: Het raamwerk is ontworpen om gemakkelijk verschillende varianten van Conformal Prediction te integreren. De auteurs demonstreren dit door CPP uit te breiden naar:
- Robust CPP (RCPP): Behandelt distributieverschuivingen (bijv. sim-to-real gaps) met behulp van robuuste conformal prediction en ambiguïteitssets.
- Mondrian CPP (MCPP): Adresseert klasse-conditionele kansvoorwaarden (MCCO), waarbij wordt gewaarborgd dat veiligheidsgaranties gelden voor specifieke subgroepen van de distributie van de willekeurige variabele.
Verbinding met Bestaande Theorie: Het artikel stelt vast dat CPP de a priori garanties van SAA erft en dat de conditionele a posteriori garanties asymptotisch reduceren tot Chernoff-bounds.

Resultaten en Casestudy's
De auteurs valideren CPP via numerieke casestudy's die zowel convexe als niet-convexe problemen, evenals een stochastische optimale controletaak, omvatten.

Convex en Niet-Convex Optimalisatie: In experimenten waarbij CPP werd vergeleken met de Scenario Approach (SA) voor niet-convexe problemen, toonde CPP een concurrerende prestatie. Opvallend genoeg, terwijl niet-convexe SA-methoden (bijv. [18, 26]) computationeel dure stappen vereisen om irreducibele ondersteunende deelverzamelingen te vinden voor a posteriori garanties (wat in de studie ongeveer 10 seconden duurde), is de kwantielverschuwing van CPP aanzienlijk sneller (lineaire tijd).
Empirische Dekking: De experimenten bevestigden dat de empirische dekking van de oplossingen convergeert naar de theoretische grenzen ( $1-\delta$ of $1-\delta^*$ ). De histogrammen van de berekende grenzen waren gecentreerd rond nul, wat aangeeft dat de kwantielherformulering de oorspronkelijke kansvoorwaarde effectief benadert.
Robuuste en Mondrian Extensies: In een stochastische optimale controletaak (robotnavigatie) handelde RCPP succesvol een distributieverschuiving af (het simuleren van een verandering in ruisvariantie), waarbij een hogere empirische dekking (0.96) werd bereikt vergeleken met de standaard CPP-baseline (0.80). Op dezelfde manier slaagde Mondrian CPP erin om de dekking guarantees te handhaven voor specifieke groepen van verstoringen waar standaard CPP in tekortschoot.

Betekenis en Claims
Het artikel claimt dat CPP een computationeel efficiënt en uitbreidbaar raamwerk biedt voor CCO-problemen waarbij standaard aannames (convexiteit, bekende distributies) niet beschikbaar of moeilijk te verifiëren zijn. De primaire betekenis ligt in het bieden van dimensie-onafhankelijke certificaten van haalbaarheid. In tegenstelling tot de Scenario Approach, waarbij garanties minder ruim worden naarmate het aantal beslissingsvariabelen toeneemt, blijven de garanties van CPP robuust ongeacht de dimensionaliteit, mits een tweede kalibratiedataset beschikbaar is. De auteurs benadrukken dat deze benadering de kloof overbrugt tussen de theoretische strengheid van conformal prediction en de praktische behoeften van controle en planning onder onzekerheid, en een praktisch alternatief biedt voor methoden die vertrouwen op complexe structurele analyse of te conservatieve oplossingen opleveren.