Dabei kann die abstrakte Restriktion beispielsweise Forderungen wie (Ganzzahligkeit) oder für einen Kegel aufnehmen. Die auftretenden Funktionen müssen weder konvex noch differenzierbar sein.
Die Funktion
heißt dann die zu dem obigen Optimierungsproblem gehörende Lagrange-Funktion. Gelegentlich werden die Funktionen sowie die Skalare zu Vektoren und zusammengefasst. Die Lagrange-Funktion vereinfacht sich dann zu
heißt dann die duale Funktion zu dem obigen Optimierungsproblem. Das Optimierungsproblem
heißt das duale Problem des obigen Optimierungsproblems. Dabei ist komponentenweise zu verstehen. Das ursprüngliche Problem wird dann auch als primales Problem bezeichnet. Im Allgemeinen muss die duale Funktion nicht reellwertig sein, sie kann durchaus auch den Wert annehmen. Man definiert dann
als den wesentlichen Definitionsbereich der dualen Funktion. Die dualen Variablen werden dual zulässig genannt, wenn sie zulässig bezüglich des dualen Problems sind, das heißt, wenn gilt.
Dabei ist und . Der Vollständigkeit halber setzt man , was in diesem Fall keine Einschränkung bedeutet. Die Lagrange-Funktion ist dann
.
Ist , so ist unabhängig von und damit ist . Ist aber , so ist in eine Richtung nach unten unbeschränkt und demnach gilt . Somit lautet die duale Funktion:
Schreibt man nun die Fallunterscheidung aus der dualen Funktion als Nebenbedingung in das duale Problem, so erhält man:
Dies ist genau ein lineares Optimierungsproblem in Standardform.
Die Definitionsmenge der dualen Funktion ist konvex.
Die duale Funktion ist konkav. Für fixiertes ist eine affine Funktion und damit ist als punktweises Infimum von affinen Funktionen konkav. Somit ist das duale Problem immer ein konvexes Optimierungsproblem, unabhängig von der Struktur des primalen Problems.
Daher sind konvexe Optimierungsprobleme eine Klasse von Problemen, deren duales Problem wieder in derselben Problemklasse liegt. Weitere solche Klassen sind die lineare Optimierungsprobleme (siehe Beispiel), die konischen Programme sowie die semidefiniten Programme und die SOCPs.
Sei die Restriktionsmenge des primalen Problems und die Definitionsmenge des dualen Problems.
Dann gilt für alle und
Der Wert heißt dann die Dualitätslücke (des zulässigen Punktes ). Die duale Funktion ist also immer eine untere Schranke für die Zielfunktion des primalen Problems. Somit lässt sich auch das duale Problem motivieren: Es stellt die Frage nach der größten unteren Schranke für das primale Problem, die noch zulässig ist.
Ist die Wertemenge des primalen Problems und die des dualen Problems, so gilt
.
Der Wert der dualen Optimallösung ist also stets kleiner als der Wert der primalen Optimallösung. Diese Aussage wird auch schwache Dualität genannt. Der Wert heißt dann die optimale Dualitätslücke.
Diese Aussagen folgen direkt aus
Dabei folgt die letzte Ungleichung, da und (Zulässigkeit von ) und (Zulässigkeit von ) und damit und . Da die Ungleichung für beliebige und gilt, folgen die beiden obigen Aussagen.
Unter gewissen Umständen stimmen der Optimalwert des primalen Problems und der des dualen Problems überein, die optimale Dualitätslücke ist also Null. Es gilt dann
.
Dieser Fall wird dann starke Dualität genannt. Gilt starke Dualität und ist der Optimalwert endlich und wird in bzw. angenommen, so gilt:
Im Allgemeinen gilt starke Dualität nicht, sondern es müssen noch weitere Regularitätsvoraussetzungen (im Englischen constraint qualifications) an das Problem erfüllt sein. Eine der wichtigsten Voraussetzungen für konvexe Optimierungsprobleme und fast-konvexe Funktionen, unter der starke Dualität gilt, ist zum Beispiel die Slater-Bedingung.
Gilt die starke Dualität, sind und primal bzw. dual optimal und ist der Optimalwert endlich, so gilt die complementary slackness, auch komplementärer Schlupf genannt:
Ist der -te Lagrange-Multiplikator (die -te Ungleichungsrestriktion) ungleich null, so muss die -te Ungleichungsrestriktion (der -te Lagrange-Multiplikator) gleich null sein:
Dies folgt aus und . Es muss also stets mindestens einer der beiden Faktoren null sein.
Ein Punkt heißt ein Sattelpunkt der Lagrange-Funktion, wenn für alle mit
gilt. Äquivalent dazu ist
Dies bedeutet, dass ein Maximum der Lagrange-Funktion für fixiertes und ein Minimum der Lagrange-Funktion für fixiertes ist.
Es lässt sich zeigen, dass genau dann ein Sattelpunkt der Lagrange-Funktion ist, wenn primal optimal ist, dual optimal ist und starke Dualität gilt.
Sattelpunkte spielen eine wichtige Rolle bei der Bestimmung von Optimalpunkten und schlagen eine Verbindung zu den Karush-Kuhn-Tucker-Bedingungen und den Lagrange-Multiplikatoren. Sind zum Beispiel alle beteiligten Funktionen stetig differenzierbar, so lässt sich aus dem Sattelpunktkriterium ableiten, dass an einem Optimalpunkt
gelten muss, da nach der Sattelpunktcharakterisierung minimiert. Diese Forderung findet sich zum Beispiel in den Karush-Kuhn-Tucker-Bedingungen zur Bestimmung eines Optimalpunktes und als notwendiges Optimalitätskriterium wieder.
Hierbei sind die Zielfunktion, die Ungleichungsrestriktionsfunktionen und die Gleichheitsrestriktionsfunktionen. Die seien mit dem echten Kegel ausgestattet, der die verallgemeinerte Ungleichung induziert.
Das zum Vektorraum gehörende Skalarprodukt sei mit bezeichnet. Man setzt dann . Dabei gilt und .
Dann ist die Lagrange-Funktion von der Form
Alternative Formulierungen fassen alle Ungleichungsrestriktionen und Gleichheitsrestriktionen zusammen:
Dies führt zu einer kompakteren Schreibweise, die ohne Summenzeichen und Indizes auskommt und daher für theoretische Betrachtungen bevorzugt wird. Alternativ wird auch die Forderung nach einem echten Kegel abgeschwächt, stattdessen definiert man die Ungleichung nur durch einen Ordnungskegel, der zumindest konvex sein muss. Manchmal wir auch komplett auf Gleichheitsnebenbedingungen verzichtet, man modelliert diese dann stattdessen als Ordnungskegel mit leerem Inneren. Statt zu fordern, definiert man einen Kegel . Dann gilt genau dann, wenn . Für alle drei Varianten sind die Lagrange-Funktion und das duale Problem in der untenstehenden Tabelle angegeben. Die duale Funktion ist stets von der Form bzw., wenn nur eine duale Variable verwendet wird, von der Form .
Primales Problem
Lagrange-Funktion
Duales Problem
Dabei ist die Zielfunktion, , wobei auf ein Kegel ausgezeichnet ist, der im ersten Fall ein echter Kegel ist, im zweiten und dritten Fall ein konvexer Kegel ist. Es ist und .
Für Probleme mit Abbildungen zwischen reellen normierten Vektorräumen ist zu beachten, dass kein Skalarprodukt definiert ist. Man wählt stattdessen die duale Paarung. Dementsprechend sind die dualen Variablen aus dem Dualraum des Vektorraumes.
Ist ein Problem der Form
gegeben, wobei die Zielfunktion, die Ungleichungsrestriktionsfunktionen und die Gleichungsrestriktionsfunktion sind. sei ein Ordnungskegel auf und es seien Banachräume. Die Lagrange-Funktion lautet dann
Dabei ist aus dem Dualraum und aus dem Dualraum
Die duale Funktion ist dann wieder
und damit lautet das duale Problem:
Dabei ist der duale Kegel, der in diesem Fall aber eine Teilmenge von ist.
Formulierungen für alternative Problemstellungen laufen analog zu den Problemen für Abbildungen zwischen Hilberträumen. Die duale Paarung ersetzt jeweils das Skalarprodukt, die dualen Variablen befinden sich im Dualraum.
Die schwache Dualität gilt auch für die beiden allgemeineren Formulierungen. Für den Beweis in der Hilbertraumformulierung nutzt man aus, dass ist, wenn und gilt (für Ordnungskegel erhält man ). In normierten Räumen gelten analoge Aussagen mit dem Unterschied, dass ein Element des Dualraumes ist: Gilt , so folgt .
Die starke Dualität wird in den allgemeineren Fällen identisch zum gewöhnlichen Fall definiert. Auch im verallgemeinerten Fall existieren Regularitätsvoraussetzungen wie die Slater-Bedingung, die starke Dualität garantieren.
