Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Scenario-Based Optimization for Multi-Stage Stochastic Decision Problems


G. Schildbach


Technological advancements over the past decades have increased the availability of ever more powerful and inexpensive hardware. This development has caused a substantial shift of research focus from classic control theory to advanced, optimization-based control methods. The latter are characterized by the fact that the decisions about the control actions are obtained by solving a numerical optimization program. In particular, model predictive control (MPC) offers an effective approach for handling multivariable control problems with a defined stage cost criterion and constraints on the inputs, states, and outputs.

The main contribution of this dissertation is the development of a novel method of scenario-based MPC (SCMPC) for handling multi-stage stochastic decision problems in a receding-horizon fashion. Indeed, MPC originally assumes that an exact model of the control system is available and there are no unknown disturbances, so it can accurately predict the system's state trajectory. However, uncertainty in these predictions can lead to substantial constraint violations and a significant performance degradation (in terms of stage costs) for the system in closed-loop operation. Various approaches to cope with uncertainty in MPC have previously been proposed. Robust MPC (RMPC) considers uncertainties contained inside a pre-fitted uncertainty set. For systems with stochastic disturbances, however, RMPC may result in a suboptimal performance. The reason is that this uncertainty model contains no probabilistic information and the decisions of RMPC are often based on extreme and unlikely disturbance realizations. Stochastic MPC (SMPC) approaches account for a probability distribution of the uncertainty. The constraints are typically relaxed in a probabilistic sense (e.g., as chance constraints), in exchange for an improved performance. This turns out to be a reasonable choice for many practical applications, where performance is critical. General distribution functions, however, are not amenable to numerical computations. Therefore many SMPC approaches are either computationally very demanding, or they are specialized to uncertainties of a particular distribution type (e.g., a normal distribution). The novel SCMPC method provides an alternative to SMPC, using sampled uncertainty scenarios of an arbitrary stochastic model (as opposed to explicit probability distributions). The number of scenarios is determined a priori, such that controller satisfies a given set of chance constraints on the system state. Compared to similar approaches that vii Abstract have previously been proposed, the novel SCMPC method requires a significantly lower number of scenarios. This reduces the computational complexity and improves the performance of the controller. Moreover, examples show that the desired level of constraint violations can accurately be achieved. The development of SCMPC in this dissertation is the result of multiple contributions. First, existing results in scenario-based optimization have established a direct link between the number of scenarios and bounds on the probability of constraint violations. These results are extended to problems with multiple chance constraints. Moreover, the existing bounds on the probability of constraint violations are improved in cases where a chance constraint has a limited support rank. The support rank is a novel concept defined in this thesis. The presented theory is applicable to very general stochastic optimization problems, in particular arising from multi-stage stochastic decision problems. Moreover, it potentially leads to a significant reduction in the number of scenarios, as compared to the previous theory. Second, the theory for a novel SCMPC method is introduced, with a focus on its mathematical properties. The theory builds on the results of the first contribution, and it additionally provides a new framework for analyzing the behavior of the closed loop under SCMPC. In contrast to previous SCMPC approaches, this framework allows for the chance constraints to be interpreted as the time-average of state constraint violations, rather than a joint probability over an open-loop prediction horizon. This leads to a potentially massive reduction in the number of required scenarios. Furthermore, the novel SCMPC approach features the possibility of sample removal (as known from scenario-based optimization), and it is compatible with previously considered methods of disturbance feedback for closed-loop predictions. Third, a possible implementation of SCMPC is examined in an extensive case study. The case study considers a networked supply chain distribution system with multiple products and uncertainty in the demands. It is shown that SCMPC is able to keep the prescribed service level constraints and significantly reduces the inventory holding costs. At the same time, SCMPC is computationally efficient for large-scale, complex problems with high-dimensional, correlated uncertainties. This type of problem can often not adequately be handled by means robust or stochastic optimization. Fourth, a new implementation of the scenario approach is presented for risk averse solutions to two-stage stochastic decision problems. Instead of a conventional mean-risk optimization, the new approach optimizes the stochastic objective function value with respect to a maximal shortfall probability. The advantage of this approach is its ability to handle high-dimensional uncertainties of a very general nature in a computationally efficient manner. Its application is demonstrated for a particular version of the farmer's problem.


Type of Publication:

(03)Ph.D. Thesis

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@PhDThesis { Xxx:2014:IFA_5008,
    author={G. Schildbach},
    title={{Scenario-Based Optimization for Multi-Stage Stochastic
	  Decision Problems}},
Permanent link