optimaliteitscriterium

Het optimaliteitscriterium is een formele regel of voorwaarde die bepaalt of een kandidaatoplossing optimaal is voor een optimalisatieprobleem, oftewel of deze de doelfunctie minimaliseert of maximaliseert onder de gegeven beperkingen.

Er wordt onderscheid gemaakt tussen globale en lokale optimaliteit: een globale optimum is een punt dat beter is dan elk ander haalbaar punt voor de probleemspecificatie; een lokaal optimum scoort beter dan alle nabije haalbare punten. Daarnaast spreekt men van noodzakelijke en voldoende voorwaarden: een noodzakelijke voorwaarde geldt bij elke optimale oplossing maar garandeert op zichzelf geen optimaliteit; een voldoende voorwaarde garandeert optimale waarde onder de veronderstellingen.

Voorbeelden van criteria per type probleem: unconstrained optimalisatie gebruikt vaak de eerste-orde voorwaarde ∇f(x*) = 0; bij extra aannames (zoals een positief definite Hessiaan) volgen lokale minima. Geconstrainteerde optimalisatie maakt gebruik van de KKT-voorwaarden: ∇f(x*) + ∑ λ_i∇g_i(x*) + ∑ μ_j∇h_j(x*) = 0, met g_i(x) ≤ 0, h_j(x) = 0, en complementaire slackness. In lineaire programmering gelden eveneens primal- en dual-feasibility en complementaire slackness; in veel gevallen levert sterke dualiteit de optimale waarde op. In dynamische systemen en controle verwijst men naar Bellman’s principe van optimaliteit en naar Pontryagin’s Maximum Principle.

Optimaliteitscriteria dienen vooral als toetsingskader voor algoritmen die naar een optimaal punt zoeken en als middel om de aard van de oplossing te interpreteren. Hun toepasselijkheid en strengheid hangen af van de probleemstelling en van de aannames die men maakt.