Mix-CALADIN: A Distributed Algorithm for Consensus Mixed-Integer Optimization

Titel: Mix-CALADIN: Een Gedistribueerd Algorithmus voor Consensus Mixed-Integer Optimalisatie

Auteurs: Boyu Han, Xu Du, Karl H. Johansson, Apostolos I. Rikos.

---

1. Probleemstelling

Het paper adresseert het probleem van gedistribueerde consensus-optimalisatie met gemengde-integer variabelen (Mixed-Integer Programming, MIP), met een specifieke focus op Booleaanse variabelen (waarden 0 of 1).

In veel toepassingen, zoals netwerkontwerp, sensordetectie en microgrid-beheer, moeten grote schaal optimalisatieproblemen worden opgelost waarbij lokale agenten een gezamenlijk doelwit moeten minimaliseren onder de beperking dat hun lokale variabelen moeten overeenkomen met een globale consensusvariabele ($x_i = z$). De uitdaging ligt in het feit dat traditionele MIP-algoritmen vaak centraal zijn en rekenkundig zeer zwaar zijn voor grote schaalproblemen. Bestaande gedistribueerde methoden vertrouwen vaak op lokale MIP-oplossers (wat de schaalbaarheid beperkt) of gebruiken heuristieken zonder formele convergentiegaranties.

Het doel is een algoritme te ontwikkelen dat:

1. Gedistribueerd werkt (zonder centrale MIP-oplosser).
2. Zowel convexe als niet-convexe problemen aankan.
3. Formele convergentiegaranties biedt.

2. Methodologie: Mix-CALADIN

De auteurs stellen Mix-CALADIN voor, een nieuw tweestaps gedistribueerd algoritme dat het Consensus Augmented Lagrangian Alternating Direction Inexact Newton (CALADIN) raamwerk uitbreidt. Het algoritme vermijdt het gebruik van lokale gemengde-integer oplossers door een specifieke aanpak voor Booleaanse variabelen te gebruiken.

Het proces verloopt in twee fasen:

Fase I: Gecontinueerde Relaxatie

• De Booleaanse beperkingen ($b_i \in \{0, 1\}$) worden tijdelijk losgelaten en de variabelen worden behandeld als continue variabelen.
• Het standaard CALADIN-algoritme wordt toegepast om dit relaxatieprobleem op te lossen.
• Doel: Het vinden van een deterministische ondergrens voor het oorspronkelijke probleem en het genereren van een hoogwaardig startpunt voor Fase II.
• Dit stadium garandeert globale lineaire convergentie voor convexe problemen en lokale lineaire convergentie voor niet-convexe problemen.

Fase II: Booleaanse Projectie en Straffing

• Deze fase start met het resultaat van Fase I ($\tilde{z}^*$).
• Het algoritme gebruikt een twee-niveaus structuur (binnen- en buitenlus):
  • Binnenlus: Agenten berekenen lokale gradiënten. Een coördinator lost een convex kwadratisch programma (QP) op met een doosbeperking ($0 \leq z_d \leq 1$). Een straffingsparameter $\alpha$ wordt gebruikt in de doelstelling om de continue variabelen naar de waarden 0 of 1 te duwen. De term $\alpha(1 - 2z_d^{[k]})^T z_d$ fungeert als een convexe benadering om numerieke stabiliteit te behouden (in plaats van een niet-convexe term die instabiliteit kan veroorzaken).
  • Buitenlus: Als de convergentiecriteria van de binnenlus zijn bereikt maar de variabelen nog niet strikt Booleaans zijn (d.w.z. $(1-z_d)z_d \geq \epsilon$), wordt de straffingsparameter $\alpha$ verhoogd ($\alpha \leftarrow \beta \alpha$) en wordt de binnenlus herstart.
• Dit proces herhaalt zich totdat de variabelen effectief Booleaans zijn en de constraints zijn voldaan.

3. Belangrijkste Bijdragen

1. Nieuw Algoritme: Mix-CALADIN is, voor zover bekend, het eerste werk dat Consensus ALADIN toepast op gedistribueerde mixed-integer optimalisatie zonder afhankelijkheid van lokale MIP-oplossers.
2. Formele Convergentie: Het paper biedt strenge convergentiebewijzen:
   • Voor Fase I: Globale lineaire convergentie voor convexe problemen en lokale lineaire convergentie voor niet-convexe problemen.
   • Voor Fase II: Convergentie wordt bewezen onder de milde aanname dat de doelstellingsfuncties Lipschitz-continu zijn, mits de augmented Lagrangian parameter $\rho$ groter is dan de Lipschitz-constante.
3. Robuuste Implementatie: Het gebruik van een convexe benadering voor de Booleaanse straffing (in plaats van directe afronding of niet-convexe termen) zorgt voor numerieke stabiliteit, een probleem dat bij eerdere heuristieken vaak voorkwam.

4. Resultaten en Numerieke Simulaties

De auteurs hebben het algoritme getest in MATLAB op twee scenario's:

1. Niet-convex Sensor Localisatie: Een complex probleem met gemengde Booleaanse beperkingen.
2. Convex Doelwit: Een benchmark tegen bestaande methoden (zoals projectie-based ADMM).

Kernbevindingen:

• Convergentie: De simulaties bevestigen de theoretische voorspellingen. Fase I toont lineaire convergentie. Fase II convergeert effectief naar een oplossing die voldoet aan de Booleaanse constraints.
• Vergelijking met ADMM: In vergelijking met projectie-based ADMM (een heuristische methode zonder convergentiegarantie), levert Mix-CALADIN een superieure oplossing op. ADMM convergeerde naar een lokaal minimum, terwijl Mix-CALADIN een betere oplossing vond met een strikte theoretische onderbouwing.
• Efficiëntie: Het tweestaps proces (relaxatie gevolgd door verfijning) zorgt voor snelle convergentie en hoge kwaliteit van de oplossing, zelfs bij niet-convexe problemen.

5. Betekenis en Conclusie

Mix-CALADIN vult een belangrijke leemte in de literatuur op. Het biedt een oplossing voor gedistribueerde mixed-integer optimalisatie die zowel schaalbaar is (geen centrale MIP-oplosser nodig) als theoretisch robuust (garanties voor convergentie).

Dit is een doorbraak omdat eerdere methoden ofwel te zwaar waren voor gedistribueerde systemen (door lokale MIP-oplossers) ofwel geen garanties boden (door heuristieken). De methode opent de deur voor toepassing in complexe, real-time gedistribueerde systemen zoals slimme netwerken en sensornetwerken, waar zowel discrete beslissingen als continue optimalisatie nodig zijn.

Toekomstig werk zal gericht zijn op het uitbreiden van de techniek naar resource-allocation varianten en het analyseren van de convergentiesnelheid van Fase II, evenals het toepassen in open netwerken met veranderende topologieën.