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:^[1]

{\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 $n$ die Anzahl der Entscheidungsvariablen ist. In der Zielfunktion $f(x)$ entspricht $H$ der Hesse-Matrix, die Mengen ${\mathcal {I}}$ und ${\mathcal {E}}$ 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 {\mathcal {I}}$ ist aktiv an einem Punkt $x$ , wenn $a_{i}^{T}x=b_{i}$ gilt.

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

{\mathcal {A}}(x):=\{j\in {\mathcal {E}}\cup i\in {\mathcal {I}}: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.^[2]

 1  Gegeben: gültiger Punkt  $x_{0}$ ,  $W_{0}\subseteq {\mathcal {A}}(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  $\forall i:\lambda _{i}\geq 0$ 
 8      terminiere und gib  $x_{k}$  aus
 9    else
10      finde Ungleichheitsbedingung  $i\in W_{k}\cap {\mathcal {I}}$  mit  $\lambda _{i}<0$ 
11       $W_{k+1}=W_{k}\backslash 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:^[3]

{\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 $g_{k}=Hx_{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: ^[4]

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 {\mathcal {I}}}a_{i}\lambda _{i}=g_{k}=Hx_{k}+c

Falls alle $\lambda _{i}\geq 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.^[5]

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}\geq 0$ sind auch am Punkt $x_{k}+\alpha _{k}p_{k}$ für alle $\alpha _{k}\geq 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}\geq a_{i}^{T}x_{k}\geq 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}\geq b_{i}

gilt. Dies ist äquivalent mit der Bedingung

\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:

\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 $W_{k+1}$ aufgenommen, da diese Nebenbedingung nun aktiv ist.^[6]

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]