🤖 machine learning

Input convex neural networks as surrogates in mathematical optimisation

Dit artikel pleit voor het gebruik van input convex neural networks (ICNN's) als surrogaatmodellen in wiskundige optimalisatie, waarbij wordt aangetoond dat hun convexe architectuur nauwere relaxaties en efficiëntere branch-and-bound-algoritmen mogelijk maakt in vergelijking met traditionele feedforward-netwerken, waardoor de oplostijden en schaalbaarheid voor problemen met convexe of concave onderliggende responsen worden verbeterd.

Oorspronkelijke auteurs: Yu Liu, Jan Kronqvist, Fabricio Oliveira

Gepubliceerd 2026-08-11

📖 8 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yu Liu, Jan Kronqvist, Fabricio Oliveira

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 enorme, ingewikkelde puzzel probeert op te lossen, zoals het plannen van de meest efficiënte route voor een vrachtwagen of het mengen van de perfecte batch wijn. Vaak zijn de regels van het spel verborgen in een "black box" — een complex computerprogramma (een neuraal netwerk) dat heeft geleerd hoe de wereld werkt door naar miljoenen voorbeelden te kijken. Je weet wat erin gaat en wat eruit komt, maar je kent de geheime wiskunde binnenin niet. Om de beste mogelijke oplossing te vinden, moet je die black box openen en deze in je puzzel passen. Het probleem is dat het meest voorkomende type black box een grillig, ziggzaggend doolhof is. Proberen het perfecte pad door dit doolhof te vinden, is als het proberen op te lossen van een Rubik's kubus terwijl je geblinddoekt bent; het is zo moeilijk dat computers vaak opgeven voordat ze het antwoord hebben gevonden.

Dit artikel pakt precies dat hoofdpijndossier aan. Het introduceert een speciaal soort black box genaamd een Input Convex Neural Network (ICNN). Zie dit niet als een grillig doolhof, maar als een gladde, komvormige glijbaan. Omdat de vorm zo voorspelbaar is (het curveert slechts één kant op), kunnen computers er zo naar beneden glijden zonder vast te komen zitten. De auteurs laten zien dat door deze gladde glijbanen te gebruiken in plaats van grillige doolhoven, we deze optimalisatiepuzzels veel sneller en met veel minder rekenkracht kunnen oplossen. Ze hebben niet alleen gegokt dat dit zou werken; ze hebben een nieuw wiskundig instrument gebouwd om het te bewijzen en hebben het getest op echte problemen zoals het leveren van voedselhulp en het boren naar olie, waarbij ze ontdekten dat hun methode vaak duizend keer sneller is dan de oude manier.

Het Problema: Het Grillige Doolhof versus de Gladde Glijbaan

In de wereld van operations research (de wetenschap van het nemen van de beste beslissingen) gebruiken we vaak neurale netwerken om als surrogaten te fungeren. Een surrogaat is als een stand-in acteur; het imiteert een complex, duur te berekenen proces zodat we snel beslissingen kunnen nemen. Jarenlang was de standaard stand-in een Feedforward Neural Network (FNN). Stel je een FNN voor als een landschap dat bestaat uit duizenden kleine, scherpe treden en kliffen. Het is ongelooflijk nauwkeurig in het voorspellen van uitkomsten, maar omdat het zo grillig is, is het een nachtmerrie om te optimaliseren. Om de beste oplossing te vinden, moeten computers het probleem omzetten in een enorme lijst van "ja of nee" vragen (binaire variabelen), wat een combinatorische explosie creëert. Het is alsof je het laagste punt in een bergketen probeert te vinden door elke individuele steen te controleren; naarmate het netwerk groter wordt, groeit de tijd die het kost zo snel dat de computer zonder tijd komt te zitten.

De auteurs stellen dat als het echte proces dat we modelleren van nature glad en gebogen is (zoals een kom of een heuvel), we niet een grillige FNN de taak moeten geven. In plaats daarvan moeten we een Input Convex Neural Network (ICNN) gebruiken. Een ICNN is een neuraal netwerk met een strikte regel: het mag alleen in één richting buigen. Het is als een gladde glijbaan of een perfecte kom. Deze structurele beperking maakt de wiskunde veel gemakkelijker te hanteren.

De Ontdekking: Twee Manieren om te Winnen

Het paper onderzoekt twee belangrijke manieren om deze gladde ICNN's te gebruiken om optimalisatieproblemen op te lossen, en ze ontdekten dat beide superieur zijn aan de oude methoden.

1. De "Strakkere Knijp" (ICNN-MIP)
Eerst keken de auteurs naar wat er gebeurt als we nog steeds de standaard "ja of nee"-methode (Mixed-Integer Programming, of MIP) gebruiken, maar de grillige FNN vervangen door een gladde ICNN. Ze bewezen wiskundig dat de "relaxatie" (een vereenvoudigde versie van het probleem die wordt gebruikt om het antwoord te raden) voor een ICNN ongelooflijk strak is.

De Analogie: Stel je voor dat je probeert het gewicht van een watermeloen te raden. De FNN-methode geeft je een doos die enorm en los is; de watermeloen kan overal in de doos zitten. De ICNN-methode geeft je een doos die de watermeloen perfect omsluit.
Het Resultaat: Omdat de "doos" van de ICCN zo strak is, hoeft de computer veel minder mogelijkheden te controleren. In hun tests loste de ICNN-versie problemen op in een fractie van een seconde waar de FNN-versie zelfs na een uur nog geen oplossing had gevonden. In sommige gevallen vond de ICCN-methode direct het perfecte antwoord zonder dat er überhaupt afgevijld (gebrancht) hoefde te worden, terwijl de FNN-methode verdwaalde in miljoenen doodlopende wegen.

2. De "Glijdende Glijbaan" (ICNN-BB)
Ten tweede, en misschien wel spannender, ontwikkelden ze een volledig nieuw algoritme genaamd ICNN-BB. Deze methode gooit de "ja of nee"-vragen volledig overboord. Omdat de ICNN glad en convex is, realiseerden de auteurs zich dat ze het hele netwerk alleen met eenvoudige lineaire vergelijkingen (zoals een rechte lijn) konden beschrijven zonder dat er binaire variabelen nodig waren.

De Analogie: In plaats van een grillige berg te beklimmen met een touw en haken, glijd je gewoon een gladde, wrijvingsloze glijbaan af.
De Addertjes onder het gras: Deze glijbaan werkt perfect als het probleem op een specifieke manier is opgezet (het minimaliseren van de output). Als het probleem complexer is, kan de glijbaan een kleine opening hebben waar hij niet perfect strak is. Om dit op te lossen, bouwden de auteurs een "concaaf envelop" — een veiligheidsnet dat bovenop de glijbaan ligt om eventuele losse eindjes op te vangen. Ze combineerden de glijbaan (epigraaf) en het veiligheidsnet (concaaf envelop) om de sterkst mogelijke wiskundige beschrijving van het netwerk te creëren.
Het Resultaat: Hun nieuwe algoritme, ICNN-BB, tak (branched) direct af op de inputvariabelen (de dingen die je probeert te beslissen) in plaats van op de interne neuronen. Dit is een enorme winst in efficiëntie. In hun tests was deze methode vaak de snelste, vooral wanneer het probleem niet te complex was.

De Praktijktests

Om te bewijzen dat dit niet alleen wiskunde op papier was, testten de auteurs hun ideeën op drie zeer verschillende scenario's uit de echte wereld:

Humanitaire Voedselhulp: Ze modelleerden een systeem om voedsel aan mensen in nood te leveren, waarbij ze probeerden de kosten te minimaliseren terwijl ze aan nutritionele en smaakvereisten voldeden. Het "smaak"-gedeelte was de black box.
- De Uitkomst: De ICNN-methoden waren ongelooflijk snel. De standaard FNN-methode liep vast en faalde; het had meer dan een uur nodig en vond geen oplossing voor grotere netwerken. De ICCN-methoden losten dezelfde problemen op in minder dan een seconde. Nog beter: de ICNN-BB-methode was zo nauwkeurig dat hij direct bij de allereerste stap stopte, wat bewees dat de "glijbaan" perfect was voor dit probleem.
Oliebron Routing: Dit hield in dat er beslist moest worden hoe olie van bronnen naar verwerkingsfaciliteiten werd gerouteerd, een probleem vol lastige fysica en binaire keuzes (een pijp open of dicht).
- De Uitkomst: Hier wonnen de ICCN-methoden ook, maar de race was spannender. De ICCN-MIP-methode loste problemen op die de FNN-methode niet eens kon aanraken. De ICNN-BB-methode was de snelste op kleinere versies, maar vertraagde op de grootste versies omdat het "veiligheidsnet" (de concaaf envelop) te ingewikkeld werd om te berekenen wanneer er te veel variabelen waren. Dit toonde een duidelijke grens aan: ICNN-BB is geweldig voor lage tot gemiddelde complexiteit, maar het "veiligheidsnet" wordt te zwaar als het probleem te groot wordt.
Wijn Blending: Een wijnmaker die probeert druiven van verschillende leveranciers te mengen om de best smakende wijn tegen de laagste kosten te creëren.
- De Uitkomst: Vergelijkbaar met het olieprobleem waren de ICCN-methoden aanzienlijk sneller en betrouwbaarder dan de FNN-methode. De ICCN-BB-methode was de kampioen voor kleine batches, maar naarmate het aantal blends toenam, groeide de computationele kosten van het "veiligheidsnet", waardoor de standaard ICCN-MIP-methode uiteindelijk de betere keuze werd.

De Conclusie

Het paper concludeert dat Input Convex Neural Networks de nieuwe standaardkeuze zijn voor optimalisatieproblemen waarbij de onderliggende relatie glad of gebogen is. Ze bieden een "twee-lagen" voordeel:

Als je ze gebruikt met standaard solvers (ICNN-MIP), krijg je een veel strakkere, efficiëntere zoektocht dan voorheen.
Als je ze gebruikt met hun gespecialiseerde algoritme (ICCN-BB), kun je het probleem vaak oplossen zonder enige binaire variabelen, wat leidt tot enorme snelheidswinsten.

De auteurs merken echter voorzichtig op dat dit geen wondermiddel is voor alles. De ICCN-BB-methode loopt tegen een muur aan wanneer het aantal inputvariabelen te hoog wordt (zoals in de wijnblending-test met 55 dimensies), omdat het berekenen van het "veiligheidsnet" te duur wordt. Maar voor een breed scala aan problemen verandert deze aanpak een computationeel onmogelijke nachtmerrie in een snelle, gladde glijbaan. De auteurs suggereren dat we in de toekomst wellicht nog slimmere manieren zullen zien om deze veiligheidsnetten te bouwen of om convexe en niet-convexe netwerken te mengen om het beste van beide werelden te krijgen.

Technische Samenvatting: Input Convex Neural Networks als Surrogaten in Wiskundige Optimalisatie

Probleemstelling

Het inbedden van getrainde neurale netwerken (NNs) als surrogaten binnen wiskundige optimalisatieproblemen is een standaardpraktijk in operations research, met name wanneer de onderliggende fysieke modellen ontoegankelijk of computationeel te kostbaar zijn. De gangbare aanpak maakt gebruik van Feedforward Neural Networks (FNNs) met Rectified Linear Unit (ReLU) activaties. Hoewel FNNs over universele benaderingscapaciteiten beschikken, vereist hun stuksgewijs lineaire structuur een exacte Mixed-Integer Programming (MIP) herformulering voor globale optimalisatie. Deze herformulering introduceert een binaire variabele voor elke ReLU-unit, wat leidt tot een computationele last die lineair schaalt met de netwerkomvang. Bovewerendien is de continue lineaire programmering (LP) relaxatie van standaard FNN-MIP formuleringen vaak zwak, wat resulteert in grote zoekbomen en een slechte schaalbaarheid voor grotere netwerken.

Dit artikel onderzoekt Input Convex Neural Networks (ICNNs) als een alternatieve surrogaatarchitectuur. ICNNs zijn beperkt tot het produceren van outputs die convex zijn met betrekking tot hun inputs. De auteurs adresseren twee primaire hiaten in de literatuur:

Het gebrek aan een rigoureuze analyse met betrekking tot de geldigheid van de LP-gebaseerde epigrafische inbedding voor ICNNs in algemene optimalisatieomgevingen (voorbij directe minimalisatie).
Het ontbreken van een vergelijkende analyse van de strakheid van LP-relaxaties tussen ICNN-MIP en standaard FNN-MIP formuleringen.

Methodologie

1. Structurele Analyse van ICNN-MIP

De auteurs leiden eerst een MIP-formulering af voor ICNNs (ICNN-MIP) die analoog is aan standaard FNN-MIPs, maar die de specifieke architecturale beperkingen van ICNNs incorporeert (niet-negatieve gewichten voor verborgen lagen en convexe, niet-dalende activatiefuncties).

Exactheid van de Relaxatie: Ze bewijzen dat voor elke vaste input de LP-relaxatie van de ICNN-MIP formulering de exacte netwerkoutput herstelt. Bijgevolg is de LP-relaxatie exact (nul integrality gap) wanneer het optimalisatieprobleem de directe minimalisatie van de ICCN-output betreft.
Vergelijking met FNN: In contrast hiermee kunnen standaard FNN-MIP relaxaties de netwerkoutput onderschatten door ongekende tekens van gewichten, wat leidt tot een niet-nul integrality gap. De auteurs demonstreren dat de structurele eigenschappen van ICNNs inherent leiden tot strakkere LP-relaxaties dan hun FNN-tegenhangers, zelfs in algemene inbeddingsscenario's waarbij de output niet direct wordt geminimaliseerd.

2. Epigrafische Inbedding en Geldigheid

Het artikel formaliseert de condities waaronder de epigrafische inbedding (een LP-gebaseerde herformulering die ReLU-units vervangt door lineaire ongelijkheden $y \geq \hat{f}(x)$ ) een geldige herformulering van het oorspronkelijke probleem vormt.

Definitie van Geldigheid: De inbedding is geldig als de optimale oplossing voldoet aan de gelijkheidsvoorwaarde $y = \hat{f}(x)$ en dezelfde objectieve waarde oplevert als het oorspronkelijke probleem.
Beperking: De epigrafische inbedding is alleen exact wanneer de probleemstructuur de overschatting van de surrogaatoutput bestraft (bijv. directe minimalisatie). In algemene gevallen waar de surrogaatoutput voorkomt in restricties of termen die grotere waarden belonen, kan de epigrafische relaxatie oplossingen toelaten waarbij $y > \hat{f}(x)$ , wat een ongeldige herformulering maakt.

3. Sterkste Continue Relaxatie (Convex Hull)

Om gevallen aan te pakken waarin de epigrafische inbedding niet geldig is, construeren de auteurs de sterkste continue relaxatie van de ICNN-grafiek over een box-domein.

Concave Envelope: Ze leiden een concave envelope af van de ICNN-output door convexe combinaties te berekenen van de waarden van het netwerk op de hoekpunten van de input-box.
Constructie van de Convex Hull: Door de epigraf (ondergrens) te combineren met de concave envelope (bovengrens), bewijzen ze dat het resulterende toegestane gebied exact de convex hull is van de ICNN-grafiek. Deze constructie is tractabel voor ICNNs (vereist $2^n$ vertex-evaluaties waarbij $n$ de inputdimensie is) maar is over het algemeen onberekenbaar voor niet-convexe FNNs.

4. ICNN-BB Algoritme

Op basis van de convex hull relaxatie ontwikkelen de auteurs een gespecialiseerd branch-and-bound algoritme: ICNN-BB:

Branching Strategie: In tegenstelling tot MIP-benaderingen die brancheren op tussenliggende binaire activatievariabelen, brancht ICNN-BB direct op de inputvariabelen.
Procedure: Het algoritme start met de epigrafische inbedding bij de root node. Als de oplossing niet exact is (gap overschrijdt tolerantie), wordt er gebranced op de inputvariabele met het breedste interval, waardoor het box-domein wordt aangescherpt en de concave envelope opnieuw wordt geëvalueerd bij de nieuwe vertices.
Terminatie: Het algoritme termineert bij de root node als de epigrafische inbedding geldig is; anders convergeert het naar het globale optimum naarmate de box-domeinen krimpen en de envelope nauwer wordt.

Belangrijkste Bijdragen

Structurele Karakterisering: Bewezen dat de LP-relaxatie van ICNN-MIP formuleringen een nul integrality gap heeft voor vaste inputs en directe output-minimalisatie, wat een theoretisch voordeel biedt ten opzien van FNN-MIP.
Formele Geldigheidscondities: Gedefinieerd onder welke precieze condities de LP epigrafische inbedding een geldige herformulering is, waarbij scenario's zijn geïdentificeerd waarin deze faalt (bijv. wanneer overschatting niet wordt bestraft).
Convex Hull Constructie: Gedemonstreerd dat de convex hull van de grafiek van een ICNN over een box-domein expliciet geconstrueerd kan worden via de intersectie van de epigraf en een vertex-gebaseerde concave envelope, een eigenschap die niet beschikbaar is voor algemene ReLU-netwerken.
Gespecialiseerd Algoritme: Ontwikkeld ICNN-BB, een LP-gebaseerde branch-and-bound methode die volledig zonder binaire variabelen werkt, door te brancheren op inputs en de convex hull relaxatie te exploiteren voor convergentie.
Empirische Validatie: Gevalideerd via drie verschillende casestudy's (humanitaire voedselhulp, olieput-routing en wijnblending), waarbij ICNN-BB, ICNN-MIP en FNN-MIP werden vergeleken.

Experimentele Resultaten

Casus 1: Humanitaire Voedselhulp

Setup: Optimalisatie van de inkoop van voedselmanden met een palatabiliteit-surrogaat.
Bevindingen: ICNNs vertoonden een vergelijkbare accuratesse als FNNs. FNN-MIP slaagde er niet in om grotere instanties binnen de tijdslimiet op te lossen vanwege zwakke relaxaties. ICCN-MIP loste alle instanties op bij de root node (nul branching) voor zowel HiGHS als Gurobi. ICNN-BB was de snelste methode en loste alle instanties op in minder dan 0,1 seconde bij de root node, wat bevestigt dat de epigrafische inbedding geldig was voor dit probleem.

Casus 2: Olieput-routing

Setup: Maximaliseren van de olie-output met surrogaten voor putprestaties en riser-drukval, waarbij combinatorische routingbeslissingen betrokken zijn.
Bevindingen: ICCN-MIP vereiste consistent minder nodes en loste sneller op dan FNN-MIP over alle solvers heen. ICCN-BB presteerde aanzienlijk beter dan ICCN-MIP bij gebruik van de open-source solver HiGHS (3–8x minder nodes, 3–4x sneller). Echter, bij gebruik van de commerciële solver Gurobi, woog de overhead van het updaten van de concave envelope in ICCN-BB soms niet op tegen het voordeel van een kleinere zoekboom, waardoor ICCN-MIP sneller was voor grotere instanties. Dit benadrukt een solver-afhankelijke trade-off.

Casus 3: Wijnblending

Setup: Minimaliseren van de kosten van druivenmengsels met surrogaten voor kwaliteitsvoorspelling, met variatie in het aantal mengsels en de inputdimensies.
Bevindingen: ICCN-MIP toonde een superieure schaalbaarheid over FNN-MIP in termen van het aantal nodes. ICCN-BB was zeer efficiënt voor kleine tot matige inputdimensies (oplossen in fracties van seconden). Echter, voor hoog-dimensionale inputs (55 dimensies in de grootste instantie), overviel de exponentiële groei van de vertex-set ( $2^n$ ) in de constructie van de concave envelope het algoritme, waardoor ICCN-BB er niet in slaagde een haalbare oplossing te vinden binnen de tijdslimiet, terwijl MIP-formuleringen wel tractabel bleven.

Betekenis en Claims

Het artikel claimt dat ICNNs een structureel superieur alternatief bieden voor FNNs voor optimalisatieproblemen waarbij de onderliggende respons ongeveer convex of concaaf is.

Strakkere Relaxaties: De convexe architectuur biedt inherent strakkere LP-relaxaties, wat de noodzaak voor branching in MIP-formuleringen vermindert.
Exacte LP Herformulering: Wanneer de probleemstructuur dit toelaat, laten ICNNs exact LP-herformuleringen toe zonder binaire variabelen, wat het gebruik van efficiënte LP-solvers mogelijk maakt.
Schaalbaarheidsfrontier: De auteurs identificeren de inputdimensie als de praktische schaalbaarheidsgrens voor het voorgestelde ICCN-BB algoritme. Hoewel het substantiële snelheidswinsten biedt voor lage tot matige dimensies door het elimineren van binaire variabelen, beperkt de exponentiële kosten van vertex-enumeratie de toepasbaarheid van ICCN-BB voor hoog-dimensionale problemen zonder verdere benaderingstechnieken.

Het werk suggereert dat ICNNs de standaard keuze voor surrogaten moeten zijn wanneer de onderliggende functie convexiteit of concaviteit vertoont, mits de inputdimensie beheersbaar is voor de voorgestelde branch-and-bound aanpak of de probleemstructuur een geldige epigrafische inbedding toestaat.