Duality theory in linear optimization and its extensions -- formally verified

Each language version is independently generated for its own context, not a direct translation.

De Gouden Regel van de Optimale Keuze: Een Verhaal over Rekenen met Oneindigheid

Stel je voor dat je een kok bent die probeert het goedkoopste, meest voedzame middagmaal te bedenken. Je hebt rijst, linzen, en misschien nog wat andere ingrediënten. Je wilt zoveel mogelijk eiwitten en calorieën, maar je budget is beperkt. Dit is een klassiek probleem in de wiskunde: Lineaire Optimalisatie.

Maar wat als je niet zeker weet of een ingrediënt wel bestaat? Wat als de prijs van linzen plotseling "oneindig" wordt omdat ze uitverkocht zijn? En wat als je wilt bewijzen dat je nooit een oplossing kunt vinden, zelfs niet als je alles probeert?

Dat is precies waar dit wetenschappelijke artikel over gaat. Martin Dvorak en Vladimir Kolmogorov hebben een oude wiskundige theorie (de Farkas-Lemma) niet alleen opnieuw bewezen, maar ze hebben hem ook "opgefrist" zodat hij werkt met oneindige getallen. En het allerbelangrijkste: ze hebben dit allemaal gedaan in een digitale "super-rekenmachine" genaamd Lean 4, die elke stap van hun redenering controleert op fouten.

Hier is een uitleg in gewone taal, met een paar creatieve vergelijkingen.

1. De Basis: Het "Of-Of" Spel (Farkas-Lemma)

Stel je een groot bord met regels voor.

Regel A: "Je moet minstens 30 gram eiwitten hebben."
Regel B: "Je mag niet meer dan 10 euro uitgeven."

De vraag is: Is er een combinatie van eten die aan al deze regels voldoet?

De wiskundige Farkas (uit de jaren '90) ontdekte een prachtige, simpele regel hierover. Het is een "Of-Of" situatie:

Ofwel bestaat er een oplossing (een maaltijd die aan alle regels voldoet).
Ofwel bestaat er een "bewijs van onmogelijkheid". Dit is een lijst met gewichten die je op de regels kunt leggen om te bewijzen dat ze elkaar tegenstrijden.

De Metafoor:
Stel je voor dat je een balans hebt.

Als je een maaltijd kunt vinden die op de balans past, dan is het goed.
Als dat niet kan, dan kun je de regels (de schalen van de balans) zo met elkaar vermenigvuldigen en optellen dat je uitkomt op een absurde conclusie, zoals: "0 is groter dan 0".
Als je die absurde conclusie kunt afleiden, dan weet je zeker dat er geen oplossing is.

Dit artikel bewijst dat deze regel altijd waar is, zelfs in de complexe wereld van de wiskunde, en dat er geen "gaten" in zitten.

2. De Nieuwe Uitdaging: Rekenen met "Oneindig"

Tot nu toe was de wiskunde beperkt tot "normale" getallen. Maar in de echte wereld (en in computerprogramma's) willen we soms dingen zeggen als: "Deze taak is zo belangrijk dat hij oneindig veel tijd kost" of "Deze prijs is oneindig hoog".

In de traditionele wiskunde is "oneindig" een lastig ding. Je kunt er niet zomaar mee rekenen (wat is oneindig min oneindig? Of nul keer oneindig?).

De auteurs hebben een nieuw systeem bedacht: De Uitgebreide Getallenlijn.

Ze hebben twee nieuwe symbolen toegevoegd: ⊥ (onderaan, negatief oneindig) en ⊤ (bovenaan, positief oneindig).
Ze hebben regels bedacht voor hoe je hiermee moet rekenen. Bijvoorbeeld: als je iets met een prijs van oneindig moet kopen, dan is de totale prijs ook oneindig.
De Grootte van de Uitdaging: Ze moesten bewijzen dat hun "Of-Of" regel (het Farkas-Lemma) nog steeds werkt, zelfs als je deze oneindige getallen in de vergelijkingen stopt.

Voorbeeld uit het artikel (De goedkope lunch):
Stel, je wilt rijst en linzen kopen.

Rijst is goedkoop.
Linzen zijn ook goedkoop.
Maar: Linzen zijn uitverkocht!

In een gewone computer zou je de linzen uit de lijst moeten halen en het programma opnieuw moeten draaien. Maar in hun nieuwe systeem zeggen ze gewoon: "De prijs van linzen is nu oneindig."
Het algoritme ziet dit, denkt: "O, als ik linzen koop, kost het oneindig veel geld. Dat kan ik niet doen." En het kiest automatisch voor alleen rijst. Het systeem "weet" zelf dat de linzen uit de oplossing moeten worden geweerd, zonder dat je de code hoeft aan te passen.

3. De Digitale Bewijskracht: Lean 4

Waarom is dit artikel zo speciaal? Omdat de auteurs niet zomaar zeggen: "We geloven dat dit waar is." Ze hebben het bewezen met een computer.

Ze gebruikten Lean 4, een taal die lijkt op een programmeertaal, maar dan voor wiskundige bewijzen.

De "Super-Check": Stel je voor dat je een heel complex bouwwerk hebt (een wiskundig bewijs). Normaal gesproken kijkt een mens naar de blauwdrukken en hoopt dat er geen fouten in zitten.
Met Lean 4 is het alsof je een robot hebt die elke steen, elke mortel en elke hoek van het bouwwerk controleert. Als er ook maar één klein foutje in de logica zit, zegt de robot: "Nee, dit klopt niet."

De auteurs hebben hun hele theorie (met de oneindige getallen erbij) in deze robot gestopt. De robot heeft gecontroleerd: "Ja, dit klopt. Geen enkele stap is fout." Dit geeft een betrouwbaarheid die bijna onmogelijk is te bereiken met alleen menselijke ogen.

4. Waarom is dit nuttig voor ons?

Je vraagt je misschien af: "Wat heb ik hieraan?"

Betrouwbare Software: Veel moderne software (voor vliegtuigen, medicijnen, financiële systemen) gebruikt lineaire optimalisatie. Als je software fouten maakt in de berekeningen, kan dat rampzalig zijn. Door wiskundige theorieën formeel te bewijzen, kunnen we software bouwen die "wiskundig foutloos" is.
Flexibele Modellen: Het vermogen om met "oneindige" waarden te rekenen helpt bij het modelleren van harde beperkingen. Bijvoorbeeld: "Je mag deze chemische stof niet gebruiken" (prijs = oneindig) in plaats van "Probeer het maar niet te gebruiken". Dit maakt modellen slimmer en natuurlijker.
De Toekomst van Wiskunde: Dit is een stap in de richting van een wereld waar wiskundigen en computers samenwerken. De mens bedenkt de ideeën en de analogieën, en de computer zorgt ervoor dat de logica waterdicht is.

Samenvatting in één zin

Dit artikel is een reis naar de grenzen van de wiskunde, waar auteurs bewezen hebben dat je zelfs met "oneindige" getallen kunt rekenen om de beste beslissingen te nemen, en dat ze dit allemaal hebben laten controleren door een onfeilbare digitale rechter.

Het is als het vinden van de perfecte receptuur voor een maaltijd, maar dan met de zekerheid dat je nooit per ongeluk een ingrediënt toevoegt dat de hele wereld doet exploderen.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het artikel "Duality theory in linear optimization and its extensions: formally verified" in het Nederlands.

Titel: Dualiteitstheorie in lineaire optimalisatie en haar uitbreidingen: formeel geverifieerd

Auteurs: Martin Dvorak en Vladimir Kolmogorov
Publicatie: Annals of Formalized Mathematics, Volume 2 (2026)

1. Probleemstelling

In het domein van optimalisatie en gerelateerde gebieden is het fundamentele vraagstuk of een gegeven stelsel van lineaire ongelijkheden een oplossing heeft. De klassieke antwoorden hierop zijn "alternativestellingen" (zoals de lemma's van Farkas), die stellen dat een stelsel een oplossing heeft dan en slechts dan als er geen contradictie kan worden afgeleid door een lineaire combinatie van de ongelijkheden.

Hoewel deze theorieën wiskundelijk goed begrepen zijn, ontbreekt het vaak aan een volledig formeel geverifieerde basis in moderne bewijshulpmiddelen, vooral voor:

Algemene algebraïsche structuren: De meeste bestaande resultaten zijn beperkt tot velden of specifieke getalstelsels, terwijl de theorie breder toepasbaar is op lineair geordende delingsringen en modules.
Uitgebreide reële getallen: In discrete optimalisatieproblemen met "harde" (moet worden voldaan) en "zachte" (moet worden geoptimaliseerd) constraints, is het wenselijk om oneindige coëfficiënten te gebruiken. Traditionele lineaire programmering (LP) staat geen oneindige waarden toe, wat leidt tot onelegant wiskundig modelleren (bijv. het gebruik van zeer grote getallen in plaats van $\infty$ ).

Het doel van dit artikel is om deze theorieën formeel te bewijzen in Lean 4 en de dualiteitstheorie uit te breiden naar een setting met oneindige coëfficiënten.

2. Methodologie

De auteurs hebben hun werk volledig gerealiseerd binnen het Lean 4 bewijshulpmiddel, gebruikmakend van de wiskundige bibliotheek Mathlib.

Formalisatie van Algebraïsche Hiërarchieën: Ze hebben de bestaande definitie van lineair geordende velden in Mathlib uitgebreid met lineair geordende delingsringen (linearly ordered division rings). Dit is essentieel omdat de commutativiteit van vermenigvuldiging niet altijd vereist is voor de geldigheid van de lemma's van Farkas.
Definitie van Uitgebreide Velden ( $F_\infty$ ): Ze hebben een nieuw type gedefinieerd, $F_\infty = F \cup \{\bot, \top\}$ $F_{\infty} = F \cup {⊥, ⊤}$ , waarbij $\bot$ $⊥$ negatieve oneindigheid en $\top$ $⊤$ positieve oneindigheid voorstelt.
- Ze hebben specifieke rekenregels gedefinieerd (bijv. $\bot + \top = \bot$ en $0 \cdot \bot = \bot$).
- Ze hebben bewezen dat dit een dicht lineair geordend abels monoid is, maar geen veld of groep.
Matrix- en Vectoroperaties: De auteurs hebben nieuwe definities voor matrix-vectorvermenigvuldiging ontwikkeld die werken met "gewogen" sommen, waarbij de vectoren en matrices over verschillende domeinen kunnen worden gedefinieerd (bijv. een matrix over $F_\infty$ vermenigvuldigd met een vector over $F$ ).
Inductieve Bewijzen: De kern van de bewijzen (vooral voor de generalisaties van Farkas) maakt gebruik van inductie op de grootte van het stelsel, gebaseerd op de methoden van Bartl.

3. Belangrijkste Bijdragen

A. Formele Bewijzen van Bestaande Resultaten

De auteurs hebben meerdere bestaande stellingen formeel bewezen in Lean 4:

Lemma's van Farkas: Zowel voor gelijkheden als ongelijkheden.
Generalisatie van Bartl: Ze hebben een zeer algemene versie van het lemma van Farkas bewezen (Theorema 1.6) die geldt voor modules over lineair geordende delingsringen, waarbij de coëfficiënten in een geordende module kunnen liggen. Dit omvat de klassieke matrix-versies als speciale gevallen.
Sterke Dualiteit: De stelling van sterke dualiteit voor lineaire programmering is formeel bewezen.

B. Nieuwe Uitbreiding: Lineaire Programmering met Oneindige Coëfficiënten

Dit is de meest innovatieve bijdrage van het papier. Ze definiëren een Extended Linear Program (ELP) over $F_\infty$ .

Validiteitsvoorwaarden: Ze hebben zes strikte voorwaarden gedefinieerd voor een "geldig" ELP om te voorkomen dat de dualiteitstheorie instort (bijv. een rij mag niet zowel $\bot$ als $\top$ bevatten).
Uitgebreide Dualiteit: Ze hebben een nieuwe stelling voor sterke dualiteit bewezen voor deze uitgebreide setting (Theorema 1.11). De stelling stelt dat als een ELP of zijn duaal toelaatbaar is, de optimale waarden elkaars tegengestelde zijn ( $P^* = -D^*$ ), zelfs met oneindige waarden.
Toepassing: Ze tonen aan hoe dit een elegante manier biedt om "harde" constraints te modelleren door de coëfficiënten in de doelfunctie naar $\top$ te zetten in plaats van een arbitrair groot getal.

4. Resultaten

Correctheid: Alle stellingen, inclusief de complexe voorwaarden voor de uitgebreide dualiteit, zijn volledig geverifieerd door de Lean 4 compiler. Dit garandeert dat er geen logische fouten in de bewijzen zitten.
Noodzaak van Voorwaarden: De auteurs hebben systematisch bewezen dat elk van de zes voorwaarden voor een "geldig" ELP noodzakelijk is. Ze presenteren contra-exempels waarbij het wegnemen van één voorwaarde leidt tot het falen van de dualiteitsstelling (bijv. beide systemen hebben dan een oplossing, of de optimale waarden kloppen niet).
Implementatie: De volledige code, inclusief definities, stellingen en bewijzen, is openbaar beschikbaar in een GitHub-repository. Ze gebruiken Lean versie 4.18.0 en Mathlib.

5. Betekenis en Impact

Wiskundige Zuiverheid: Het werk biedt een robuuste, foutloze basis voor dualiteitstheorie die verder gaat dan de standaard lineaire velden en ook niet-commutatieve structuren en oneindige waarden omvat.
Praktische Toepassingen: De uitbreiding naar $F_\infty$ biedt een wiskundig elegante oplossing voor problemen in discrete optimalisatie waar "harde" en "zachte" constraints gemengd worden. Dit elimineert de noodzaak voor "engineering hacks" (zoals het kiezen van een groot getal $M$ ) en maakt modellen natuurgetrouwer.
Formele Gemeenschap: Het project demonstreert de kracht van Lean 4 en Mathlib voor het formaliseren van geavanceerde optimalisatietheorie. Het vult een gat in de bestaande formalisaties (die vaak beperkt zijn tot Isabelle of Rocq en specifieke getalstelsels) en biedt een referentiepunt voor toekomstig werk in lineaire programmering en convex analyse binnen de formele wiskunde.
Uitdagingen: Het papier benadrukt ook de beperkingen van huidige tools: het handmatig definiëren van niet-standaard matrixoperaties en het ontbreken van geautomatiseerde tactieken voor complexe gevalanalyse en sommaties over subtypen bleek tijdrovend.

Kortom, dit artikel levert een grondige, formeel geverifieerde uitbreiding van de dualiteitstheorie die zowel theoretisch diepgaand is als praktische voordelen biedt voor het modelleren van complexe optimalisatieproblemen.