Active-Set-Methoden

Active-Set-Methoden sind eine Klasse iterativer Algorithmen zur Lösung von quadratischen Optimierungsproblemen.

Mathematische Problemstellung

Jedes quadratische Programm kann in eine standardisierte Form überführt werden:

minx∈ℝn12xTHx+cTx=f(x)s.t.aiTx≥bi∀i∈ℐajTx=bj∀j∈ℰ

wobei n die Anzahl der Entscheidungsvariablen ist. In der Zielfunktion f(x) entspricht H der Hesse-Matrix, die Mengen ℐ und ℰ indizieren die Ungleichheits- und Gleichheitsbedingungen. Oft wird dabei gefordert, dass die Matrix H positiv semidefinit ist, da dann das Optimierungsproblem konvex ist.

Active Set

Eine Nebenbedingung i∈ℐ ist aktiv an einem Punkt x, wenn aiTx=bi gilt.

Das Active Set 𝒜(x) ist die Menge aller aktiven Bedingungen an einem gültigen Punkt x:

𝒜(x):={j∈ℰ∪i∈ℐ:aiTx=bi}

Algorithmus

Active-Set-Methoden setzen eine initiale gültige Lösung x0 voraus. Die Algorithmen berechnen dann in jeder Iteration einen gültigen Punkt xk, bis ein Optimum erreicht ist. Dabei wird eine Menge Wk verwaltet, die angibt, welche Nebenbedingungen in der aktuellen Iteration aktiv sein sollen.

 1  Gegeben: gültiger Punkt x0, W0⊆𝒜(x0)
 2
 3  for k=0,1,.. do
 4  berechne eine Suchrichtung pk
 5  if pk=0
 6    berechne Lagrange-Multiplikatoren λi
 7    if ∀i:λi≥0
 8      terminiere und gib xk aus
 9    else
10      finde Ungleichheitsbedingung i∈Wk∩ℐ mit λi<0
11      Wk+1=Wk∖i
12    end
13  else
14    berechne Schrittlänge αk
15    if αk<1
16      finde Nebenbedingung j die αk beschränkt
17      Wk+1=Wk∪j
18    end
19    xk+1=xk+αkpk
20  end

Berechnung der Suchrichtung pk

Die Nebenbedingungen in Wk definieren einen Unterraum. Wenn x in der optimalen Lösung der Zielfunktion in diesem Unterraum ist, kann man die Suchrichtung als pk=x−xk definieren. Substituiert man dies in die Zielfunktion, erhält man die Suchrichtung pk durch Lösen eines quadratischen Subproblems:

minx∈ℝn12pkTHpk+gkTpks.t.ATpk=0∀i∈Wk

wobei gk=Hxk+c der Gradient an der aktuellen Lösung ist und die Spalten der Matrix A die Vektoren ai,i∈Wk sind.

Dieses Subproblem kann auf verschiedenen Weisen gelöst werden. Eine Möglichkeit ist dabei ein Nullspace-Ansatz:

Hat man eine Matrix Z, deren Spalten eine Basis für den Kern der Matrix AT bilden, kann man den gültigen Bereich des Subproblems durch pk=Zu parametrisieren. Löst man nun das Gleichungssystem

Mu=−ZTgk,

wobei M=ZTHZ die reduzierte Hesse-Matrix ist, erhält man die Suchrichtung im originalen Problem.

Berechnung der Lagrange-Multiplikatoren λi

Falls die Suchrichtung pk=0 ist, ist xk bereits optimal im aktuellen Unterraum. Man muss dann eine geeignete Ungleichheitsbedingung aus Wk entfernen. Die Lagrange-Multiplikatoren λi erhält man durch Lösen eines linearen Gleichungssystems:

∑i∈Wk∩ℐaiλi=gk=Hxk+c

Falls alle λi≥0 sind, erfüllen xk und λ die Karush-Kuhn-Tucker-Bedingungen, welche notwendige Kriterien für die Optimalität sind. Wenn zudem die Hesse-Matrix H positiv semidefinit ist, sind diese Bedingungen hinreichend und xk ist die optimale Lösung des Problems. Entfernt man eine Ungleichheitsbedingung mit negativem Lagrange-Multiplikator aus Wk erhält man in der nächsten Iteration eine Suchrichtung.

Berechnung der Schrittlänge αk

Hat man eine Suchrichtung pk, muss man die maximale Schrittlänge αk berechnen. Eine volle Schrittlänge mit αk=1 führt direkt zum Minimum im durch Wk definierten Unterraum. Die Schrittlänge ist jedoch häufig durch eine Nebenbedingung i∉Wk beschränkt.

Alle Nebenbedingungen in i∉Wk mit aiTpk≥0 sind auch am Punkt xk+αkpk für alle αk≥0 erfüllt, da dann die Ungleichung

aiT(xk+αkpk)=aiTxk+αkaiTpk≥aiTxk≥bi

gilt. Alle Nebenbedingungen i∉Wk mit aiTpk<0 werden am neuen Punkt nur dann eingehalten, wenn für diese Nebenbedingungen die Ungleichung

aiTxk+αkaiTpk≥bi

gilt. Dies ist äquivalent mit der Bedingung

αk≤bi−aiTxkaiTpk∀{i∉Wk|aiTpk<0}

Um so nah wie möglich an das Optimum im aktuellen Unterraum zu kommen, kann man die maximale Schrittlänge durch diese Formel berechnen:

αk=min⁡(1,mini∉Wk,aiTpk<0bi−aiTxkaiTpk)

Die Nebenbedingung, die diese Länge beschränkt, wird in die Menge Wk+1 aufgenommen, da diese Nebenbedingung nun aktiv ist.