barrièrefuncties

Barrièrefuncties zijn speciale functies die in constrained optimization worden gebruikt om ongelijkhedeng_i(x) ≤ 0 af te dwingen. Ze dragen bij aan het omzetten van een constrained probleem naar een reeks makkelijker op te lossen unconstrained problemen, doorgaans via een zogenaamde barrièreterm die oneindig wordt bij het naderen van de rand van het feasible gebied.

Een veel gebruikte vorm is B(x) = ∑i -log(-g_i(x)) voor g_i(x) < 0. Voor een barrièreparameter μ > 0 wordt het geconcentreerde probleem min f(x) + μ B(x) opgelost. Door μ geleidelijk te verlagen, volgen de oplossingen een centrale pad en convergeert men onder geschikte omstandigheden naar een oplossing van het oorspronkelijke constrained probleem. Barrièrefuncties vereisten dat het domein van het probleem de open ruimt van interne punten is; ze zijn daarom meestal bruikbaar wanneer een intern punt van het feasible gebied bestaat.

Eigenschappen van barrièrefuncties omvatten dat ze oneindig worden bij nadering van de grens van de ongelijkheid en doorgaans streng convex zijn wanneer de onderliggende problemen convex zijn. Ze zijn glad binnen het interne domein en vereisen doorgaans een initiële punt in het interne gebied. Barrièrefuncties vormen de kern van interieurpuntmethoden, die veelvuldig worden toegepast in lineaire programmering, convex optimalisatie en niet-lineaire programmering.

Toepassingen en varianten: log-barrière wordt vaak toegepast bij ongelijkheden, en er bestaan zelf-concordante barrières die nuttig zijn voor analyse en snelle convergentie. Voordelen zijn stabiliteit en efficiëntie bij grote, sparsige problemen; nadelen zijn de noodzaak van een startpunt in het interne gebied en de zorgvuldige afbouw van de barrièreparameter.