Search

This thesis presents a novel hierarchical learning framework, Reinforcement Learning Optimal Control, for controlling nonlinear dynamical systems with continuous states and actions. The adapted approach mimics the neural computations that allow our brain to bridge across the divide between symbolic action-selection and low-level actuation control by operating at two levels of abstraction. First, current findings demonstrate that at the level of limb coordination human behaviour is explained by linear optimal feedback control theory, where cost functions match energy and timing constraints of tasks. Second, humans learn cognitive tasks involving learning symbolic level action selection, in terms of both model-free and model-based reinforcement learning algorithms. We postulate that the ease with which humans learn complex nonlinear tasks arises from combining these two levels of abstraction. The Reinforcement Learning Optimal Control framework learns the local task dynamics from naive experience using an expectation maximization algorithm for estimation of linear dynamical systems and forms locally optimal Linear Quadratic Regulators, producing continuous low-level control. A high-level reinforcement learning agent uses these available controllers as actions and learns how to combine them in state space, while maximizing a long term reward. The optimal control costs form training signals for high-level symbolic learner. The algorithm demonstrates that a small number of locally optimal linear controllers can be combined in a smart way to solve global nonlinear control problems and forms a proof-of-principle to how the brain may bridge the divide between low-level continuous control and high-level symbolic action selection. It competes in terms of computational cost and solution quality with state-of-the-art control, which is illustrated with solutions to benchmark problems.

Stochastic programming models are large-scale optimization problems that are used to facilitate decision-making under uncertainty. Optimization algorithms for such problems need to evaluate the exptected future costs of current decisions, often referred to as the recourse function. In practice, this calculation is computationally difficult as it requires the evaluation of a multidimensional integral whose integrand is an optimization problem. In turn, the recourse function has to be estimated using techniques such as scenario trees or Monte Carlo methods, both of which require numerous function evaluations to produce accurate results for large-scale problems with multiple periods and high-dimensional uncertainty. In this thesis, we introduce an Importance Sampling framework for stochastic programming that can produce accurate estimates of the recourse function using a small number of samples. Previous approaches for importance sampling in stochastic programming were limited to problems where the uncertainty was modelled using discrete random variables, and the recourse function was additively separable in the uncertain dimensions. Our framework avoids these restrictions by pairing Markov Chain Monte Carlo methods with Kernel Density Estimation algorithms to build a non-parametric Importance Sampling distribution, which can then be used to produce a low-variance estimate of the recourse function. We demonstrate the increased accuracy and efficiency of our approach using variants of well-known multistage stochastic programming problems. Our numerical results show that our framework produces more accurate estimates of the optimal value of stochastic programming models, especially for problems with moderate-to-high variance distributions or rare-event distributions. For example, in some applications, we found that if the random variables are drawn from a rare-event distribution, our proposed algorithm can achieve four times reduction in the mean square error and variance given by other existing methods (e.g.: SDDP with Crude Monte Carlo or SDDP with Quasi Monte Carlo method) for the same number of samples. Or when the random variables are drawn from the high variance distribution, our proposed algorithm can reduce the variance averagely by two times compared to the results obtained by other methods for approximately the same level of mean square error and a fixed number of samples. We use our proposed algorithm to solve a capacity expansion planning problem in the electric power industry. The model includes the unit commitment problem and maintenance scheduling. It allows the investors to make optimal decisions on the capacity and the type of generators to build in order to minimize the capital cost and operating cost over a long period of time. Our model computes the optimal schedule for each of the generators while meeting the demand and respecting the engineering constraints of each generator. We use an aggregation method to group generators of similar features, in order to reduce the problem size. The numerical experiment shows that by clustering the generators of the same technology with similar size together and apply the SDDP algorithm with our proposed sampling framework on this simplified formulation, we are able to solve the problem using only one fourth the amount of time to solve the original problem by conventional algorithms. The speed-up is achieved without a significant reduction in the quality of the solution.

A wide variety of decision problems in engineering, science and economics involve uncertain parameters whose values are unknown to the decision maker when the decisions are made. Ignoring this uncertainty can lead to inferior solutions that perform poorly in practice. Many decision problems under uncertainty also span across multiple time stages and thus involve adaptive decisions. Such problems are naturally formulated as multi-stage stochastic programs. Despite its wide applicability, stochastic programming suffers from three major shortcomings. Firstly, stochastic programming models assume precise knowledge of the probability distribution of the uncertain parameters, an assumption which may be difficult to justify in practice when only a finite number of historical observations is available. Secondly, stochastic programming models typically minimize expected cost or disutility. This necessitates the evaluation of a multivariate integral, which can be computationally burdensome, particularly in the presence of high-dimensional uncertainty. Thirdly, multi-stage stochastic programs are inherently intractable as they involve infinitely many constraints as well as functional decision variables ranging over an infinite-dimensional space. In addition, many practical problems also involve integer decision variables, which further aggravates the complexity of even finding a feasible solution. The first main objective of this thesis is to formulate and analyze distributionally robust optimization models that overcome the aforementioned shortcomings. In distributionally robust optimization we seek decisions that perform best in view of the worst-case distribution from within some family of distributions of the uncertain parameters. Distributionally robust models thus relax the unrealistic assumption of a known probability distribution. Instead, they rely on the availability of an ambiguity set, that is, a family of distributions consistent with the decision maker's prior information. By employing the classical duality theory for moment problems, distributionally robust optimization problems can be reduced to finite dimensional conic programs, which are often computationally tractable. In this thesis, we study a distributionally robust variant of the multi-product newsvendor problem. While the arising formulation is proven to be NP-hard due to the presence of a sum of maxima term, we propose a tractable conservative approximation in the form of quadratic decision rules. We further study distributionally robust uncertainty quantification and chance constrained programming problems. We introduce a standardized ambiguity set that captures a wide variety of popular ambiguity sets as special cases, and we present for the first time a thorough complexity analysis of distributionally robust uncertainty quantification and chance constrained programming. The second main objective of this thesis is to develop scalable approximations for dynamic optimization problems under uncertainty. For two-stage problems with continuous recourse decisions there exist already some tractable approximation schemes. However, to date hardly any attempts have been undertaken to solve (distributionally) robust dynamic problems with integer recourse decisions. In this thesis, we present a new finite adaptability approximation for two-stage robust binary programs. We show that these problems admit mixed-integer linear programming approximations that are not much harder to solve than their deterministic counterparts. For multi-stage decision problems with continuous recourse decisions, we further propose a data-driven dynamic programming algorithm that allows the decision maker to incorporate the historical observations directly into the solution procedure in an asymptotically consistent manner. We then combine the data-driven method with robust optimization techniques to alleviate the overfitting effects inherent in problems with sparse historical observations.

In this thesis, we consider optimisation problems which involve ambiguous chance constraints, i.e., probabilistic constraints where the probability distribution of the primitive uncertainties is at least partly unknown. In this case, we can define an ambiguity set that contains all distributions consistent with our prior knowledge of the uncertainty and take either a pessimistic (worst-case) or optimistic (best-case) view of the world. The former view can be used to actively optimise a system whilst guaranteeing some predefined level of safety; being robust even if the worst-case scenario materialises. The latter view can be used to actively optimise a system where it is required to reconstruct realisations of a random variable whose distribution is not known precisely. We characterise the ambiguity set through generalised moment bounds and structural properties such as symmetry, unimodality, or independence patterns. Sufficient conditions are presented under which the corresponding chance constraints admit equivalent explicit tractable conic reformulations that can be solved with off-the-shelf solvers. However, in general, ambiguous chance constrained problems are provably difficult and we suggest efficiently computable conservative approximations. To illustrate the effectiveness of our reformulations, we give two detailed and novel examples. First, we consider the pricing problem of a provider of cloud computing services. This provider faces uncertain demand and wishes to maximise profit, whilst maintaining a desired level of quality of service. We show that such a problem naturally fits within the pessimistic ambiguous chance constraint framework. Second, we consider the problem of improving the quality of a photographic image by reconstructing and then removing noise. We show that such a problem can be formulated as an optimistic ambiguous chance constrained program that generalises, and offers new insight to, an existing powerful image denoising approach.

Decision making under uncertainty is a widely-studied area spanning a number of fields such as computational optimization, control theory, utility theory and game theory. A typical problem of decision making under uncertainty requires the design of an optimal decision rule, control policy, or behavioural function, that takes into account all available information regarding the uncertain parameters and returns the decision that is most suitable for the given objective. A popular requirement is to determine robust decisions that maintain certain desired characteristics despite the presence of uncertainty. In this thesis, we study three distinct problems that involve the design of robust decisions under different types of uncertainty. We investigate a dynamic multi-stage control problem with stochastic exogenous uncertainty, a dynamic two-stage robust optimization problem with epistemic exogenous uncertainty, and finally a game theoretic problem with both stochastic endogenous and epistemic exogenous uncertainty. Specifically, a) we develop an efficient algorithm that bounds the performance loss of affine policies operating in discrete-time, finite-horizon, stochastic systems with expected quadratic costs and mixed linear state and input constraints. Finding the optimal control policy for such problems is generally computationally intractable, but suboptimal policies can be computed by restricting the class of admissible policies to be affine on the observation. Our algorithm provides an estimate of the loss of optimality due to the use of such affine policies, and it is based on a novel dualization technique, where the dual variables are restricted to have an affine structure; b) we develop an efficient algorithm to bound the suboptimality of linear decision rules in two-stage dynamic linear robust optimization problems, where they have been shown to suffer a worst-case performance loss of the order $\Omega(\sqrt{m})$ for problems with $m$ linear constraints. Our algorithm is based on a scenario selection technique, where the original problem is evaluated only over a finite subset of the possible uncertain parameters. This set is constructed from the Lagrange multipliers associated with the computation of the linear adaptive decision rules. The resulting instance-wise bounds outperform known bounds, including the aforementioned worst-case bound, in the vast majority of problem instances; c) we develop an algorithm that enumerates all behavioural functions that are at equilibrium in a game where players face epistemic uncertainty regarding their opponent's utility functions. Traditionally, these games are solved as complete-information games where players are assumed to be risk-neutral, with a utility function that is positively affine in the monetary payoffs. We demonstrate that this assumption imposes severe limitations on the problem structure, and we propose that these games should be formulated as incomplete private information games where each player may have any increasing or increasing concave utility function. If the players are ambiguity-averse, then under these assumptions, they play either a pure strategy, a max-min strategy, or a convex combination of the two. By utilizing this result, we develop an algorithm that can enumerate all equilibria of the game.

The ongoing deregulation of energy markets has greatly impacted the power industry. In this new environment, firms shift their focus from cost-efficient energy supply to more profit-oriented goals, trading energy at the price set by the market. Consequently, traditional management approaches based on cost minimisation disregarding market uncertainties and financial risk are no longer applicable. In this thesis, we investigate medium-term planning problems in deregulated energy markets. These problems typically involve taking decisions over many periods and are affected by significant uncertainty, most notably energy price uncertainty. Multistage stochastic programming provides a flexible framework for modelling this type of dynamic decision-making process: it allows for future decisions to be represented as decision rules, that is, as measurable functions of the observable data. Multistage stochastic programs are generally intractable. Instead of using classical scenario tree-based techniques, we reduce their computational complexity by restricting the set of decision rules to those that exhibit an affine or quadratic data dependence. Decision rule approaches typically lead to polynomial-time solution schemes and are therefore ideal to tackle industry-size energy problems. However, the favourable scalability properties of the decision rule approach come at the cost of a loss of optimality. Fortunately, the degree of suboptimality can be measured efficiently by solving the dual of the stochastic program under consideration in linear or quadratic decision rules. The approximation error is then estimated by the gap between the optimal values of the primal and the dual decision rule problems. We develop this dual decision rule technique for general quadratic stochastic programs. Using these techniques, we solve a mean-variance portfolio optimisation problem faced by an electricity retailer. We observe that incorporating adaptivity into the model is beneficial in a risk minimisation framework, especially in the presence of high spot price variability or large market prices of risk. For a problem instance involving six electricity derivatives and a monthly planning horizon with daily trading periods, the solution time amounts to a few seconds. In contrast, scenario tree methods result in excessive run times since they require a prohibitively large number of scenarios to preclude arbitrage. Moreover, we address the medium-term scheduling of a cascaded hydropower system. To reduce computational complexity, we partition the planning horizon into hydrological macroperiods, each of which accommodates many trading microperiods, and we account for intra-stage variability through the use of price duration curves. Using linear decision rules, a solution to a real-sized hydro storage problem with a yearly planning horizon comprising 52 weekly macroperiods can be located in a few minutes, with an approximation error of less than 10%.

Dynamic decision problems affected by uncertain data are notoriously hard to solve due to the presence of adaptive decision variables which must be modeled as functions or decision rules of some (or all) of the uncertain parameters. All exact solution techniques suffer from the curse of dimensionality while most solution schemes assume that the decision-maker cannot influence the sequence in which the uncertain parameters are revealed. The main objective of this thesis is to devise tractable approximation schemes for dynamic decision-making under uncertainty. For this purpose, we develop new decision rule approximations whereby the adaptive decisions are approximated by finite linear combinations of prescribed basis functions. In the first part of this thesis, we develop a tractable unifying framework for solving convex multi-stage robust optimization problems with general nonlinear dependence on the uncertain parameters. This is achieved by combining decision rule and constraint sampling approximations. The synthesis of these two methodologies provides us with a versatile data-driven framework, which circumvents the need for estimating the distribution of the uncertain parameters and offers almost complete freedom in the choice of basis functions. We obtain a-priori probabilistic guarantees on the feasibility properties of the optimal decision rule and demonstrate asymptotic consistency of the approximation. We then investigate the problem of hedging and pricing path-dependent electricity derivatives such as swing options, which play a crucial risk management role in today’s deregulated energy markets. Most of the literature on the topic assumes that a swing option can be assigned a unique fair price. This assumption nevertheless fails to hold in real-world energy markets, where the option admits a whole interval of prices consistent with those of traded instruments. We formulate two large-scale robust optimization problems whose optimal values yield the endpoints of this interval. We analyze and exploit the structure of the optimal decision rule to formulate approximate problems that can be solved efficiently with the decision rule approach discussed in the first part of the thesis. Most of the literature on stochastic and robust optimization assumes that the sequence in which the uncertain parameters unfold is independent of the decision-maker’s actions. Nevertheless, in numerous real-world decision problems, the time of information discovery can be influenced by the decision-maker. In the last part of this thesis, we propose a decision rule-based approximation scheme for multi-stage problems with decision-dependent information discovery. We assess our approach on a problem of infrastructure and production planning in offshore oil fields.

Optimisation under uncertainty has a long and distinguished history in operations research. Decision-makers realised early on that the failure to account for uncertainty in optimisation problems can lead to substantial unexpected losses or even infeasible solutions. Therefore, approximating the uncertain parameters by their average or nominal values may result in decisions that perform poorly in scenarios that deviate from the average. For the last sixty years, scenario tree-based stochastic programming has been the method of choice for solving optimisation problems affected by parameter uncertainty. This method approximates the random problem parameters by finite scenarios that can be arranged as a tree. Unfortunately, this approximation suffers from a curse of dimensionality: the tree needs to branch whenever new uncertainties are revealed, and thus its size grows exponentially with the number of decision stages. It has recently been argued that stochastic programs can quite generally be made tractable by restricting the space of recourse decisions to those that exhibit a linear data dependence. An attractive feature of this linear decision rule approximation is that it typically leads to polynomial-time solution schemes. Unfortunately, the simple structure of linear decision rules sacrifices optimality in return for scalability. The worst-case performance of linear decision rules is in fact rather disappointing. When applied to two-stage robust optimisation problems with m linear constraints, the underlying worst-case approximation ratio has been shown to be of the order O(√m). Therefore, in this thesis we endeavour to construct efficiently computable instance-wise bounds on the loss of optimality incurred by the linear decision rule approximation. The contributions of this thesis are as follows. (i)We develop an efficient algorithm for assessing the loss of optimality incurred by the linear decision rule approximation. The key idea is to apply the linear decision rule restriction not only to the primal but also to a dual version of the stochastic program. Since both problems share a similar structure, both problems can be solved in polynomial-time. The gap between their optimal values estimates the loss of optimality incurred by the linear decision rule approximation. (ii) We design an improved approximation based on non-linear decision rules, which can be useful if the optimality gap of the linear decision rules is deemed unacceptably high. The idea takes advantage of the fact that one can always map a linearly parameterised non-linear function into a higher dimensional space, where it can be represented as a linear function. This allows us to utilise the machinery developed for linear decision rules to produce superior quality approximations that can be obtained in polynomial time. (iii) We assess the performance of the approximations developed in two operations management problems: a production planning problem and a supply chain design problem. We show that near-optimal solutions can be found in problem instances with many stages and random parameters. We additionally compare the quality of the decision rule approximation with classical approximation techniques. (iv) We develop a systematic approach to reformulate multi-stage stochastic programs with a large (possibly infinite) number of stages as static robust optimisation problem that can be solved with a constraint sampling technique. The method is motivated via an investment planning problem in the electricity industry.

Portfolio selection is a decision problem that can be formulated as a mathematical optimisation program. Ever since portfolio selection has been first modelled as a mathematical optimisation problem, a number of frameworks have emerged. These different frameworks aim to address the shortfalls and limitations of previous models. However, most of these models rely on the weak assumption, that the input parameters are known exactly. In the existence of uncertainty surrounding the input parameters, the outcome of a deterministic optimisation problem might be overoptimistic with unexpected consequences in certain scenarios. Robust optimisation deals with the uncertainty surrounding the input parameters. This framework approaches the uncertainty as deterministic and the solution provides certain guarantees, given that the realized scenario is within the considered uncertainty set. The consideration of all possible scenarios leads to more sensible decisions. Robust optimisation frameworks are quite popular in engineering, whereas an overoptimistic solution might yield a catastrophic outcome. This thesis aims to investigate the portfolio construction using robust optimisation frameworks. More specifically, we formulate existing deterministic optimisation models as robust optimisation models and show that they remain tractable under several types of uncertainty. In particular, we examine the distributionally robust Omega Ratio maximization (through solving the Omega Ratio as a convex optimisation problem) and we show that it remains tractable under mixture distribution, ellipsoidal and box uncertainty. In order to illustrate this, we first show that the Omega Ratio maximization is a convex optimisation problem. In addition, we show that the robust counterpart of the Equally-weighted Risk Contribution problem can also be formulated as a convex optimisation problem. We finally provide numerical evidence that suggest the existence of a positive premium for the portfolios constructed using robust formulations versus the deterministic models. The numerical evidence is based on real-life data that span the pre-and post- credit crisis periods.

Although the consideration of foreign investments may have a positive impact on the overall market risk of the portfolio through diversi cation, it also adds a new source of uncertainty due to changes in the value of the currency. We investigate portfolio optimization models that account separately for the local asset returns and the currency returns, providing the investor with a full investment strategy. We tackle the uncertainty inherent to the estimation of the parameters with the aid of robust optimization techniques. We show how, by using appropriate assumptions regarding the formulation of the uncertainty sets, the original non-linear and non-convex models may be reformulated as second order cone or as semide nite programs. Additionally to the guarantees provided by robust optimization, we consider the use of hedging instruments such as forward contracts and options. The proposed hedging strategies are implemented from a portfolio perspective, and therefore do not depend on the individual value or behavior of any particular asset or currency. Hedging decisions are taken at the same time as investment decisions in a holistic approach to portfolio management. While dynamic decision making has traditionally been represented as scenario trees, these may become severely intractable and di cult to compute with an increasing number of time periods. We present an alternative approach to multiperiod international portfolio optimization based on an a ne dependence between the decision variables and the past returns. We add to our formulation the minimization of the worst case value-at-risk and show the close relationship with robust optimization. The proposed theoretical framework is supported by various numerical experiments with simulated and historical market data demonstrating its potential bene ts.