A stochastic dynamic programming approach for pricing options on stock-index futures

The aim of this thesis is to price options on equity index futures with an application to standard options on S&P 500 futures traded on the Chicago Mercantile Exchange. Our methodology is based on stochastic dynamic programming, which can accommodate European as well as American options. The model accommodates dividends from the underlying asset. It also captures the optimal exercise strategy and the fair value of the option. This approach is an alternative to available numerical pricing methods such as binomial trees, finite differences, and ad-hoc numerical approximation techniques. Our numerical and empirical investigations demonstrate convergence, robustness, and efficiency. We use this methodology to value exchange-listed options. The European option premiums thus obtained are compared to Black's closed-form formula. They are accurate to four digits. The American option premiums also have a similar level of accuracy compared to premiums obtained using finite differences and binomial trees with a large number of time steps. The proposed model accounts for deterministic, seasonally varying dividend yield. In pricing futures options, we discover that what matters is the sum of the dividend yields over the life of the futures contract and not their distribution.

Quality-optimization algorithm based on stochastic dynamic programming for MPEG DASH video streaming

In contrast to traditional push-based protocols, adaptive streaming techniques like Dynamic Adaptive Streaming over HTTP (DASH) fix attention on the client, who dynamically requests different-quality portions of the content to cope with a limited and variable bandwidth but aiming at maximizing the quality perceived by the user. Since DASH adaptation logic at the client is not covered by the standard, we propose a solution based on Stochastic Dynamic Programming (SDP) techniques to find the optimal request policies that guarantee the users' Quality of Experience (QoE). Our algorithm is evaluated in a simulated streaming session and is compared with other adaptation approaches. The results show that our proposal outperforms them in terms of QoE, requesting higher qualities on average.

Stochastic dynamic programming for election timing: A game theory approach

In this paper, we consider dynamic programming for the election timing in the majoritarian parliamentary system such as in Australia, where the government has a constitutional right to call an early election. This right can give the government an advantage to remain in power for as long as possible by calling an election, when its popularity is high. On the other hand, the opposition's natural objective is to gain power, and it will apply controls termed as "boosts" to reduce the chance of the government being re-elected by introducing policy and economic responses. In this paper, we explore equilibrium solutions to the government, and the opposition strategies in a political game using stochastic dynamic programming. Results are given in terms of the expected remaining life in power, call and boost probabilities at each time at any level of popularity.

On the Convergence of Stochastic Iterative Dynamic Programming Algorithms

Recent developments in the area of reinforcement learning have yielded a number of new algorithms for the prediction and control of Markovian environments. These algorithms, including the TD(lambda) algorithm of Sutton (1988) and the Q-learning algorithm of Watkins (1989), can be motivated heuristically as approximations to dynamic programming (DP). In this paper we provide a rigorous proof of convergence of these DP-based learning algorithms by relating them to the powerful techniques of stochastic approximation theory via a new convergence theorem. The theorem establishes a general class of convergent algorithms to which both TD(lambda) and Q-learning belong.

Dynamic programming for stochastic target problems, Viscosity solutions and hedging in markets with Portfolio constraints and large investors

The purpose of this expository arti le is to present a self- ontained overview of some results on the hara terization of the optimal value fun tion of a sto hasti target problem as (dis ontinuous) vis osity solution of a ertain dynami programming PDE and its appli ation to the problem of hedging ontingent laims in the presen e of portfolio onstraints and large investors

Information relaxations and duality in stochastic dynamic programs

We describe a general technique for determining upper bounds on maximal values (or lower bounds on minimal costs) in stochastic dynamic programs. In this approach, we relax the nonanticipativity constraints that require decisions to depend only on the information available at the time a decision is made and impose a "penalty" that punishes violations of nonanticipativity. In applications, the hope is that this relaxed version of the problem will be simpler to solve than the original dynamic program. The upper bounds provided by this dual approach complement lower bounds on values that may be found by simulating with heuristic policies. We describe the theory underlying this dual approach and establish weak duality, strong duality, and complementary slackness results that are analogous to the duality results of linear programming. We also study properties of good penalties. Finally, we demonstrate the use of this dual approach in an adaptive inventory control problem with an unknown and changing demand distribution and in valuing options with stochastic volatilities and interest rates. These are complex problems of significant practical interest that are quite difficult to solve to optimality. In these examples, our dual approach requires relatively little additional computation and leads to tight bounds on the optimal values. © 2010 INFORMS.

Hybrid wind-diesel power plant valuation and optimization using real option theory and dynamic programming

El sistema de energía eólica-diesel híbrido tiene un gran potencial en la prestación de suministro de energía a comunidades remotas. En comparación con los sistemas tradicionales de diesel, las plantas de energía híbridas ofrecen grandes ventajas tales como el suministro de capacidad de energía extra para "microgrids", reducción de los contaminantes y emisiones de gases de efecto invernadero, y la cobertura del riesgo de aumento inesperado del precio del combustible. El principal objetivo de la presente tesis es proporcionar nuevos conocimientos para la evaluación y optimización de los sistemas de energía híbrido eólico-diesel considerando las incertidumbres. Dado que la energía eólica es una variable estocástica, ésta no puede ser controlada ni predecirse con exactitud. La naturaleza incierta del viento como fuente de energía produce serios problemas tanto para la operación como para la evaluación del valor del sistema de energía eólica-diesel híbrido. Por un lado, la regulación de la potencia inyectada desde las turbinas de viento es una difícil tarea cuando opera el sistema híbrido. Por otro lado, el bene.cio económico de un sistema eólico-diesel híbrido se logra directamente a través de la energía entregada a la red de alimentación de la energía eólica. Consecuentemente, la incertidumbre de los recursos eólicos incrementa la dificultad de estimar los beneficios globales en la etapa de planificación. La principal preocupación del modelo tradicional determinista es no tener en cuenta la incertidumbre futura a la hora de tomar la decisión de operación. Con lo cual, no se prevé las acciones operativas flexibles en respuesta a los escenarios futuros. El análisis del rendimiento y simulación por ordenador en el Proyecto Eólico San Cristóbal demuestra que la incertidumbre sobre la energía eólica, las estrategias de control, almacenamiento de energía, y la curva de potencia de aerogeneradores tienen un impacto significativo sobre el rendimiento del sistema. En la presente tesis, se analiza la relación entre la teoría de valoración de opciones y el proceso de toma de decisiones. La opción real se desarrolla con un modelo y se presenta a través de ejemplos prácticos para evaluar el valor de los sistemas de energía eólica-diesel híbridos. Los resultados muestran que las opciones operacionales pueden aportar un valor adicional para el sistema de energía híbrida, cuando esta flexibilidad operativa se utiliza correctamente. Este marco se puede aplicar en la optimización de la operación a corto plazo teniendo en cuenta la naturaleza dependiente de la trayectoria de la política óptima de despacho, dadas las plausibles futuras realizaciones de la producción de energía eólica. En comparación con los métodos de valoración y optimización existentes, el resultado del caso de estudio numérico muestra que la política de operación resultante del modelo de optimización propuesto presenta una notable actuación en la reducción del con- sumo total de combustible del sistema eólico-diesel. Con el .n de tomar decisiones óptimas, los operadores de plantas de energía y los gestores de éstas no deben centrarse sólo en el resultado directo de cada acción operativa, tampoco deberían tomar decisiones deterministas. La forma correcta es gestionar dinámicamente el sistema de energía teniendo en cuenta el valor futuro condicionado en cada opción frente a la incertidumbre. ABSTRACT Hybrid wind-diesel power systems have a great potential in providing energy supply to remote communities. Compared with the traditional diesel systems, hybrid power plants are providing many advantages such as providing extra energy capacity to the micro-grid, reducing pollution and greenhouse-gas emissions, and hedging the risk of unexpected fuel price increases. This dissertation aims at providing novel insights for assessing and optimizing hybrid wind-diesel power systems considering the related uncertainties. Since wind power can neither be controlled nor accurately predicted, the energy harvested from a wind turbine may be considered a stochastic variable. This uncertain nature of wind energy source results in serious problems for both the operation and value assessment of the hybrid wind-diesel power system. On the one hand, regulating the uncertain power injected from wind turbines is a difficult task when operating the hybrid system. On the other hand, the economic profit of a hybrid wind-diesel system is achieved directly through the energy delivered to the power grid from the wind energy. Therefore, the uncertainty of wind resources has increased the difficulty in estimating the total benefits in the planning stage. The main concern of the traditional deterministic model is that it does not consider the future uncertainty when making the dispatch decision. Thus, it does not provide flexible operational actions in response to the uncertain future scenarios. Performance analysis and computer simulation on the San Cristobal Wind Project demonstrate that the wind power uncertainty, control strategies, energy storage, and the wind turbine power curve have a significant impact on the performance of the system. In this dissertation, the relationship between option pricing theory and decision making process is discussed. A real option model is developed and presented through practical examples for assessing the value of hybrid wind-diesel power systems. Results show that operational options can provide additional value to the hybrid power system when this operational flexibility is correctly utilized. This framework can be applied in optimizing short term dispatch decisions considering the path-dependent nature of the optimal dispatch policy, given the plausible future realizations of the wind power production. Comparing with the existing valuation and optimization methods, result from numerical example shows that the dispatch policy resulting from the proposed optimization model exhibits a remarkable performance in minimizing the total fuel consumption of the wind-diesel system. In order to make optimal decisions, power plant operators and managers should not just focus on the direct outcome of each operational action; neither should they make deterministic decisions. The correct way is to dynamically manage the power system by taking into consideration the conditional future value in each option in response to the uncertainty.

Coordinated road-junction traffic control by dynamic programming

This paper presents a novel approach to road-traffic control for interconnected junctions. With a local fuzzy-logic controller (FLC) installed at each junction, a dynamic-programming (DP) technique is proposed to derive the green time for each phase in a traffic-light cycle. Coordination parameters from the adjacent junctions are also taken into consideration so that organized control is extended beyond a single junction. Instead of pursuing the absolute optimization of traffic delay, this study examines a practical approach to enable the simple implementation of coordination among junctions, while attempting to reduce delays, if possible. The simulation results show that the delay per vehicle can be substantially reduced, particularly when the traffic demand reaches the junction capacity. The implementation of this controller does not require complicated or demanding hardware, and such simplicity makes it a useful tool for offline studies or realtime control purposes.

Efficient articulated trajectory reconstruction using dynamic programming and filters

This paper considers the problem of reconstructing the motion of a 3D articulated tree from 2D point correspondences subject to some temporal prior. Hitherto, smooth motion has been encouraged using a trajectory basis, yielding a hard combinatorial problem with time complexity growing exponentially in the number of frames. Branch and bound strategies have previously attempted to curb this complexity whilst maintaining global optimality. However, they provide no guarantee of being more efficient than exhaustive search. Inspired by recent work which reconstructs general trajectories using compact high-pass filters, we develop a dynamic programming approach which scales linearly in the number of frames, leveraging the intrinsically local nature of filter interactions. Extension to affine projection enables reconstruction without estimating cameras.

Load profile based determination of distribution feeder configuration by dynamic programming

This paper presents a new method to determine feeder reconfiguration scheme considering variable load profile. The objective function consists of system losses, reliability costs and also switching costs. In order to achieve an optimal solution the proposed method compares these costs dynamically and determines when and how it is reasonable to have a switching operation. The proposed method divides a year into several equal time periods, then using particle swarm optimization (PSO), optimal candidate configurations for each period are obtained. System losses and customer interruption cost of each configuration during each period is also calculated. Then, considering switching cost from a configuration to another one, dynamic programming algorithm (DPA) is used to determine the annual reconfiguration scheme. Several test systems were used to validate the proposed method. The obtained results denote that to have an optimum solution it is necessary to compare operation costs dynamically.

Approximate solutions to stochastic dynamic programs

This paper examines the properties of various approximation methods for solving stochastic dynamic programs in structural estimation problems. The problem addressed is evaluating the expected value of the maximum of available choices. The paper shows that approximating this by the maximum of expected values frequently has poor properties. It also shows that choosing a convenient distributional assumptions for the errors and then solving exactly conditional on the distributional assumption leads to small approximation errors even if the distribution is misspecified. © 1997 Cambridge University Press.

A dynamic programming model for optimising feeding and slaughter decisions regarding fattening pigs

Costs of purchasing new piglets and of feeding them until slaughter are the main variable expenditures in pig fattening. They both depend on slaughter intensity, the nature of feeding patterns and the technological constraints of pig fattening, such as genotype. Therefore, it is of interest to examine the effect of production technology and changes in input and output prices on feeding and slaughter decisions. This study examines the problem by using a dynamic programming model that links genetic characteristics of a pig to feeding decisions and the timing of slaughter and takes into account how these jointly affect the quality-adjusted value of a carcass. The model simulates the growth mechanism of a pig under optional feeding and slaughter patterns and then solves the optimal feeding and slaughter decisions recursively. The state of nature and the genotype of a pig are known in the analysis. The main contribution of this study is the dynamic approach that explicitly takes into account carcass quality while simultaneously optimising feeding and slaughter decisions. The method maximises the internal rate of return to the capacity unit. Hence, the results can have vital impact on competitiveness of pig production, which is known to be quite capital-intensive. The results suggest that producer can significantly benefit from improvements in the pig's genotype, because they improve efficiency of pig production. The annual benefits from obtaining pigs of improved genotype can be more than €20 per capacity unit. The annual net benefits of animal breeding to pig farms can also be considerable. Animals of improved genotype can reach optimal slaughter maturity quicker and produce leaner meat than animals of poor genotype. In order to fully utilise the benefits of animal breeding, the producer must adjust feeding and slaughter patterns on the basis of genotype. The results suggest that the producer can benefit from flexible feeding technology. The flexible feeding technology segregates pigs into groups according to their weight, carcass leanness, genotype and sex and thereafter optimises feeding and slaughter decisions separately for these groups. Typically, such a technology provides incentives to feed piglets with protein-rich feed such that the genetic potential to produce leaner meat is fully utilised. When the pig approaches slaughter maturity, the share of protein-rich feed in the diet gradually decreases and the amount of energy-rich feed increases. Generally, the optimal slaughter weight is within the weight range that pays the highest price per kilogram of pig meat. The optimal feeding pattern and the optimal timing of slaughter depend on price ratios. Particularly, an increase in the price of pig meat provides incentives to increase the growth rates up to the pig's biological maximum by increasing the amount of energy in the feed. Price changes and changes in slaughter premium can also have large income effects. Key words: barley, carcass composition, dynamic programming, feeding, genotypes, lean, pig fattening, precision agriculture, productivity, slaughter weight, soybeans

Optimal Reservoir Operation for Flood Control Using Folded Dynamic Programming

Folded Dynamic Programming (FDP) is adopted for developing optimalnreservoir operation policies for flood control. It is applied to a case study of Hirakud Reservoir in Mahanadi basin, India with the objective of deriving optimal policy for flood control. The river flows down to Naraj, the head of delta where a major city is located and finally joins the Bay of Bengal. As Hirakud reservoir is on the upstream side of delta area in the basin, it plays an important role in alleviating the severity of the flood for this area. Data of 68 floods such as peaks of inflow hydrograph, peak of outflow from reservoir during each flood, peak of flow hydrograph at Naraj and d/s catchment contribution are utilized. The combinations of 51, 54, 57 thousand cumecs as peak inflow into reservoir and 25.5, 20, 14 thousand cumecs respectively as,peak d/s catchment contribution form the critical combinations for flood situation. It is observed that the combination of 57 thousand cumecs of inflow into reservoir and 14 thousand cumecs for d/s catchment contribution is the most critical among the critical combinations of flow series. The method proposed can be extended to similar situations for deriving reservoir operating policies for flood control.