Active-Set-Methoden

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

Jedes quadratische Programm kann in eine standardisierte Form überführt werden:^[1]

${\displaystyle {\begin{array}{rcl}\min _{x\in \mathbb {R} ^{n}}&{\frac {1}{2}}x^{T}Hx+c^{T}x&=f(x)\\s.t.&a_{i}^{T}x\geq b_{i}&\forall i\in {\mathcal {I}}\\&a_{j}^{T}x=b_{j}&\forall j\in {\mathcal {E}}\end{array}}}${\displaystyle {\begin{array}{rcl}\min _{x\in \mathbb {R} ^{n}}&{\frac {1}{2}}x^{T}Hx+c^{T}x&=f(x)\\s.t.&a_{i}^{T}x\geq b_{i}&\forall i\in {\mathcal {I}}\\&a_{j}^{T}x=b_{j}&\forall j\in {\mathcal {E}}\end{array}}}

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

Eine Nebenbedingung ${\displaystyle i\in {\mathcal {I}}}${\displaystyle i\in {\mathcal {I}}} ist aktiv an einem Punkt ${\displaystyle x}${\displaystyle x}, wenn ${\displaystyle a_{i}^{T}x=b_{i}}${\displaystyle a_{i}^{T}x=b_{i}} gilt.

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

${\displaystyle {\mathcal {A}}(x):=\{j\in {\mathcal {E}}\cup i\in {\mathcal {I}}:a_{i}^{T}x=b_{i}\}}${\displaystyle {\mathcal {A}}(x):=\{j\in {\mathcal {E}}\cup i\in {\mathcal {I}}:a_{i}^{T}x=b_{i}\}}

Active-Set-Methoden setzen eine initiale gültige Lösung ${\displaystyle x_{0}}${\displaystyle x_{0}} voraus. Die Algorithmen berechnen dann in jeder Iteration einen gültigen Punkt ${\displaystyle x_{k}}${\displaystyle x_{k}}, bis ein Optimum erreicht ist. Dabei wird eine Menge ${\displaystyle W_{k}}${\displaystyle W_{k}} verwaltet, die angibt, welche Nebenbedingungen in der aktuellen Iteration aktiv sein sollen.^[2]

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

Die Nebenbedingungen in ${\displaystyle W_{k}}${\displaystyle W_{k}} definieren einen Unterraum. Wenn ${\displaystyle x}${\displaystyle x} in der optimalen Lösung der Zielfunktion in diesem Unterraum ist, kann man die Suchrichtung als ${\displaystyle p_{k}=x-x_{k}}${\displaystyle p_{k}=x-x_{k}} definieren. Substituiert man dies in die Zielfunktion, erhält man die Suchrichtung ${\displaystyle p_{k}}${\displaystyle p_{k}} durch Lösen eines quadratischen Subproblems:^[3]

${\displaystyle {\begin{array}{rcl}\min _{x\in \mathbb {R} ^{n}}&{\frac {1}{2}}p_{k}^{T}Hp_{k}+g_{k}^{T}p_{k}\\s.t.&A^{T}p_{k}=0&\forall i\in W_{k}\end{array}}}${\displaystyle {\begin{array}{rcl}\min _{x\in \mathbb {R} ^{n}}&{\frac {1}{2}}p_{k}^{T}Hp_{k}+g_{k}^{T}p_{k}\\s.t.&A^{T}p_{k}=0&\forall i\in W_{k}\end{array}}}

wobei ${\displaystyle g_{k}=Hx_{k}+c}${\displaystyle g_{k}=Hx_{k}+c} der Gradient an der aktuellen Lösung ist und die Spalten der Matrix ${\displaystyle A}${\displaystyle A} die Vektoren ${\displaystyle a_{i},i\in W_{k}}${\displaystyle a_{i},i\in W_{k}} sind.

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

Hat man eine Matrix ${\displaystyle Z}${\displaystyle Z}, deren Spalten eine Basis für den Kern der Matrix ${\displaystyle A^{T}}${\displaystyle A^{T}} bilden, kann man den gültigen Bereich des Subproblems durch ${\displaystyle p_{k}=Zu}${\displaystyle p_{k}=Zu} parametrisieren. Löst man nun das Gleichungssystem

${\displaystyle Mu=-Z^{T}g_{k}}${\displaystyle Mu=-Z^{T}g_{k}},

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

Falls die Suchrichtung ${\displaystyle p_{k}=0}${\displaystyle p_{k}=0} ist, ist ${\displaystyle x_{k}}${\displaystyle x_{k}} bereits optimal im aktuellen Unterraum. Man muss dann eine geeignete Ungleichheitsbedingung aus ${\displaystyle W_{k}}${\displaystyle W_{k}} entfernen. Die Lagrange-Multiplikatoren ${\displaystyle \lambda _{i}}${\displaystyle \lambda _{i}} erhält man durch Lösen eines linearen Gleichungssystems:

${\displaystyle \sum _{i\in W_{k}\cap {\mathcal {I}}}a_{i}\lambda _{i}=g_{k}=Hx_{k}+c}${\displaystyle \sum _{i\in W_{k}\cap {\mathcal {I}}}a_{i}\lambda _{i}=g_{k}=Hx_{k}+c}

Falls alle ${\displaystyle \lambda _{i}\geq 0}${\displaystyle \lambda _{i}\geq 0} sind, erfüllen ${\displaystyle x_{k}}${\displaystyle x_{k}} und ${\displaystyle \lambda }${\displaystyle \lambda } die Karush-Kuhn-Tucker-Bedingungen, welche notwendige Kriterien für die Optimalität sind. Wenn zudem die Hesse-Matrix ${\displaystyle H}${\displaystyle H} positiv semidefinit ist, sind diese Bedingungen hinreichend und ${\displaystyle x_{k}}${\displaystyle x_{k}} ist die optimale Lösung des Problems. Entfernt man eine Ungleichheitsbedingung mit negativem Lagrange-Multiplikator aus ${\displaystyle W_{k}}${\displaystyle W_{k}} erhält man in der nächsten Iteration eine Suchrichtung.^[5]

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

Alle Nebenbedingungen in ${\displaystyle i\notin W_{k}}${\displaystyle i\notin W_{k}} mit ${\displaystyle a_{i}^{T}p_{k}\geq 0}${\displaystyle a_{i}^{T}p_{k}\geq 0} sind auch am Punkt ${\displaystyle x_{k}+\alpha _{k}p_{k}}${\displaystyle x_{k}+\alpha _{k}p_{k}} für alle ${\displaystyle \alpha _{k}\geq 0}${\displaystyle \alpha _{k}\geq 0} erfüllt, da dann die Ungleichung

${\displaystyle a_{i}^{T}(x_{k}+\alpha _{k}p_{k})=a_{i}^{T}x_{k}+\alpha _{k}a_{i}^{T}p_{k}\geq a_{i}^{T}x_{k}\geq b_{i}}${\displaystyle a_{i}^{T}(x_{k}+\alpha _{k}p_{k})=a_{i}^{T}x_{k}+\alpha _{k}a_{i}^{T}p_{k}\geq a_{i}^{T}x_{k}\geq b_{i}}

gilt. Alle Nebenbedingungen ${\displaystyle i\notin W_{k}}${\displaystyle i\notin W_{k}} mit ${\displaystyle a_{i}^{T}p_{k}<0}${\displaystyle a_{i}^{T}p_{k}<0} werden am neuen Punkt nur dann eingehalten, wenn für diese Nebenbedingungen die Ungleichung

${\displaystyle a_{i}^{T}x_{k}+\alpha _{k}a_{i}^{T}p_{k}\geq b_{i}}${\displaystyle a_{i}^{T}x_{k}+\alpha _{k}a_{i}^{T}p_{k}\geq b_{i}}

gilt. Dies ist äquivalent mit der Bedingung

${\displaystyle \alpha _{k}\leq {\frac {b_{i}-a_{i}^{T}x_{k}}{a_{i}^{T}p_{k}}}\qquad \forall \{i\notin W_{k}|a_{i}^{T}p_{k}<0\}}${\displaystyle \alpha _{k}\leq {\frac {b_{i}-a_{i}^{T}x_{k}}{a_{i}^{T}p_{k}}}\qquad \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:

${\displaystyle \alpha _{k}=\min(1,\min _{i\notin W_{k},a_{i}^{T}p_{k}<0}{\frac {b_{i}-a_{i}^{T}x_{k}}{a_{i}^{T}p_{k}}})}${\displaystyle \alpha _{k}=\min(1,\min _{i\notin W_{k},a_{i}^{T}p_{k}<0}{\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 ${\displaystyle W_{k+1}}${\displaystyle W_{k+1}} aufgenommen, da diese Nebenbedingung nun aktiv ist.^[6]

• 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.

1. ↑ Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 449.
2. ↑ Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 472.
3. ↑ Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 468.
4. ↑ Roger Fletcher: Stable reduced Hessian updates for indefinite quadratic programming. Mathematical Programming (87.2) 2000, S. 251–264.
5. ↑ Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 469f.
6. ↑ Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 468f.

• Numerische Mathematik
• Nichtlineare Optimierung