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:

$\begin{array}{ccc}\underset{x\in {ℝ}^n}{\min }& \frac{1}{2}{x}^{T}Hx+c^{T}x& =f(x)\\ s.t.& a_i^{T}x\ge b_i& \mathrm{\forall }i\in ℐ\\ & a_j^{T}x=b_j& \mathrm{\forall }j\in ℰ\end{array}$

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\in ℐ$ ist aktiv an einem Punkt $x$, wenn $a_i^{T}x=b_i$ gilt.

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

$𝒜(x):=\{j\in ℰ\cup i\in ℐ:a_i^{T}x=b_i\}$

Algorithmus

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

 1  Gegeben: gültiger Punkt $x_0$, $W_0\subseteq 𝒜(x_0)$
 2
 3  for k=0,1,.. do
 4  berechne eine Suchrichtung $p_k$
 5  if $p_k=0$
 6    berechne Lagrange-Multiplikatoren ${\lambda }_i$
 7    if $\mathrm{\forall }i:{\lambda }_i\ge 0$
 8      terminiere und gib $x_k$ aus
 9    else
10      finde Ungleichheitsbedingung $i\in W_k\cap ℐ$ mit ${\lambda }_i<0$
11      $W_{k+1}=W_k\mathrm{\setminus }i$
12    end
13  else
14    berechne Schrittlänge ${\alpha }_k$
15    if ${\alpha }_k<1$
16      finde Nebenbedingung j die ${\alpha }_k$ beschränkt
17      $W_{k+1}=W_k\cup j$
18    end
19    $x_{k+1}=x_k+{\alpha }_k{p}_k$
20  end

Berechnung der Suchrichtung p_k

Die Nebenbedingungen in $W_k$ definieren einen Unterraum. Wenn $x$ in der optimalen Lösung der Zielfunktion in diesem Unterraum ist, kann man die Suchrichtung als $p_k=x-x_k$ definieren. Substituiert man dies in die Zielfunktion, erhält man die Suchrichtung $p_k$ durch Lösen eines quadratischen Subproblems:

$\begin{array}{cc}\underset{x\in {ℝ}^n}{\min }& \frac{1}{2}{p}_k^{T}H{p}_k+g_k^T{p}_k\\ s.t.& A^T{p}_k=0& \mathrm{\forall }i\in W_k\end{array}$

wobei $g_k=H{x}_k+c$ der Gradient an der aktuellen Lösung ist und die Spalten der Matrix $A$ die Vektoren $a_i,i\in W_k$ 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 $A^T$ bilden, kann man den gültigen Bereich des Subproblems durch $p_k=Zu$ parametrisieren. Löst man nun das Gleichungssystem

$Mu=-Z^T{g}_k$,

wobei $M=Z^{T}HZ$ die reduzierte Hesse-Matrix ist, erhält man die Suchrichtung im originalen Problem.

Berechnung der Lagrange-Multiplikatoren λ_i

Falls die Suchrichtung $p_k=0$ ist, ist $x_k$ bereits optimal im aktuellen Unterraum. Man muss dann eine geeignete Ungleichheitsbedingung aus $W_k$ entfernen. Die Lagrange-Multiplikatoren ${\lambda }_i$ erhält man durch Lösen eines linearen Gleichungssystems:

$\sum _{i\in W_k\cap ℐ}{a}_i{\lambda }_i=g_k=H{x}_k+c$

Falls alle ${\lambda }_i\ge 0$ sind, erfüllen $x_k$ und $\lambda$ 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 $x_k$ ist die optimale Lösung des Problems. Entfernt man eine Ungleichheitsbedingung mit negativem Lagrange-Multiplikator aus $W_k$ erhält man in der nächsten Iteration eine Suchrichtung.

Berechnung der Schrittlänge α_k

Hat man eine Suchrichtung $p_k$, muss man die maximale Schrittlänge ${\alpha }_k$ berechnen. Eine volle Schrittlänge mit ${\alpha }_k=1$ führt direkt zum Minimum im durch $W_k$ definierten Unterraum. Die Schrittlänge ist jedoch häufig durch eine Nebenbedingung $i\notin W_k$ beschränkt.

Alle Nebenbedingungen in $i\notin W_k$ mit $a_i^T{p}_k\ge 0$ sind auch am Punkt $x_k+{\alpha }_k{p}_k$ für alle ${\alpha }_k\ge 0$ erfüllt, da dann die Ungleichung

$a_i^T(x_k+{\alpha }_k{p}_k)=a_i^T{x}_k+{\alpha }_k{a}_i^T{p}_k\ge a_i^T{x}_k\ge b_i$

gilt. Alle Nebenbedingungen $i\notin W_k$ mit $a_i^T{p}_k<0$ werden am neuen Punkt nur dann eingehalten, wenn für diese Nebenbedingungen die Ungleichung

$a_i^T{x}_k+{\alpha }_k{a}_i^T{p}_k\ge b_i$

gilt. Dies ist äquivalent mit der Bedingung

${\alpha }_k\le \frac{b_i-a_i^T{x}_k}{a_i^T{p}_k}\mathrm{\forall }\{i\notin W_k|a_i^T{p}_k<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:

${\alpha }_k=\min (1,\underset{i\notin W_k,a_i^T{p}_k<0}{\min }\frac{b_i-a_i^T{x}_k}{a_i^T{p}_k})$

Die Nebenbedingung, die diese Länge beschränkt, wird in die Menge $W_{k+1}$ aufgenommen, da diese Nebenbedingung nun aktiv ist.

Literatur

• Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, Kapitel 16.5.
• Roger Fletcher: Practical methods of optimization. Second Edition. John Wiley & Sons, 1987, ISBN 978-0-471-49463-8, Kapitel 10.3.