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:<ref>Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 449. </ref>

<math>

\begin{array}{rcl} \min_{x \in \mathbb{R}^n} & \frac{1}{2} x^THx + c^Tx & = f(x) \\ s.t. & a_i^Tx \geq b_i & \forall i \in \mathcal{I} \\ & a_j^Tx = b_j & \forall j \in \mathcal{E} \end{array} </math>

wobei <math>n</math> die Anzahl der Entscheidungsvariablen ist. In der Zielfunktion <math>f(x)</math> entspricht <math>H</math> der Hesse-Matrix, die Mengen <math>\mathcal{I}</math> und <math>\mathcal{E}</math> indizieren die Ungleichheits- und Gleichheitsbedingungen. Oft wird dabei gefordert, dass die Matrix <math>H</math> positiv semidefinit ist, da dann das Optimierungsproblem konvex ist.

Active Set

Eine Nebenbedingung <math>i \in \mathcal{I}</math> ist aktiv an einem Punkt <math>x</math>, wenn <math>a_i^Tx = b_i</math> gilt.

Das Active Set <math>\mathcal{A}(x)</math> ist die Menge aller aktiven Bedingungen an einem gültigen Punkt <math>x</math>:

<math>\mathcal{A}(x) := \{j \in \mathcal{E} \cup i \in \mathcal{I} : a_i^Tx = b_i \}</math>

Algorithmus

Active-Set-Methoden setzen eine initiale gültige Lösung <math>x_0</math> voraus. Die Algorithmen berechnen dann in jeder Iteration einen gültigen Punkt <math>x_k</math>, bis ein Optimum erreicht ist. Dabei wird eine Menge <math>W_k</math> verwaltet, die angibt, welche Nebenbedingungen in der aktuellen Iteration aktiv sein sollen.<ref>Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 472. </ref>

 1  Gegeben: gültiger Punkt <math>x_0</math>, <math>W_0 \subseteq \mathcal{A}(x_0)</math>
 2
 3  for k=0,1,.. do
 4  berechne eine Suchrichtung <math>p_k</math>
 5  if <math>p_k = 0</math>
 6    berechne Lagrange-Multiplikatoren <math>\lambda_i</math>
 7    if <math>\forall i: \lambda_i \geq 0</math>
 8      terminiere und gib <math>x_k</math> aus
 9    else
10      finde Ungleichheitsbedingung <math>i \in W_k \cap \mathcal{I}</math> mit <math>\lambda_i < 0 </math>
11      <math>W_{k+1} = W_k \backslash i</math>
12    end
13  else
14    berechne Schrittlänge <math>\alpha_k</math>
15    if <math>\alpha_k < 1</math>
16      finde Nebenbedingung j die <math>\alpha_k</math> beschränkt
17      <math>W_{k+1} = W_k \cup j</math>
18    end
19    <math>x_{k+1} = x_k + \alpha_k p_k</math>
20  end

Berechnung der Suchrichtung p_k

Die Nebenbedingungen in <math>W_k</math> definieren einen Unterraum. Wenn <math>x</math> in der optimalen Lösung der Zielfunktion in diesem Unterraum ist, kann man die Suchrichtung als <math>p_k = x - x_k</math> definieren. Substituiert man dies in die Zielfunktion, erhält man die Suchrichtung <math>p_k</math> durch Lösen eines quadratischen Subproblems:<ref>Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 468. </ref>

<math>

\begin{array}{rcl} \min_{x \in \mathbb{R}^n} & \frac{1}{2} p_k^THp_k + g_k^Tp_k\\ s.t. & A^Tp_k = 0 & \forall i \in W_k \end{array} </math> wobei <math>g_k = Hx_k + c </math> der Gradient an der aktuellen Lösung ist und die Spalten der Matrix <math>A</math> die Vektoren <math>a_i, i \in W_k</math> sind.

Dieses Subproblem kann auf verschiedenen Weisen gelöst werden. Eine Möglichkeit ist dabei ein Nullspace-Ansatz:<ref>Roger Fletcher: Stable reduced Hessian updates for indefinite quadratic programming. Mathematical Programming (87.2) 2000, S. 251–264.</ref>

Hat man eine Matrix <math>Z</math>, deren Spalten eine Basis für den Kern der Matrix <math>A^T</math> bilden, kann man den gültigen Bereich des Subproblems durch <math> p_k = Zu </math> parametrisieren. Löst man nun das Gleichungssystem

<math> M u = -Z^Tg_k </math>,

wobei <math> M = Z^THZ</math> die reduzierte Hesse-Matrix ist, erhält man die Suchrichtung im originalen Problem.

Berechnung der Lagrange-Multiplikatoren λ_i

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

<math>

\sum_{i \in W_k \cap \mathcal{I}} a_i\lambda_i = g_k = Hx_k + c </math> Falls alle <math>\lambda_i \geq 0</math> sind, erfüllen <math>x_k</math> und <math>\lambda</math> die Karush-Kuhn-Tucker-Bedingungen, welche notwendige Kriterien für die Optimalität sind. Wenn zudem die Hesse-Matrix <math>H</math> positiv semidefinit ist, sind diese Bedingungen hinreichend und <math>x_k</math> ist die optimale Lösung des Problems. Entfernt man eine Ungleichheitsbedingung mit negativem Lagrange-Multiplikator aus <math>W_k</math> erhält man in der nächsten Iteration eine Suchrichtung.<ref>Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 469f. </ref>

Berechnung der Schrittlänge α_k

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

Alle Nebenbedingungen in <math> i \notin W_k </math> mit <math>a_i^Tp_k \geq 0</math> sind auch am Punkt <math>x_k + \alpha_k p_k</math> für alle <math>\alpha_k \geq 0 </math> erfüllt, da dann die Ungleichung

<math>a_i^T(x_k + \alpha_kp_k) = a_i^Tx_k + \alpha_k a_i^Tp_k \geq a_i^Tx_k \geq b_i</math>

gilt. Alle Nebenbedingungen <math> i \notin W_k </math> mit <math>a_i^Tp_k < 0</math> werden am neuen Punkt nur dann eingehalten, wenn für diese Nebenbedingungen die Ungleichung

<math>

a_i^Tx_k + \alpha_ka_i^Tp_k \geq b_i </math> gilt. Dies ist äquivalent mit der Bedingung

<math>

\alpha_k \leq \frac{b_i - a_i^Tx_k}{a_i^Tp_k} \qquad \forall \{i \notin W_k | a_i^Tp_k < 0\} </math>

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

<math>

\alpha_k = \min(1, \min_{i \notin W_k, a_i^Tp_k < 0} \frac{b_i-a_i^Tx_k}{a_i^Tp_k}) </math> Die Nebenbedingung, die diese Länge beschränkt, wird in die Menge <math>W_{k+1}</math> aufgenommen, da diese Nebenbedingung nun aktiv ist.<ref>Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 468f. </ref>

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.

Einzelnachweise

<references/>