Dualiteit (optimalisatie)

In de wiskundige optimalisatietheorie is dualiteit of het dualiteitsprincipe het principe dat optimaliseringsproblemen vanuit twee perspectieven kunnen worden bekeken: het primaire probleem of het duale probleem. Als het primaire probleem een minimalisatieprobleem is, dan is het duale een maximalisatieprobleem (en omgekeerd). Elke toelaatbare oplossing voor het primaire (minimalisatie)probleem is minstens zo groot als elke toelaatbare oplossing voor het duale (maximalisatie)probleem. Daarom is de oplossing van het primaire een bovengrens voor de oplossing van het duale, en de oplossing van het duale een ondergrens voor de oplossing van het primaire. Dit feit wordt zwakke dualiteit genoemd.

Over het algemeen hoeven de optimale waarden van het primaire en het duale probleem niet gelijk te zijn. Hun verschil wordt de dualiteitskloof genoemd. Voor convexe optimalisatieproblemen is de dualiteitskloof nul onder een beperkingskwalificatievoorwaarde. Dit feit wordt sterke dualiteit genoemd.

Duaal probleem

Meestal verwijst de term "duaal probleem" naar het lagrangiaanse duale probleem, maar er worden ook andere duale problemen gebruikt, bijvoorbeeld het duale probleem van Wolfe en het duale probleem van Fenchel. Het lagrangiaanse duale probleem wordt verkregen door de lagrangiaan van een minimalisatieprobleem te vormen door niet-negatieve lagrange-multiplicatoren te gebruiken om de beperkingen aan de doelfunctie toe te voegen, en vervolgens de primaire variabelewaarden op te lossen die de oorspronkelijke doelfunctie minimaliseren. Deze oplossing geeft de primaire variabelen als functies van de lagrange-multiplicatoren, die duale variabelen worden genoemd. Het nieuwe probleem is dan om de doelfunctie met betrekking tot de duale variabelen te maximaliseren, onder de afgeleide beperkingen van de duale variabelen (inclusief ten minste de beperkingen van niet-negativiteit).

Toepassingen

Bij support vector machines (SVM's) kan het formuleren van het primaire probleem van SVM's als het duale probleem worden gebruikt om de kernel trick te implementeren, maar deze laatste heeft in de historische gevallen een hogere tijdscomplexiteit.