Lagrange-duales Problem

sup⁡λ∈Rm,μ∈R+ℓinf⁡x∈RnL(x,λ,μ)\sup _{\lambda \in \mathbb{R}^{m}, \mu \in \mathbb{R}_{+}^{\ell}} \inf _{x \in \mathbb{R}^{n}} \mathcal{L}(x, \lambda, \mu)

Lagrange-Funktion, Lagrange-Multiplikatoren

mit dualer Zielfunktion:

d(λ,μ)=inf⁡x∈RnL(x,λ,μ)d(\lambda, \mu)=\inf _{x \in \mathbb{R}^{n}} \mathcal{L}(x, \lambda, \mu)

Gradient der Lagrange-Funktion berechnen um μ\mu und λ\lambda zu bestimmen. Lösungen in die Zielfunktion substituieren. Daraus ergibt sich das Lagrange-duale Problem.

Beziehungsweise geschickt das Infimum bestimmen indem man Sachen, die nicht von xx abhängen rauszieht und das restliche Infimum überprüft.

→ siehe Übung 5

primale Zielfunktion:

p(x)=sup⁡λ∈Rm,μ∈R+ℓL(x,λ,μ)p(x)=\sup _{\lambda \in \mathbb{R}^{m}, \mu \in \mathbb{R}_{+}^{\ell}} \mathcal{L}(x, \lambda, \mu)

Beispiel

Bildschirmfoto 2022-07-16 um 12.37.27.png

Wie man hier gut erkennen kann stellt das duale Problem stets eine untere Schranke des primalen Problems beziehungsweise der primalen Lösung dar.

In diesem Beispiel gilt sogar, dass der primale und duale Zielfunktionswert im Optimum gleich sind. Das ist allerdings nicht immer der Fall.

Other References