Mit Nebenbedingungen — Lagrange & KKT
Gleichungs-Restriktionen — Lagrange
Minimiere f(x) unter g(x) = 0. Lagrange-Funktion: L(x, λ) = f(x) + λ·g(x). Notwendig: ∇L = 0, also ∇f = -λ·∇g.
Geometrisch: Im Optimum stehen ∇f und ∇g parallel — die Niveaulinie von f tangiert die Restriktion g = 0.
Beispiel — Maximum auf dem Kreis
Maximiere f(x, y) = xy unter g(x, y) = x² + y² - 1 = 0.
∇f = (y, x), ∇g = (2x, 2y) → y = 2λx, x = 2λy → x² = y² → x = ±y. Mit x²+y² = 1: |x| = |y| = 1/√2. Maximum bei (1/√2, 1/√2) und (-1/√2, -1/√2): f = 1/2.
Ungleichungs-Restriktionen — KKT
Minimiere f(x) unter g_i(x) ≤ 0. KKT-Bedingungen:
1) ∇f + Σ μᵢ ∇gᵢ = 0 2) μᵢ ≥ 0 3) gᵢ(x) ≤ 0 4) μᵢ · gᵢ(x) = 0 (Komplementarität)
1) ∇f + Σ μᵢ ∇gᵢ = 0 2) μᵢ ≥ 0 3) gᵢ(x) ≤ 0 4) μᵢ · gᵢ(x) = 0 (Komplementarität)
Aktive Restriktionen (gᵢ = 0) haben μᵢ > 0; inaktive (gᵢ < 0) haben μᵢ = 0. Bei konvexen Problemen sind die KKT-Bedingungen hinreichend.