Deterministisk global optimering

Deterministisk global optimering är en gren av numerisk optimering som fokuserar på att hitta de globala lösningarna för ett optimeringsproblem samtidigt som de ger teoretiska garantier för att den rapporterade lösningen verkligen är den globala, inom en viss fördefinierad tolerans. Termen "deterministisk global optimering" hänvisar vanligtvis till fullständiga eller rigorösa (se nedan) optimeringsmetoder. Rigorösa metoder konvergerar till det globala optimum i begränsad tid. Deterministiska globala optimeringsmetoder används vanligtvis när lokalisering av den globala lösningen är en nödvändighet (dvs. när det enda naturligt förekommande tillståndet som beskrivs av en matematisk modell är det globala minimumet av ett optimeringsproblem), när det är extremt svårt att hitta en genomförbar lösning, eller helt enkelt när användaren vill hitta den bästa möjliga lösningen på ett problem.

Översikt

Neumaier klassificerade globala optimeringsmetoder i fyra kategorier, beroende på deras grad av stränghet med vilken de närmar sig det optimala, enligt följande:

En ofullständig metod använder smart intuitiv heuristik för sökning men har inga skyddsåtgärder om sökningen fastnar i ett lokalt minimum
En asymptotiskt komplett metod når ett globalt minimum med säkerhet eller åtminstone med sannolikhet ett om den tillåts köra oändligt länge, men har inga medel att veta när en global minimering har hittats.
En komplett metod når ett globalt minimum med säkerhet, med antagande av exakta beräkningar och obestämd lång drifttid, och vet efter en begränsad tid att en ungefärlig global minimering har hittats (inom föreskrivna toleranser).
En rigorös metod når ett globalt minimum med säkerhet och inom givna toleranser även i närvaro av avrundningsfel, förutom i nästan degenererade fall, där toleranserna kan överskridas.

Deterministiska globala optimeringsmetoder hör vanligtvis till de två sista kategorierna. Observera att det är extremt svårt att bygga en rigorös mjukvara eftersom processen kräver att alla beroenden också kodas noggrant.

Deterministiska globala optimeringsmetoder kräver sätt att strikt binda funktionsvärden över områden i rymden. Man skulle kunna säga att en huvudskillnad mellan deterministiska och icke-deterministiska metoder i detta sammanhang är att de förra utför beräkningar över regioner i lösningsrummet, medan de senare utför beräkningar på enstaka punkter. Detta görs antingen genom att utnyttja särskilda funktionella former (t.ex. McCormick-relaxationer), eller genom att använda intervallanalys för att arbeta med mer generella funktionsformer. I vilket fall som helst krävs bounding, vilket är anledningen till att deterministiska globala optimeringsmetoder inte kan ge ett rigoröst resultat när man arbetar med black-box- kod, såvida inte den koden uttryckligen skrivs för att även returnera funktionsgränser. Av denna anledning är det vanligt att problem med deterministisk global optimering representeras med hjälp av en beräkningsgraf , eftersom det är enkelt att överbelasta alla operatorer så att de resulterande funktionsvärdena eller derivatan ger resultatintervall (snarare än skalära).

Klasser av deterministiska globala optimeringsproblem

Linjär programmeringsproblem (LP)

Linjära programmeringsproblem är en mycket önskvärd formulering för alla praktiska problem. Anledningen är att med framväxten av inre punktalgoritmer är det möjligt att effektivt lösa mycket stora problem (som involverar hundratusentals eller till och med miljontals variabler) till global optimalitet. Linjär programmeringsoptimeringsproblem faller strikt under kategorin deterministisk global optimering.

Linjär programmeringsproblem med blandade heltal (MILP)

Precis som linjära programmeringsproblem är MILP:er mycket viktiga när man löser beslutsfattande modeller. Effektiva algoritmer för att lösa komplexa problem av denna typ är kända och finns tillgängliga i form av lösare som CPLEX .

Icke-linjära programmeringsproblem (NLP)

Icke-linjära programmeringsproblem är extremt utmanande vid deterministisk global optimering. Den storleksordning som en modern lösare kan förväntas hantera inom rimlig tid är ungefär 100 till några hundra icke-linjära variabler. När detta skrivs finns det inga parallella lösare för den deterministiska lösningen av NLP, vilket står för komplexitetsgapet mellan deterministisk LP och NLP-programmering.

Blandade heltals icke-linjära programmeringsproblem (MINLP)

Ännu mer utmanande än sina NLP-motsvarigheter kan det vara mycket svårt att deterministiskt lösa ett MINLP-problem. Tekniker som heltalssnitt , eller förgrening av ett problem på dess heltalsvariabler (därav att skapa NLP-underproblem som i sin tur kan lösas deterministiskt), används ofta.

Nollordningsmetoder

Nollordningens metoder består av metoder som använder sig av nollordningens intervallaritmetik . Ett representativt exempel är intervallhalvering.

Första ordningens metoder

Första ordningens metoder består av metoder som använder sig av första ordningens information, t.ex. intervallgradienter eller intervalllutningar.

Andra ordningens metoder

Andra ordningens metoder använder sig av andra ordningens information, vanligtvis egenvärdesgränser härledda från intervall Hessiska matriser . En av de mest allmänna andra ordningens metoderna för att hantera problem av allmän typ är αΒΒ -algoritmen.

Deterministiska globala optimeringslösare

ANTIGONE : Algoritmer för kontinuerlig / heltals global optimering av icke-linjära ekvationer). Det är en proprietär programvara, tillgänglig via ANTIGONE GAMS -modelleringsplattformen.

BARON : BARON är tillgängligt under modellspråken AIMMS , AMPL och GAMS och på NEOS-servern. Det är en proprietär programvara
Couenne : Convex Over and Under Envelopes for Nolinear Estimation (Couenne) är ett bibliotek med öppen källkod
EAGO: Easy-Advanced Global Optimization (EAGO) är en lösare med öppen källkod i Julia (programmeringsspråk) . Det är utvecklat av University of Connecticut.
LINDO (Linear, Interactive, and Discrete Optimizer) inkluderar globala optimeringsmöjligheter.
MAiNGO: McCormick-baserad algoritm för icke-linjär global optimering med blandade heltal (MAiNGO) är ett C++-paket med MPI- och openMP-parallellisering och tillhandahålls med öppen källkod under Eclipse Public License - v 2.0.
Octeract Engine är en egenutvecklad lösare med parallelliseringsmöjligheter. Den är utvecklad och licensierad av Octeract
SCIP : SCIP är en öppen källkodssvit av optimeringslösare som bland annat löser blandad heltals icke-linjär programmering (MINLP)