Algoritmen die zich richten op oplossingen voor optimalisatieproblemen, vormen het kloppende hart van machineredeneringen. Nieuwe resultaten onthullen verrassende limieten. Bepalen waar een luchtvaarthub moet worden geplaatst, is een voorbeeld van een polynoomoptimalisatieprobleem. Twee nieuwe bewijzen geven aan wanneer het mogelijk is om dit soort problemen snel op te lossen en wanneer niet.

Opvolging

Ons leven is een aaneenschakeling van optimalisatieproblemen. Ze doen zich voor wanneer we de snelste route naar huis van het werk zoeken of wanneer we kosten en kwaliteit proberen te balanceren tijdens een bezoek aan de winkel, of zelfs wanneer we beslissen hoe we beperkte vrije tijd willen besteden voordat we naar bed gaan.

Deze scenario’s en vele andere kunnen worden weergegeven als een wiskundig optimalisatieprobleem. Het nemen van de beste beslissingen is een kwestie van het vinden van hun optimale oplossingen. Snelweg verkeersborden vind je online. En voor een wereld die doordrenkt is van optimalisatie, bieden twee recente resultaten zowel goed als slecht nieuws.

In een paper dat in augustus 2020 werd gepubliceerd, stelden Amir Ali Ahmadi van Princeton University en zijn voormalige student Jeffrey Zhang, die nu aan de Carnegie Mellon University werkt, vast dat het voor sommige kwadratische optimalisatieproblemen – waarbij paren van variabelen kunnen interageren – rekenkundig onhaalbaar is om vind zelfs lokaal optimale oplossingen op een tijdbesparende manier.

Positieve afhaalmaaltijden

Maar toen, twee dagen later, brachten Zhang en Ahmadi een tweede paper uit met een positieve afhaalmaaltijd. Ze bewezen dat het altijd mogelijk is om snel te identificeren of een kubieke polynoom – die drieweginteracties tussen variabelen kan bevatten – een lokaal minimum heeft, en om het te vinden als dat zo is.

De limieten zijn niet wat hun ontdekkers verwachtten

“Ik had niet gedacht dat er iets magisch gebeurt met kubussen waardoor hun lokale minima handelbaar zijn om te vinden,” zei Ahmadi. Al met al vormen de resultaten twee belangrijke markers in de studie van computationele complexiteit, wat aantoont dat bepaalde soorten problemen gemakkelijk op te lossen zijn, terwijl andere noodzakelijkerwijs moeilijk zijn. Ze bieden ook nieuwe vangrails voor onderzoekers die geïnteresseerd zijn in optimalisatie op verschillende gebieden, van financiën tot autonome systemen.

Leven in wiskunde

Stel dat je de leiding hebt over een autofabriek die maar twee modellen maakt, de Cheapo en de Deluxe. De Deluxe verkoopt voor meer dan de Cheapo, kost meer om te produceren en neemt meer tijd in beslag op de productielijn. Hoeveel van elk moet de fabriek bouwen?

Dit dilemma vertaalt zich in een polynoom optimalisatieprobleem

Om deze vertaling uit te voeren, splitst u het probleem in drie afzonderlijke elementen. Er zijn alle kwantificeerbare variabelen die wachten om te worden geoptimaliseerd – zoals het aantal auto’s dat je moet produceren – beperkingen, zoals budgetten en productiecapaciteit, en dan iets dat de objectieve functie wordt genoemd, wat de som is van hoe elke variabele je naar je doel of ervan weg. Theorie examen oefenen in het Engels is mogelijk online. “De objectieve functie neemt de beslissingsvariabelen als invoer en spuugt een getal uit”, zei Ahmadi. “Dit is iets dat we altijd willen minimaliseren of maximaliseren.”

Ons voorbeeld van een autofactor is een eenvoudig optimalisatieprobleem. Zoals we het hebben beschreven, gaan we ervan uit dat geen van de variabelen met elkaar in wisselwerking staat, wat betekent dat ze in een lineaire functie kunnen worden verpakt. Maar de meeste problemen in de echte wereld zijn rommeliger. De wiskunde die ze beschrijft, is dat ook.

Luchtvaartmaatschappij

Stel je bijvoorbeeld voor dat je probeert de optimale hub voor een luchtvaartmaatschappij te vinden. Elke luchthaven heeft zijn eigen inherente waarde (lineaire bijdragen) van de verkeers- of luchthavenkosten. Maar dan leggen kwadratische termen het effect vast van het kiezen van paren luchthavens die op een bepaalde manier met elkaar interageren: als je veel verkeer uit Los Angeles hebt, heb je meer baat bij een koppeling met een hub in San Francisco.

En natuurlijk kunnen problemen nog ingewikkelder zijn dan dat. Drie-weg interacties tussen variabelen vereisen meer complexe kubieke functies. Elke stap in de complexiteit van functies stelt u in staat een breder scala aan problemen te modelleren. Maar die complexiteit brengt kosten met zich mee – er is geen garantie dat u nog steeds de optimale oplossingen kunt berekenen.

Optimaal probleem

Moderne optimalisatietheorie ontwikkeld tijdens de Tweede Wereldoorlog toen een wetenschapper genaamd George Dantzig een procedure bedacht om oplossingen te vinden voor lineaire optimalisatieproblemen. Zijn baanbrekende werk hielp het Amerikaanse ministerie van Defensie om weloverwogen beslissingen te nemen over alles, van het aanschaffen van vliegtuigen tot het vervoeren van voorraden naar het buitenland.