Optimalisatieproblemen

Een optimalisatieprobleem is een wiskundige formulering waarin men de beste waarde zoekt van een doelfunctie f(x) onder een verzameling beperkingen die de toegestane beslissingen bepalen. Een oplossing bestaat uit een toewijzing van de variabelen x die aan alle beperkingen voldoet en waarbij f(x) zo gunstig mogelijk is (minimale of maximale waarde). Een veelgebruikte notatie is min f(x) onder g_i(x) ≤ 0 en h_j(x) = 0, met x ∈ X.

Optimalisatieproblemen worden onderverdeeld naar de aard van de variabelen en de structuur van f en de beperkingen. Lineaire programmering (LP) heeft een lineaire doelstelling en lineaire beperkingen. Integer programming (IP) of combinatoriële optimalisatie vereist dat sommige variabelen gehele getallen aannemen. Niet-lineaire optimalisatie omvat gevallen waarin f of de beperkingen niet-lineair zijn; niet-convexe problemen kunnen meerdere lokale optima hebben. Convexiteit is een belangrijke eigenschap: bij een convex min-probleem met een convexe feasible set heeft elke lokale optimum doorgaans ook een globaal optimum en bestaan er vaak efficiënte oplossingsmethoden.

Oplossingsmethoden variëren van analytische technieken zoals Lagrange-multipliers en de KKT-voorwaarden tot numerieke algoritmen zoals gradiënt- en Newton-methoden en interior-point-methoden voor convex problemen. Voor LP gebruikt men de simplex-methode of interior-point, voor IP en combinatoriële problemen bestaan methoden als branch-and-bound en cutting planes. Daarnaast worden heuristische en metaheuristische benaderingen toegepast, zoals greedy, local search, genetische algoritmen en simulatie-annealing, vooral bij grote of ongestructureerde problemen.

Toepassingen van optimalisatieproblemen bevinden zich in logistiek, productieplanning en operations research, financiën, engineering, energievoorziening en machine learning. De complexiteit varieert sterk: veel combinatoriële problemen zijn NP-hard, terwijl veel lineaire en convex problemen efficiënt kunnen worden opgelost met polynomial-tijddalgoritmen.