In a hydro-dominated system, such as New Zealand, the continual improvement and development of effective optimization and simulation software to inform decision making is necessary for effective resource management. Stochastic Constructive Dual Dynamic Programming (SCDDP) is a technique which has been effectively applied to the New Zealand system for optimization and simulation. This variant of Dynamic Programming (DP) allows optimization to occur in the dual space reducing the computational complexity and allows solutions from a single run to be formed as price signal surfaces and trajectories. However, any application of this method suffers from issues with computational tractability for higher reservoir numbers. Furthermore, New Zealand specific applications currently provide limited information on the system as they all use the same two-reservoir approximation of the New Zealand system. This limitation is of increasing importance with the decentralization of the New Zealand electricity sector. In this thesis we develop this theory with respect to two key goals: • To advance the theory surrounding SCDDP to be generalizable to higher reservoir numbers through the application of the point-wise algorithm explored in R. A. Read, Dye, S. & Read, E.G. (2012) to the stochastic case. • To develop at least two new and distinct two-reservoir SCDDP representations of the New Zealand system to provide a theoretical basis for greater flexibility in simulation and optimization of hydro-thermal scheduling in the New Zealand context.

A phylogenetic tree is used to model gene evolution and species evolution using molecular sequence data. For artifactual and biological reasons, a gene tree may differ from a species tree, a phenomenon known as gene tree-species tree incongruence. Assuming the presence of one or more evolutionary events, e.g., gene duplication, gene loss, and lateral gene transfer (LGT), the incongruence may be explained using a reconciliation of a gene tree inside a species tree. Such information has biological utilities, e.g., inference of orthologous relationship between genes. In this thesis, we present probabilistic models and methods for orthology analysis and species tree inference, while accounting for evolutionary factors such as gene duplication, gene loss, and sequence evolution. Furthermore, we use a probabilistic LGT-aware model for inferring gene trees having temporal information for duplication and LGT events. In the first project, we present a Bayesian method, called DLRSOrthology, for estimating orthology probabilities using the DLRS model: a probabilistic model integrating gene evolution, a relaxed molecular clock for substitution rates, and sequence evolution. We devise a dynamic programming algorithm for efficiently summing orthology probabilities over all reconciliations of a gene tree inside a species tree. Furthermore, we present heuristics based on receiver operating characteristics (ROC) curve to estimate suitable thresholds for deciding orthology events. Our method, as demonstrated by synthetic and biological results, outperforms existing probabilistic approaches in accuracy and is robust to incomplete taxon sampling artifacts. In the second project, we present a probabilistic method, based on a mixture model, for species tree inference. The method employs a two-phase approach, where in the first phase, a structural expectation maximization algorithm, based on a mixture model, is used to reconstruct a maximum likelihood set of candidate species trees. In the second phase, in order to select the best species tree, each of the candidate species tree is evaluated using PrIME-DLRS: a method based on the DLRS model. The method is accurate, efficient, and scalable when compared to a recent probabilistic species tree inference method called PHYLDOG. We observe that, in most cases, the analysis constituted only by the first phase may also be used for selecting the target species tree, yielding a fast and accurate method for larger datasets. Finally, we devise a probabilistic method based on the DLTRS model: an extension of the DLRS model to include LGT events, for sampling reconciliations of a gene tree inside a species tree. The method enables us to estimate gene trees having temporal information for duplication and LGT events. To the best of our knowledge, this is the first probabilistic method that takes gene sequence data directly into account for sampling reconciliations that contains information about LGT events. Based on the synthetic data analysis, we believe that the method has the potential to identify LGT highways. / <p>QC 20150529</p>

動態規劃是一種專門用來解決最適化的數學方法，其觀念源自於Bellman (1962)，他提出了動態規劃的最佳原則，然而動態規劃問題不見得有封閉解(closed form solution)，即使其存在，求解過程往往也相當困難且複雜。Vigna & Haberman (2001)用動態規劃方式找出最佳的投資策略並分析確定提撥制(defined contribution)下的財務風險；本研究擬以Vigna & Haberman (2001)的模型為基礎，提出解決動態規劃問題的數值方法。 Vigna & Haberman (2001)推導出確定提撥退休金制度下離散時間的最適投資策略封閉解，透過該模型，我們可以比較本研究所建議的方法與真正封閉解的差異，證實本研究所建議的方法的確可以提供動態規劃問題一個接近且有效率的數值解法。接著根據Yvonne C.(2002、2003)的抽樣方法，希望在進行模擬時，能找出模擬情境的特性並對這些情境進行抽樣，藉此減少情境數以增加電腦運算的效率。最後應用在Vigna & Haberman (2001)的修正模型以及Haberman & Vigna (2002)的模型上，說明了本研究所建議的數值方法也適用在各類型的動態規劃上，包含理論封閉解不存在以及求解非常複雜的問題。

Mineral processing plan ts, such as LONMIN's Eastern Platinum B-stream, typically have few on-line measurements, and key measures of performance such as grade only become available after samples have been analysed in the laboratory. More immediate feedback from a dynamic observer model promises enhanced understanding of the process, and facilitates prompt corrective actions, whether in open or closed loop . Such plant s easily enter sub-optimal modes such as large , uselessly re-circulating loads as the feed conditions change. Interpretation of such modes from key combinations of the variables deduced by an observer model , using a type of expert system, would add another level of intelligence to benefit operation. The aim of this thesis was to develop and implement a dynamic observer model of the LONMIN Eastern Platinum B-Stream into one of the existing control platforms available at the plant , known as PlantStar®, developed by MINTEK. The solution of the system of differential and algebraic equations resulting from this type of flowsheet modelling is based on an extended Kalman filter, which is able to dynamically reconcile any measurements which are presented to it, in real time. These measurement selections may also vary in real time, which provides flexibility of the model solution and the model 's uses. PlantStar passes the measurements that are available at the plant, to the dynamic observer model through a "plugin" module, which has been developed to incorporate the observer model and utilise the PlantStar control platform. In an on-line situation, the model will track the plant's behaviour and continuously update its position in real-time to ensure it follows the plant closely. This model would then be able to run simulations of the plant in parallel and could be used as a training facility for new operators, while in a real-time situation it could provide estimates of unmeasurable variables throughout the plant. An example of some of these variables are the flotation rate constants of minerals throughout the plant, which can be estimated in real time by the extended Kalman filter. The model could also be used to predict future plant conditions based on the current plant state , allowing for case scenarios to be performed without affecting the actual plant's performance. Once the dynamic observer model and "plugin" module were completed, case scenario simulations were performed using a measured data set from the plant as a starting point because real-time data were unavailable as the model was developed off-site . / Thesis (M.Sc.Eng.)-University of Natal, Durban, 2004.

Le travail présenté ici s'intéresse à la résolution numérique de problèmes de commande optimale stochastique de grande taille. Nous considérons un système dynamique, sur un horizon de temps discret et fini, pouvant être influencé par des bruits exogènes et par des actions prises par le décideur. L'objectif est de contrôler ce système de sorte à minimiser une certaine fonction objectif, qui dépend de l'évolution du système sur tout l'horizon. Nous supposons qu'à chaque instant des observations sont faites sur le système, et éventuellement gardées en mémoire. Il est généralement profitable, pour le décideur, de prendre en compte ces observations dans le choix des actions futures. Ainsi sommes-nous à la recherche de stratégies, ou encore de lois de commandes, plutôt que de simples décisions. Il s'agit de fonctions qui à tout instant et à toute observation possible du système associent une décision à prendre. Ce manuscrit présente trois contributions. La première concerne la convergence de méthodes numériques basées sur des scénarios. Nous comparons l'utilisation de méthodes basées sur les arbres de scénarios aux méthodes particulaires. Les premières ont été largement étudiées au sein de la communauté "Programmation Stochastique". Des développements récents, tant théoriques que numériques, montrent que cette méthodologie est mal adaptée aux problèmes à plusieurs pas de temps. Nous expliquons ici en détails d'où provient ce défaut et montrons qu'il ne peut être attribué à l'usage de scénarios en tant que tel, mais plutôt à la structure d'arbre. En effet, nous montrons sur des exemples numériques comment les méthodes particulaires, plus récemment développées et utilisant également des scénarios, ont un meilleur comportement même avec un grand nombre de pas de temps. La deuxième contribution part du constat que, même à l'aide des méthodes particulaires, nous faisons toujours face à ce qui est couramment appelé, en commande optimale, la malédiction de la dimension. Lorsque la taille de l'état servant à résumer le système est de trop grande taille, on ne sait pas trouver directement, de manière satisfaisante, des stratégies optimales. Pour une classe de systèmes, dits décomposables, nous adaptons des résultats bien connus dans le cadre déterministe, portant sur la décomposition de grands systèmes, au cas stochastique. L'application n'est pas directe et nécessite notamment l'usage d'outils statistiques sophistiqués afin de pouvoir utiliser la variable duale qui, dans le cas qui nous intéresse, est un processus stochastique. Nous proposons un algorithme original appelé Dual Approximate Dynamic Programming (DADP) et étudions sa convergence. Nous appliquons de plus cet algorithme à un problème réaliste de gestion de production électrique sur un horizon pluri-annuel. La troisième contribution de la thèse s'intéresse à une propriété structurelle des problèmes de commande optimale stochastique : la question de la consistance dynamique d'une suite de problèmes de décision au cours du temps. Notre but est d'établir un lien entre la notion de consistance dynamique, que nous définissons de manière informelle dans le dernier chapitre, et le concept de variable d'état, qui est central dans le contexte de la commande optimale. Le travail présenté est original au sens suivant. Nous montrons que, pour une large classe de modèles d'optimisation stochastique n'étant pas a priori consistants dynamiquement, on peut retrouver la consistance dynamique quitte à étendre la structure d'état du système / This work is intended at providing resolution methods for Stochastic Optimal Control (SOC) problems. We consider a dynamical system on a discrete and finite horizon, which is influenced by exogenous noises and actions of a decision maker. The aim is to minimize a given function of the behaviour of the system over the whole time horizon. We suppose that, at every instant, the decision maker is able to make observations on the system and even to keep some in memory. Since it is generally profitable to take these observations into account in order to draw further actions, we aim at designing decision rules rather than simple decisions. Such rules map to every instant and every possible observation of the system a decision to make. The present manuscript presents three main contributions. The first is concerned with the study of scenario-based solving methods for SOC problems. We compare the use of the so-called scenario trees technique to the particle method. The first one has been widely studied among the Stochastic Programming community and has been somehow popular in applications, until recent developments showed numerically as well as theoretically that this methodology behaved poorly when the number of time steps of the problem grows. We here explain this fact in details and show that this negative feature is not to be attributed to the scenario setting, but rather to the use of a tree structure. Indeed, we show on numerical examples how the particle method, which is a newly developed variational technique also based on scenarios, behaves in a better way even when dealing with a large number of time steps. The second contribution starts from the observation that, even with particle methods, we are still facing some kind of curse of dimensionality. In other words, decision rules intrisically suffer from the dimension of their domain, that is observations (or state in the Dynamic Programming framework). For a certain class of systems, namely decomposable systems, we adapt results concerning the decomposition of large-scale systems which are well known in the deterministic case to the SOC case. The application is not straightforward and requires some statistical analysis for the dual variable, which is in our context a stochastic process. We propose an original algorithm called Dual Approximate Dynamic Programming (DADP) and study its convergence. We also apply DADP to a real-life power management problem. The third contribution is concerned with a rather structural property for SOC problems: the question of dynamic consistency for a sequence of decision making problems over time. Our aim is to establish a link between the notion of time consistency, that we loosely define in the last chapter, and the central concept of state structure within optimal control. This contribution is original in the following sense. Many works in the literature aim at finding optimization models which somehow preserve the "natural" time consistency property for the sequence of decision making problems. On the contrary, we show for a broad class of SOC problems which are not a priori time-consistent that it is possible to regain this property by simply extending the state structure of the model

This thesis develops efficient optimization methods for Model Predictive Control (MPC) to enable its application to constrained systems with fast and uncertain dynamics. The key contribution is an active set method which exploits the parametric nature of the sequential optimization problem and is obtained from a dynamic programming formulation of the MPC problem. This method is first applied to the nominal linear MPC problem and is successively extended to linear systems with additive uncertainty and input constraints or state/input constraints. The thesis discusses both offline (projection-based) and online (active set) methods for the solution of controllability problems for linear systems with additive uncertainty. The active set method uses first-order necessary conditions for optimality to construct parametric programming regions for a particular given active set locally along a line of search in the space of feasible initial conditions. Along this line of search the homotopy of optimal solutions is exploited: a known solution at some given plant state is continuously deformed into the solution at the actual measured current plant state by performing the required active set changes whenever a boundary of a parametric programming region is crossed during the line search operation. The sequence of solutions for the finite horizon optimal control problem is therefore obtained locally for the given plant state. This method overcomes the main limitation of parametric programming methods that have been applied in the MPC context which usually require the offline precomputation of all possible regions. In contrast to this the proposed approach is an online method with very low computational demands which efficiently exploits the parametric nature of the solution and returns exact local DP solutions. The final chapter of this thesis discusses an application of robust tube-based MPC to the nonlinear MPC problem based on successive linearization.

We analyze the policy implications of aversion to Knightian uncertainty (ambiguity) about the possibility of tipping points. We demonstrate two channels through which uncertainty aversion affects optimal policy in the general setting. The first channel relates to the policy's effect on the probability of tipping, and the second channel to its differential impact in the pre- and post-tipping regimes. We then extend a recursive dynamic model of climate policy and tipping points to include uncertainty aversion. Numerically, aversion to Knightian uncertainty in the face of an ambiguous tipping point increases the optimal tax on carbon dioxide emissions, but only by a small amount.

La panne de moteur est une situation critique pour la sécurité du vol. L’objectif de cette thèse est d’améliorer la gestion de la trajectoire avion d’urgence dans le cas d’une panne totale de moteur en un certain point de vol alors que l’avion a déjà pris une certaine vitesse et une certaine altitude après le décollage. Dans cette étude, on considère que la trajectoire de vol plané le long d’un plan vertical peut conduire directement à un lieu atterrissage sûr. Les performances d’un avion de transport sont d’abord analysées, et les lieus atteignables sont établis à partir d’une situation donnée initiale. Une fois une zone de sécurité accessible existe le problème qui est abordée ici est de développer un système de guidage qui permet à l’avion d’effectuer une trajectoire faisable vers la zone d’atterrissage. La programmation dynamique inverse est utilisée pour construire en arrière des ensembles de trajectoires faisables vers conditions finales compatibles avec panne de moteur. Afin d’obtenir un dispositif en ligne pour générer des directives efficaces pour le pilote automatique ou le pilote humain (par un directeur de vol), un réseau de neurones est construit à partir de la base de données générée. Ensuite, les résultats de simulation sont analysés pour validation, et d’autres améliorations de l’approche proposée sont prises en considération. / Engine-out is an undoubted critical situation for flight safety. The objective of this thesis is to improve the management of emergency manoeuvres for transportation aircraft once all engines go out at a given point during the flight. Here we consider the evolution of the gliding aircraft along a vertical plane possibly leading directly to a safe landing place. The gliding qualities of standard transportation aircraft are first analyzed and reachable areas from given initial situations are established. Once a safe reachable area exists the problem which is tackled here is to develop design principles for a guidance system which makes the aircraft perform a feasible glide trajectory towards such landing area. Reverse dynamic programming is used to build backwards sets of feasible trajectories leading to final conditions compatible with engine-out landing. To get an on-line device to produce efficient directives for the autopilot or the human pilot (through a flight director), a neural network is built from the generated database. Then simulation results are analyzed for validation and further improvements of the proposed approach are considered

Title: Stochastic Dynamic Programming Problems: Theory and Applications Author: Gabriel Lendel Department: Department of Probability and Mathematical Statistics Supervisor: Ing. Karel Sladký CSc. Supervisor's e-mail address: sladky@utia.cas.cz Abstract: In the present work we study Markov decision processes which provide a mathematical framework for modeling decision-making in situations where outcomes are partly random and partly under the control of a decision maker. We study iterative procedures for finding policy that is optimal or nearly optimal with respect to the selec- ted criteria. Specifically, we mainly examine the task of finding a policy that is optimal with respect to the total expected discounted reward or the average expected reward for discrete or continuous systems. In the work we study policy iteration algorithms and aproximative value iteration algorithms. We give numerical analysis of specific problems. Keywords: Stochastic dynamic programming, Markov decision process, policy ite- ration, value iteration

Underwater video is used by marine biologists to observe, identify, and quantify living marine resources. Video sequences are typically analyzed manually, which is a time consuming and laborious process. Automating this process will significantly save time and cost. This work proposes a technique for automatic fish classification in underwater video. The steps involved are background subtracting, fish region tracking and classification using features. The background processing is used to separate moving objects from their surrounding environment. Tracking associates multiple views of the same fish in consecutive frames. This step is especially important since recognizing and classifying one or a few of the views as a species of interest may allow labeling the sequence as that particular species. Shape features are extracted using Fourier descriptors from each object and are presented to nearest neighbor classifier for classification. Finally, the nearest neighbor classifier results are combined using a probabilistic-like framework to classify an entire sequence. The majority of the existing pattern matching techniques focus on affine invariance, mainly because rotation, scale, translation and shear are common image transformations. However, in some situations, other transformations may be modeled as a small deformation on top of an affine transformation. The proposed algorithm complements the existing Fourier transform-based pattern matching methods in such a situation. First, the spatial domain pattern is decomposed into non-overlapping concentric circular rings with centers at the middle of the pattern. The Fourier transforms of the rings are computed, and are then mapped to polar domain. The algorithm assumes that the individual rings are rotated with respect to each other. The variable angles of rotation provide information about the directional features of the pattern. This angle of rotation is determined starting from the Fourier transform of the outermost ring and moving inwards to the innermost ring. Two different approaches, one using dynamic programming algorithm and second using a greedy algorithm, are used to determine the directional features of the pattern.