Header

UZH-Logo

Maintenance Infos

A complementarity approach to multistage stochastic linear programs


Siegrist, Simon. A complementarity approach to multistage stochastic linear programs. 2005, University of Zurich, Faculty of Science.

Abstract

Das Gebiet der Stochastischen Programmierung gehört in die Problemklasse der "Entscheidungsfindung unter Unsicherheit". Anwendungen finden sich weitverbreitet in den Feldern der industriellen Produktion und der finanziellen Planung neben vielen anderen. Die Arbeit befasst sich mit der Approximation von 'Multistage Stochastic Linear Programs' (MSLP), wo einige Modelldaten als zufällig vorausgesetzt werden und sich sukzessiv in diskreter Zeit $t=1,...,T$ realisieren, wobei $T$ ein endlicher Planungshorizont sei. Entscheidungen zum Zeitpunkt $t$ sollen so gefällt werden, dass die Summe ihrer unmittelbar anfallenden Kosten und den erwarteten Recourse Kosten minimiert wird, gegeben die vorangegangenen Entscheidungen und die Information, welche bis $t$ verfügbar ist. Falls die Anzahl Szenarien endlich ist, dann lässt sich das Optimierungsproblem als Linearprogramm formulieren und auch direkt lösen, sofern diese Anzahl nicht zu gross ist. Numerische Approximationsmethoden sind häufig unumgänglich, insbesondere falls die zufälligen Daten stetig verteilt sind. Es gibt einige Methoden für den Fall $T=2$, welche auf diese Situation zugeschnitten sind. Leider stellten sich diese als unpraktisch heraus, um sie auf den Fall $T≥3$ zu erweitern, weil in diesem Fall die Auswertung eines einzelnen Recourse Funktionswertes nahezu denselben Schwierigkeitsgrad wie die Bestimmung des optimalen Zielfunktionswertes des Gesamtproblems aufweist. Da wir den Fall von stetig verteilten Daten miteinschliessen, wird MSLP als infinites Linearprogramm formuliert, welches auch eine infinite duale Form besitzt. Die Optimalitätslücke eines zulässigen primal-dual Paares kann als Erwartungswert einer nichtnegativen Zufallsvariablen ausgedrückt werden, in der Arbeit 'Komplementaritätsvariable' genannt. Eine Aggregation von Restriktionen und Entscheidungen scheint ein natürlicher Zugangzu sein, um MSLP numerisch handhabbar zu machen. Wir analysieren vor allem Modelle, bei denen jede optimale Lösung eines geeignet aggregierten Dualproblems zulässig im originalen Dualproblem ist, was auf untere Schranken führt. Danach schlagen wir einen Weg basierend auf den aggregierten Lösungen vor, wie sich rekursiv durch das Lösen einer Folge von kleinen linearen und quadratischen Subproblemen eine zulässige Entscheidungspolitik in der Originalaufgabe definieren lässt. Unter geeigneten Modellannahmen und abhängig vom Aggregationsfehler erweist sich diese Entscheidungspolitik als nahe liegend zu der aggregierten optimalen Primallösung. Ausserdem wird das Worst-Case Verhalten der Komplementaritätsvariable, welche sich aus der rekursiven Entscheidungspolitik und der aggregierten optimalen Duallösung ergibt, sowohl in Erwartung als auch in einem fast sicheren Sinn analysiert. Das letztere Resultat wird verwendet, um die Endlichkeit des vorgeschlagenen Verfeinerungsalgorithmus MSLP-APPROX nachzuweisen, welcher auf simulierten Werten der Komplementaritätsvariable basiert. Wir beweisen auch, dass - bei sukzessiver Erhöhung der Stichprobe und eines Genauigkeitsparameters von MSLP-APPROX - die (schwachen) Häufungspunkte der Lösungskandidaten das Originalproblem lösen. Um das praktische Verhalten von MSLP-APPROX zu veranschaulichen, werden im letzten Teil numerische Resultate präsentiert. The field of Stochastic Programming belongs to the problem class of "Decision-Making under Uncertainty''. Applications are widely available in the areas of industrial production and financial planning, among many others. The thesis deals with the approximation of Multistage Stochastic Linear Programs (MSLP) where some model data are assumed to be random and successively realized at time $t=1,...,T$ where $T $ is a finite planning horizon. Decisions at time $t$ should be made such that the sum of their immediate costs and the expected recourse costs is minimized, given the previous decisions and the information available up to $t$. When the number of scenarios is finite, the optimization problem can be formulated as a linear program and may also be solved directly, provided that this number is not too high. Numerical approximation methods are often inevitable, especially if the random data are continuously distributed. There are some methods available for the case $T=2$ designed for this situation. Unfortunately, they turned out to be impractical to extend to the case $T≥3$ because, in this case, the computation of a single recourse function value has almost the same degree of difficulty as determining the optimal objective value of the overall problem.Since we include the case of continuously distributed data, MSLP is expressed as an infinite linear program which also has an infinite dual form. The optimality gap of a feasible primal-dual pair is expressed as the expectation of a nonnegative random variable, in the thesis called the 'complementarity variable'. Aggregation of constraints and decisions seems to be a natural approach to make MSLP numerically manageable. We analyze particularly models where every optimal solution of a suitably aggregated dual problem is feasible in the original dual problem, leading to lower bounds. After that, based on the aggregated solutions, we propose a way to define recursively a feasible decision policy in the original primal problem by solving a sequence of small linear and quadratic subproblems. Under suitable model assumptions and depending on the aggregation error, the recursive decision policy turns out to be close to the aggregated optimal primal solution. Furthermore, the worst-case behavior of the complementarity variable resulting from the recursive decision policy and the aggregated optimal dual solution is analyzed both in expectation and in an almost sure sense. The latter result is used to prove the finiteness of the proposed refinement algorithm MSLP-APPROX which is based on simulated values of the complementarity variable. We also prove that - by successively increasing both the sample size and an accuracy parameter of MSLP-APPROX} - the (weak) accumulation points of the candidate solutions solve the original problem. In the last part, numerical results are presented in order to illustrate the practical behavior of MSLP-APPROX.

Abstract

Das Gebiet der Stochastischen Programmierung gehört in die Problemklasse der "Entscheidungsfindung unter Unsicherheit". Anwendungen finden sich weitverbreitet in den Feldern der industriellen Produktion und der finanziellen Planung neben vielen anderen. Die Arbeit befasst sich mit der Approximation von 'Multistage Stochastic Linear Programs' (MSLP), wo einige Modelldaten als zufällig vorausgesetzt werden und sich sukzessiv in diskreter Zeit $t=1,...,T$ realisieren, wobei $T$ ein endlicher Planungshorizont sei. Entscheidungen zum Zeitpunkt $t$ sollen so gefällt werden, dass die Summe ihrer unmittelbar anfallenden Kosten und den erwarteten Recourse Kosten minimiert wird, gegeben die vorangegangenen Entscheidungen und die Information, welche bis $t$ verfügbar ist. Falls die Anzahl Szenarien endlich ist, dann lässt sich das Optimierungsproblem als Linearprogramm formulieren und auch direkt lösen, sofern diese Anzahl nicht zu gross ist. Numerische Approximationsmethoden sind häufig unumgänglich, insbesondere falls die zufälligen Daten stetig verteilt sind. Es gibt einige Methoden für den Fall $T=2$, welche auf diese Situation zugeschnitten sind. Leider stellten sich diese als unpraktisch heraus, um sie auf den Fall $T≥3$ zu erweitern, weil in diesem Fall die Auswertung eines einzelnen Recourse Funktionswertes nahezu denselben Schwierigkeitsgrad wie die Bestimmung des optimalen Zielfunktionswertes des Gesamtproblems aufweist. Da wir den Fall von stetig verteilten Daten miteinschliessen, wird MSLP als infinites Linearprogramm formuliert, welches auch eine infinite duale Form besitzt. Die Optimalitätslücke eines zulässigen primal-dual Paares kann als Erwartungswert einer nichtnegativen Zufallsvariablen ausgedrückt werden, in der Arbeit 'Komplementaritätsvariable' genannt. Eine Aggregation von Restriktionen und Entscheidungen scheint ein natürlicher Zugangzu sein, um MSLP numerisch handhabbar zu machen. Wir analysieren vor allem Modelle, bei denen jede optimale Lösung eines geeignet aggregierten Dualproblems zulässig im originalen Dualproblem ist, was auf untere Schranken führt. Danach schlagen wir einen Weg basierend auf den aggregierten Lösungen vor, wie sich rekursiv durch das Lösen einer Folge von kleinen linearen und quadratischen Subproblemen eine zulässige Entscheidungspolitik in der Originalaufgabe definieren lässt. Unter geeigneten Modellannahmen und abhängig vom Aggregationsfehler erweist sich diese Entscheidungspolitik als nahe liegend zu der aggregierten optimalen Primallösung. Ausserdem wird das Worst-Case Verhalten der Komplementaritätsvariable, welche sich aus der rekursiven Entscheidungspolitik und der aggregierten optimalen Duallösung ergibt, sowohl in Erwartung als auch in einem fast sicheren Sinn analysiert. Das letztere Resultat wird verwendet, um die Endlichkeit des vorgeschlagenen Verfeinerungsalgorithmus MSLP-APPROX nachzuweisen, welcher auf simulierten Werten der Komplementaritätsvariable basiert. Wir beweisen auch, dass - bei sukzessiver Erhöhung der Stichprobe und eines Genauigkeitsparameters von MSLP-APPROX - die (schwachen) Häufungspunkte der Lösungskandidaten das Originalproblem lösen. Um das praktische Verhalten von MSLP-APPROX zu veranschaulichen, werden im letzten Teil numerische Resultate präsentiert. The field of Stochastic Programming belongs to the problem class of "Decision-Making under Uncertainty''. Applications are widely available in the areas of industrial production and financial planning, among many others. The thesis deals with the approximation of Multistage Stochastic Linear Programs (MSLP) where some model data are assumed to be random and successively realized at time $t=1,...,T$ where $T $ is a finite planning horizon. Decisions at time $t$ should be made such that the sum of their immediate costs and the expected recourse costs is minimized, given the previous decisions and the information available up to $t$. When the number of scenarios is finite, the optimization problem can be formulated as a linear program and may also be solved directly, provided that this number is not too high. Numerical approximation methods are often inevitable, especially if the random data are continuously distributed. There are some methods available for the case $T=2$ designed for this situation. Unfortunately, they turned out to be impractical to extend to the case $T≥3$ because, in this case, the computation of a single recourse function value has almost the same degree of difficulty as determining the optimal objective value of the overall problem.Since we include the case of continuously distributed data, MSLP is expressed as an infinite linear program which also has an infinite dual form. The optimality gap of a feasible primal-dual pair is expressed as the expectation of a nonnegative random variable, in the thesis called the 'complementarity variable'. Aggregation of constraints and decisions seems to be a natural approach to make MSLP numerically manageable. We analyze particularly models where every optimal solution of a suitably aggregated dual problem is feasible in the original dual problem, leading to lower bounds. After that, based on the aggregated solutions, we propose a way to define recursively a feasible decision policy in the original primal problem by solving a sequence of small linear and quadratic subproblems. Under suitable model assumptions and depending on the aggregation error, the recursive decision policy turns out to be close to the aggregated optimal primal solution. Furthermore, the worst-case behavior of the complementarity variable resulting from the recursive decision policy and the aggregated optimal dual solution is analyzed both in expectation and in an almost sure sense. The latter result is used to prove the finiteness of the proposed refinement algorithm MSLP-APPROX which is based on simulated values of the complementarity variable. We also prove that - by successively increasing both the sample size and an accuracy parameter of MSLP-APPROX} - the (weak) accumulation points of the candidate solutions solve the original problem. In the last part, numerical results are presented in order to illustrate the practical behavior of MSLP-APPROX.

Statistics

Downloads

4 downloads since deposited on 05 Jun 2019
4 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Dissertation (monographical)
Referees:Barbour Andrew D, Kall P
Communities & Collections:UZH Dissertations
Dewey Decimal Classification:Unspecified
Language:English
Place of Publication:Zürich
Date:2005
Deposited On:05 Jun 2019 14:46
Last Modified:07 Apr 2020 07:15
Number of Pages:91
OA Status:Green
Related URLs:https://www.recherche-portal.ch/primo-explore/fulldisplay?docid=ebi01_prod005148385&context=L&vid=ZAD&search_scope=default_scope&tab=default_tab&lang=de_DE (Library Catalogue)

Download

Green Open Access

Download PDF  'A complementarity approach to multistage stochastic linear programs'.
Preview
Content: Published Version
Language: English
Filetype: PDF
Size: 649kB