Direkt zum Inhalt

Lexikon der Mathematik: Dekomposition

Technik zur Zurückführung eines Optimierungsproblems auf mehrere kleinere Teilprobleme, sofern dies die spezielle Struktur des Ausgangsproblems zuläßt.

Wichtiges Beispiel einer derartigen Strukur stellen Probleme dar, bei denen die Zielfunktion und Nebenbedingungen additiv zerlegt werden können; man betrachte eine Zielfunktion \begin{eqnarray}f(\mathop{x}\limits_{\_}):=f({\mathop{x}\limits_{\_}}_{1},\ldots, {\mathop{x}\limits_{\_}}_{s});=\displaystyle \sum _{i=1}^{s}{f}_{i}({\mathop{x}\limits_{\_}}_{i})\end{eqnarray} unter Nebenbedingungen \(\displaystyle {\sum }_{i=1}^{s}{g}_{ij}({\mathop{x}\limits_{\_}}_{i})\ge 0,1\le j\le m\); \({h}_{i}({\mathop{x}\limits_{\_}}_{i})\ge 0,1,\le i\le s.\)

Hierbei sind die \({\mathop{x}\limits_{\_}}_{i}\) Variablenblöcke gewisser Dimensionen ni und die fi, gij sowie hi Funktionen von ℝni nach ℝ.

Bei der sogenannten Ressourcenzerlegung unterteilt man jede der m Nebenbedingungen \({\sum }_{i=1}^{s}{g}_{ij}({\mathop{x}\limits_{\_}}_{i})\ge 0\), \(1\le j\le m\), in s weitere Nebenbedingungen gijbij, 1 ≤ is, wobei zusätzlich \({\sum }_{i=1}^{s}{b}_{ij}=0\) verlangt wird.

Für jeden Variablenblock \({\mathop{x}\limits_{\_}}_{i}\) erhält man somit eine eigene zulässige Menge \begin{eqnarray}{M}_{i}:=\{{\mathop{x}\limits_{\_}}_{i}|{g}_{ij}({\mathop{x}\limits_{\_}}_{i})|\ge {b}_{ij},1\le j\le m,{h}_{}({\mathop{x}\limits_{\_}}_{i})\ge 0\}\end{eqnarray} sowie eine Funktion \begin{eqnarray}{\psi }_{i}({b}_{i1},\ldots, {b}_{im});=\inf \{f({\mathop{x}\limits_{\_}}_{i}),{\mathop{x}\limits_{\_}}_{i}\in {M}_{i}\}{\mathop{x}\limits_{\_}}_{i}\end{eqnarray}

(und ψi(bi1, …, bim) := ∞ falls Mi = ∅).

Schließlich optimiert man die Summe \({\sum }_{i=1}^{s}\psi ({b}_{i1},\ldots, {b}_{im})\) unter den m Nebenbedingungen \({\sum }_{i=1}^{s}{b}_{ij}=0,1\le j\le m.\). Letzteres führt i.allg. auf ein nichtglattes Optimierungsproblem. Bei der Anwendung von Iterationsmethoden sind dann in jedem Schritt die Teilprobleme der Form inf{\(\{{f}_{i}({\mathop{x}\limits_{\_}}_{i}),{\mathop{x}\limits_{\_}}_{i}\in {M}_{i}\}\)} zu lösen.

Die Ressourcenzerlegung wird auch als ein primales Dekompositionsverfahren bezeichnet. Analog gibt es duale Dekompositionsverfahren; bei diesen werden alle fi und die (gewichteten) gij in einer Funktion \begin{eqnarray}\displaystyle \sum _{i-1}^{s}({f}_{i}({\mathop{x}\limits_{\_}}_{i})+\displaystyle \sum _{j=1}^{m}{\lambda }_{j}.{g}_{ij}({\mathop{x}\limits_{\_}}_{i}))\end{eqnarray} zusammengefaßt, die dann weiter untersucht wird.

Eine andere zur Anwendung von Dekompositionstechniken geeignete Struktur liegt vor, wenn es lediglich einen Variablenblock \(\mathop{y}\limits_{\_}}\) gibt, der mit den anderen Blöcken \({\mathop{x}\limits_{\_}}_{i}\) in den Nebenbedingungen gekoppelt ist. Es handelt sich dann um ein Problem der Gestalt: Minimiere \begin{eqnarray}\displaystyle \sum _{i-1}^{s}({f}_{i}({\mathop{x}\limits_{\_}}_{i})+{f}_{s}+1(\mathop{y}\limits_{\_}))\end{eqnarray} unter Nebenbedingungen \({g}_{i}({\mathop{x}\limits_{\_}}_{i},\mathop{y}\limits_{\_})\ge 0,1\le i\le s\).

Ausgangspunkt von Lösungstechniken (darunter u. a. das Verfahren von Benders) ist die Idee, bei festem Wert von \(\mathop{y}\limits_{\_}\) unabhängige Teilprobleme in den \({\mathop{x}\limits_{\_}}_{i}\) zu erhalten. Erforderlich ist daran anschließend die Analyse des Zusammenhangs zwischen den erhaltenen Lösungen und dem Ausgangsproblem.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos