Dynamic programming in stochastic control of systems with delay

We consider optimal control problems for systems described by stochastic differential equations with delay (SDDE). We prove a version of Bellman's principle of optimality (the dynamic programming principle) for a general class of such problems. That the class in general means that both the dynamics and the cost depends on the past in a general way. As an application, we study systems where the value function depends on the past only through some weighted average. For such systems we obtain a Hamilton-Jacobi-Bellman partial differential equation that the value function must solve if it is smooth enough. The weak uniqueness of the SDDEs we consider is our main tool in proving the result. Notions of strong and weak uniqueness for SDDEs are introduced, and we prove that strong uniqueness implies weak uniqueness, just as for ordinary stochastic differential equations.     

Finite-stage stochastic decision processes with recursive reward structure I: optimality equations and deterministic strategies

In this paper we examine an N-stage stochastic decision model with a recursive reward structure whose state and action spaces are standard Borel ones. The central results relate to the validity of the optimality equations and to the sufficiency of deterministic strategies. The results expand statements known for classical dynamic programming problems with additive total rewards to a wide class of recursive reward functions under certain monotonicity and continuity assumptions. The existence of an expected utility representation of the total rewards is generally not presupposed     

混合动力公交车能量控制策略的优化模型

针对混合动力公交车在循环工况内功率需求的特点,建立了未来功率需求贝叶斯预测模型;利用2-阶段随机动态规划模型将大规模的随机动态规划问题简化为多个小规模的随机动态规划问题和一个确定型动态规划问题;对于随机动态规划模型的求解,给出了稀疏表示的降维方法,将复杂的泛函极值问题转化为常规的随机动态优化问题,并采用分布估计算法和计算资源最优配置算法的计算机仿真优化算法对随机动态优化问题进行求解;给出了基于查表的在线控制策略,为模型的实际应用进行了有益的探索。     

On the relative efficiency of nth order and DARA stochastic dominance rules

It is known that third order stochastic dominance implies DARA dominance while no implications exist between higher orders and DARA dominance. A recent contribution points out that, with regard to the problem of determining lower and upper bounds for the price of a financial option, the DARA rule turns out to improve the stochastic dominance criteria of any order. In this paper the relative efficiency of the ordinary stochastic dominance and DARA criteria for alternatives with discrete distributions are compared, in order to see if the better performance of DARA criterion is also suitable for other practical applications. Moreover, the operational use of the stochastic dominance techniques for financial choices is deepened.     

Sustainable production technologies which take into account environmental constraints

We formulate and study a multiobjective programming approach for production processes which implements suitable constraints on pollutant emissions. We consider two alternative optimization problems: (a) minimum pollution risk; (b) maximum expected return. For each pollutant, we define three different contamination levels: (a) the desirable or the target pollution level, (b) the alarm (warning or critical) level and (c) the maximum admissible (acceptable) level, and introduce penalties proportional to the amounts of pollutants that exceed these levels. The objective function of the minimum pollution risk problem is not smooth since it contains positive parts of some affine functions, resulting in mathematical difficulties, which can be solved by formulating an alternative linear programming model, which makes use of additional variables and has the same solutions as the initial problem. We investigate various particular cases and analyze a numerical example for a textile plant.     

一类组合最优化问题及其算法

本文介绍三个新的组合最优化模型，并分别给出复杂性为Ｏ（Ｎ２）和Ｏ（Ｎ２α）的多项式算法和拟多项式算法．     

The C 3 Theorem and a D 2 Algorithm for Large Scale Stochastic Mixed-Integer Programming: Set Convexification

This paper considers the two-stage stochastic integer programming problem, with an emphasis on instances in which integer variables appear in the second stage. Drawing heavily on the theory of disjunctive programming, we characterize convexifications of the second stage problem and develop a decomposition-based algorithm for the solution of such problems. In particular, we verify that problems with fixed recourse are characterized by scenario-dependent second stage convexifications that have a great deal in common. We refer to this characterization as the C³ (Common Cut Coefficients) Theorem. Based on the C³ Theorem, we develop a decomposition algorithm which we refer to as Disjunctive Decomposition (D²). In this new class of algorithms, we work with master and subproblems that result from convexifications of two coupled disjunctive programs. We show that when the second stage consists of 0-1 MILP problems, we can obtain accurate second stage objective function estimates after finitely many steps. This result implies the convergence of the D² algorithm.This research was funded by NSF grants DMII 9978780 and CISE 9975050.     

Optimal operation of hydrothermal systems with Hydrological Scenario Generation through Bootstrap and Periodic Autoregressive Models

In electrical power systems with strong hydro generation, the use of adequate techniques to generate synthetic hydrological scenarios is extremely important for the evaluation of the ways the system behaves in order to meet the forecast energy demand. This paper proposes a new model to generate natural inflow energy scenarios in the long-term operation planning of large-sized hydrothermal systems. This model is based on the Periodic Autoregressive Model, PAR (p), where the identification of the p orders is based on the significance of the Partial Autocorrelation Function (PACF) estimated via Bootstrap, an intensive computational technique. The scenarios generated through this new technique were applied to the operation planning of the Brazilian Electrical System (BES), using the previously developed methodology of Stochastic Dynamic Programming based on Convex Hull algorithm (SDP-CHull). The results show that identification via Bootstrap is considerably more parsimonious, leading to the identification of lower orders models in most cases which retains the statistical characteristics of the original series. Additionally it presents a closer total mean operation cost when compared to the cost obtained via historic series.     

Multistage stochastic convex programs: Duality and its implications

In this paper, we study alternative primal and dual formulations of multistage stochastic convex programs (SP). The alternative dual problems which can be traced to the alternative primal representations, lead to stochastic analogs of standard deterministic constructs such as conjugate functions and Lagrangians. One of the by-products of this approach is that the development does not depend on dynamic programming (DP) type recursive arguments, and is therefore applicable to problems in which the objective function is non-separable (in the DP sense). Moreover, the treatment allows us to handle both continuous and discrete random variables with equal ease. We also investigate properties of the expected value of perfect information (EVPI) within the context of SP, and the connection between EVPI and nonanticipativity of optimal multipliers. Our study reveals that there exist optimal multipliers that are nonanticipative if, and only if, the EVPI is zero. Finally, we provide interpretations of the retroactive nature of the dual multipliers. This work was supported by NSF grant DMII-9414680.     

最优投资及最优消费策略

本文假设证券市场为有效竞争均衡市场，在文［１］的基础上，探讨最优投资及最优消费策略，得到最优投资与最优消费决策条件。     

生产运输成本问题的随机优化模型及新的求解途径

研究了供应商的生产能力,销售地的需求量和单位运输成本等因素均为随机变量条件下的单产品和多产品的生产运输成本问题,建立了该类问题的随机优化模型,证明了一般运输模型有解的充要条件,探讨了在一定的置信水平和其它相关约束条件下,确定每个供应商给每个销售地的送货量,以保证总运输成本最低的新的求解方法.通过数值方式,分析了不同的置信水平对成本的影响,给出了选择最佳置信水平的方法.     

Analysis of stochastic dual dynamic programming method

In this paper we discuss statistical properties and convergence of the Stochastic Dual Dynamic Programming (SDDP) method applied to multistage linear stochastic programming problems. We assume that the underline data process is stagewise independent and consider the framework where at first a random sample from the original (true) distribution is generated and consequently the SDDP algorithm is applied to the constructed Sample Average Approximation (SAA) problem. Then we proceed to analysis of the SDDP solutions of the SAA problem and their relations to solutions of the “true” problem. Finally we discuss an extension of the SDDP method to a risk averse formulation of multistage stochastic programs. We argue that the computational complexity of the corresponding SDDP algorithm is almost the same as in the risk neutral case.     

Optimality in transient markov chains and linear programming

It is shown how a discrete Markov programming problem can be transformed, using a linear program, into an equivalent problem from which the optimal decision rule can be trivially deduced. This transformation is applied to problems which have either transient probabilities or discounted costs.This research was supported by the National Research Council of Canada, Grant A7751.     

Long-term hydrothermal coordination with natural inflows modelled through a PDF and simulation results

Summary The long-term hydrothermal coordination of electricity generation has to optimize many variables tied to stochastic parameters. Multicommodity network flows in a replicated reservoir hydronetwork with multicommodity water inflows is one of the possible ways to model and optimize the long-term coordination. In the existing literature on this methodology there are several hypotheses and simplifications that need validation and analysis, and this is the prime purpose of this work. Simulation tests show that the method is sound, and indicate ways to improve the algorithm. The advantages and limitations of taking more or less water commodities are also analyzed.     

Transient policies in discrete dynamic programming: Linear programming including suboptimality tests and additional constraints

This paper investigates the computation of transient-optimal policies in discrete dynamic programming. The model, is quite general: it may contain transient as well as nontransient policies. and the transition matrices are not necessarily substochastic. A functional equation for the so-called transient-value-vector is derived and the concept of superharmonicity is introduced. This concept provides the linear program to compute the transientvalue-vector and a transient-optimal policy. We also discuss the elimination of suboptimal actions, the solution of problems with additional constraints, and the computation of an efficient policy for a multiple objective dynamic programming problem.     

Portfolio optimization in a Lévy market with intertemporal substitution and transaction costs

We investigate an infinite horizon investment-consumption model in which a single agent consumes and distributes her wealth between a risk-free asset (bank account) and several risky assets (stocks) whose prices are governed by Lévy (jump-diffusion) processes. We suppose that transactions between the assets incur a transaction cost proportional to the size of the transaction. The problem is to maximize the total utility of consumption under Hindy-Huang-Kreps intertemporal preferences. This portfolio optimisation problem is formulated as a singular stochastic control problem and is solved using dynamic programming and the theory of viscosity solutions. The associated dynamic programming equation is a second order degenerate elliptic integro-differential variational inequality subject to a state constraint boundary condition. The main result is a characterization of the value function as the unique constrained viscosity solution of the dynamic programming equation. Emphasis is put on providing a framework that allows for a general class of Lévy processes. Owing to the complexity of our investment-consumption model, it is not possible to derive closed form solutions for the value function. Hence, the optimal policies cannot be obtained in closed form from the first order conditions for the dynamic programming equation. Therefore, we have to resort to numerical methods for computing the value function as well as the associated optimal policies. In view of the viscosity solution theory, the analysis found in this paper will ensure the convergence of a large class of numerical methods for the investment-consumption model in question.     

A review of Goal Programming and its applications

This paper presents a review of the current literature on the branch of multi-criteria decision modelling known as Goal Programming (GP). The result of our indepth investigations of the two main GP methods, lexicographic and weighted GP together with their distinct application areas is reported. Some guidelines to the scope of GP as an application tool are given and methods of determining which problem areas are best suited to the different GP approaches are proposed. The correlation between the method of assigning weights and priorities and the standard of the results is also ascertained.     

Probabilistic Solutions to Optimal Control Problems

Let ( x 1 ( t ), x 2 ( t )) be a controlled two-dimensional diffusion process. The problem of minimizing, or maximizing, the time spent by ( x 1 ( t ), x 2 ( t )) in a given subset of 2 is solved, in two particular instances, by transforming the optimal control problems into purely probabilistic problems. In Section 2 , ( x 1 ( t ), x 2 ( t )) is a two-dimensional Wiener process and the optimal control is obtained by transforming a nonlinear dynamic programming equation into the Kolmogorov backward equation for a two-dimensional geometric Brownian motion. In Section 3 , the converse problem is solved. The problem of finding the maximal instantaneous reward that we can give for survival in the continuation region is also treated.     

Optimal selection from distributions with unknown parameters: Robustness of Bayesian models

We consider the problem of making one choice from a known number of i.i.d. alternatives. It is assumed that the distribution of the alternatives has some unknown parameter. We follow a Bayesian approach to maximize the discounted expected value of the chosen alternative minus the costs for the observations. For the case of gamma and normal distribution we investigate the sensitivity of the solution with respect to the prior distributions. Our main objective is to derive monotonicity and continuity results for the dependence on parameters of the prior distributions. Thus we prove some sort of Bayesian robustness of the model.