A model for decision problems with continuous time parameter

The concept of statistical decision theory concerning sequential observations is generalized to decision problems, which are based upon a continuous stochastic process.

In this model decision functions are introduced, consisting of a stopping time and a terminal decision rule. A method of discretization shows the connections between the discrete sequential and the continuous model. Concerning Bayes problems we find, that under certain assumptions the decision problem can be viewed as an optimal stopping problem with continuous time parameter.     

Asymptotic Optimality of Certain Multihypothesis Sequential Tests: Non‐i.i.d. Case

It is known that certain combinations of one‐sided sequential probability ratio tests are asymptotically optimal (relative to the expected sample size) for problems involving a finite number of possible distributions when probabilities of errors tend to zero and observations are independent and identically distributed according to one of the underlying distributions. The objective of this paper is to show that two specific constructions of sequential tests asymptotically minimize not only the expected time of observation but also any positive moment of the stopping time distribution under fairly general conditions for a finite number of simple hypotheses. This result appears to be true for general statistical models which include correlated and non‐homogeneous processes observed either in discrete or continuous time. For statistical problems with nuisance parameters, we consider invariant sequential tests and show that the same result is valid for this case. Finally, we apply general results to the solution of several particular problems such as a multi‐sample slippage problem for correlated Gaussian processes and for statistical models with nuisance parameters. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the empirical Bayes approach to multiple decision problems with sequential components

The empirical Bayes approach to multiple decision problems with a sequential decision problem as the component is studied. An empirical Bayesm-truncated sequential decision procedure is exhibited for general multiple decision problems. With a sequential component, an empirical Bayes sequential decision procedure selects both a stopping rule function and a terminal decision rule function for use in the component. Asymptotic results are presented for the convergence of the Bayes risk of the empirical Bayes sequential decision procedure.     

A sequential test for the failure rate of an exponential distribution with censored data

This paper provides an optimal sequential decision procedure for deciding between two composite hypotheses about the unknown failure rate of an exponential distribution, using censored data. The procedure has two components, a stopping time and a decision function. The optimal stopping time minimizes the expected total loss due to a wrong decision plus cost of observing the process. The optimal decision function is easily characterized once a stopping time has been specified. The main result determines the continuation region for the optimal decision procedure     

Dynamic Programming Method for Constrained Discrete-Time Optimal Control

A dynamic programming method is presented for solving constrained, discrete-time, optimal control problems. The method is based on an efficient algorithm for solving the subproblems of sequential quadratic programming. By using an interior-point method to accommodate inequality constraints, a modification of an existing algorithm for equality constrained problems can be used iteratively to solve the subproblems. Two test problems and two application problems are presented. The application examples include a rest-to-rest maneuver of a flexible structure and a constrained brachistochrone problem.     

Empirical Bayes sequential estimation for exponential families: The untruncated component

We consider the empirical Bayes decision problem where the component problem is the sequential estimation of the mean of one-parameter exponential family of distributions with squared error loss for the estimation error and a cost c>0 for each observation. The present paper studies the untruncated sequential component case. In particular, an untruncated asymptotically pointwise optimal sequential procedure is employed as the component. With sequential components, an empirical Bayes decision procedure selects both a stopping time and a terminal decision rule for use in the component with parameter . The goodness of the empirical Bayes sequential procedure is measured by comparing the asymptotic behavior of its Bayes risk with that of the component procedure as the number of past data increases to infinity. Asymptotic risk equivalence of the proposed empirical Bayes sequential procedure to the component procedure is demonstrated.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada under grant GP7987.     

Multiple-Subarc Gradient-Restoration Algorithm, Part 1: Algorithm Structure

Rapid progresses in information and computer technology allow the development of more advanced optimal control algorithms dealing with real-world problems. In this paper, which is Part 1 of a two-part sequence, a multiple-subarc gradient-restoration algorithm (MSGRA) is developed. We note that the original version of the sequential gradient-restoration algorithm (SGRA) was developed by Miele et al. in single-subarc form (SSGRA) during the years 1968–86; it has been applied successfully to solve a large number of optimal control problems of atmospheric and space flight.MSGRA is an extension of SSGRA, the single-subarc gradient-restoration algorithm. The primary reason for MSGRA is to enhance the robustness of gradient-restoration algorithms and also to enlarge the field of applications. Indeed, MSGRA can be applied to optimal control problems involving multiple subsystems as well as discontinuities in the state and control variables at the interface between contiguous subsystems.Two features of MSGRA are increased automation and efficiency. The automation of MSGRA is enhanced via time normalization: the actual time domain is mapped into a normalized time domain such that the normalized time length of each subarc is 1. The efficiency of MSGRA is enhanced by using the method of particular solutions to solve the multipoint boundary-value problems associated with the gradient phase and the restoration phase of the algorithm.In a companion paper [Part 2 (Ref. 2)], MSGRA is applied to compute the optimal trajectory for a multistage launch vehicle design, specifically, a rocket-powered spacecraft ascending from the Earth surface to a low Earth orbit (LEO). Single-stage, double-stage, and triple-stage configurations are considered and compared.     

Partitioned Random Search for Global Optimization with Sampling Cost and Discounting Factor

The method of partitioned random search has been proposed in recent years to obtain an as good as possible solution for the global optimization problem (1). A practical algorithm has been developed and applied to real-life problems. However, the design of this algorithm was based mainly on intuition. The theoretical foundation of the method is an important issue in the development of efficient algorithms for such problems. In this paper, we generalize previous theoretical results and propose a sequential sampling policy for the partitioned random search for global optimization with sampling cost and discounting factor. A proof of the optimality of the proposed sequential sampling policy is given by using the theory of optimal stopping.     

Continuous time Markovian decision processes average return criterion

Continuous time Markovian decision models with countable state space are investigated. The existence of an optimal stationary policy is established for the expected average return criterion function. It is shown that the expected average return can be expressed as an expected discounted return of a related Markovian decision process. A policy iteration method is given which converges to an optimal deterministic policy, the policy so obtained is shown optimal over all Markov policies.     

Sequential Fixed-Width Confidence Interval for the Product of Two Means

For the product of two population means, the problem of constructing a fixed-width confidence interval with preassigned coverage probability is considered. It is shown that the optimal sample sizes which minimize the total sample size and at the same time guarantee a fixed-width confidence interval of desired coverage depend on the unknown parameters. In order to overcome this, a fully sequential procedure consisting of a sampling scheme and a stopping rule are proposed. It is then shown that the sequential confidence interval is asymptotically consistent and the stopping rule is asymptotically efficient, as the width goes to zero. Furthermore, a second order result for the difference between the expected stopping time and the (total) optimal fixed sample size is established. The theoretical results are supported by appropriate simulations.     

Asymptotic analysis for multi-objective sequential stochastic assignment problems

ABSTRACT

We provide an asymptotic analysis of multi-objective sequential stochastic assignment problems (MOSSAP). In MOSSAP, a fixed number of tasks arrive sequentially, with an n-dimensional value vector revealed upon arrival. Each task is assigned to one of a group of known workers immediately upon arrival, with the reward given by an n-dimensional product-form vector. The objective is to maximize each component of the expected reward vector. We provide expressions for the asymptotic expected reward per task for each component of the reward vector and compare the convergence rates for three classes of Pareto optimal policies.     

秘书问题研究综述：何时停止搜索信息?

秘书问题是一类序贯观察与选择问题,描述了一种动态的信息搜索与决策过程,其问题实质是决定何时停止观察选项、而不是哪一个选项被选择.已有研究成果从解决该问题的策略方法角度,可以分为最优解策略与启发式策略,二者的差异主要体现在理论依据与研究方法上.最优解策略基于决策者完全理性假设,运用数学模型论证了解决该问题的最优决策行为。但许多实证研究发现,人们往往并没有遵循最优决策行为。相比较最优解策略而言,人们通常停止搜索信息太早或者说搜索量太少。这种基于决策者有限理性假设的描述性研究,在解释人们最优选择行为偏离的基础上,提出了解决秘书问题的一些启发式策略.最后,本文通过对已有研究成果的梳理与分析,提出了进一步研究的问题与方向。     

Parallel decomposition of multistage stochastic programming problems

A new decomposition method for multistage stochastic linear programming problems is proposed. A multistage stochastic problem is represented in a tree-like form and with each node of the decision tree a certain linear or quadratic subproblem is associated. The subproblems generate proposals for their successors and some backward information for their predecessors. The subproblems can be solved in parallel and exchange information in an asynchronous way through special buffers. After a finite time the method either finds an optimal solution to the problem or discovers its inconsistency. An analytical illustrative example shows that parallelization can speed up computation over every sequential method. Computational experiments indicate that for large problems we can obtain substantial gains in efficiency with moderate numbers of processors.This work was partly supported by the International Institute for Applied Systems Analysis, Laxenburg, Austria.     

加权马尔可夫链在传染病发病情况预测分析中的应用

首先基于传染病的发病情况存在大量不确定性的特点,应用有序聚类的方法建立发病人数状态的分级标准;然后针对发病人数序列为相依随机变量的特点,采取以规范化的各阶自相关系数为权重,用加权的马尔可夫链模型来预测和分析发病人数的变化状况,使预测结论的长期效果趋于最优;最后通过实例检验,对预测结果和方法进行评价和深入的分析.     

强化学习在运筹学的应用:研究进展与展望

强化学习已经成为人工智能领域一个新的研究热点,并已成功应用于各领域,强化学习将运筹优化领域的很多问题视为序贯决策问题,建模为马尔可夫决策过程并进行求解,在求解复杂、动态、随机运筹优化问题具有较大的优势。本文主要对强化学习在运筹优化领域的应用进行综述,首先介绍了强化学习的基本原理及其应用于运筹优化领域的研究框架,然后回顾并总结了强化学习在库存控制、路径优化、装箱配载和车间作业调度等方面的研究成果,并将最新的深度强化学习以及传统方法在运筹学领域的应用研究进行了对比分析,以突出深度强化学习的优越性。最后提出几个值得进一步探讨的研究方向,期望能为强化学习在运筹优化领域的研究提供参考。     

The sequential differentiation and its applications in the optimal control problems

Using the sequential approach, we define a certain generalization of the operator derivative. We establish the necessary extremum condition in terms of the sequential derivative. As examples we consider the optimal control problems for systems governed by partial nonlinear differential equations of several kinds.     

Optimal online detection of parameter changes in two linear models

Shiryaev has obtained the optimal sequential rule for detecting the instant of a distributional change in an independent sequence using the theory of optimal stopping of Markov processes. This paper considers the problem of sequential detection of certain parameter changes in two dependent sequences: an autoregressive process, and a regression model with serially correlated error terms. It is shown that the rule that is optimal in the sense of minimizing the expected positive delay is the one which declares a change to have occured as soon as the posterior probability of a change crosses a threshold. This rule also permits control of the probability of a false-declaration of change, just as in the independent sequence case.     

A periodic review production and maintenance model with random demand,deteriorating equipment,and binomial yield

In many environments, product yield is heavily influenced by equipment condition. Despite this fact, previous research has either focused on the issue of maintenance, ignoring the effect of equipment condition on yield, or has focused on the issue of production, omitting the possibility of actively changing the machine state. We formulate a Markov decision process model of a single-stage production system in which demand is random. The product yield has a binomial distribution that depends on the equipment condition, which deteriorates over time. The objective is to choose simultaneously the equipment maintenance schedule as well as the quantity to produce in a way that minimizes the sum of expected production, backorder, and holding costs. After proving some results about the structural properties of the optimal policy, numerical problems are used to compare this method to the typical approach of solving the maintenance and production problems sequentially. The results show that the simultaneous solution provides substantial gains over the sequential approach. In the cases studied, the proposed method resulted in an average cost savings of approximately 18%.     

Efficient Sequential Quadratic Programming Implementations for Equality-Constrained Discrete-Time Optimal Control

Efficient sequential quadratic programming (SQP) implementations are presented for equality-constrained, discrete-time, optimal control problems. The algorithm developed calculates the search direction for the equality-based variant of SQP and is applicable to problems with either fixed or free final time. Problem solutions are obtained by solving iteratively a series of constrained quadratic programs. The number of mathematical operations required for each iteration is proportional to the number of discrete times N. This is contrasted by conventional methods in which this number is proportional to N ³. The algorithm results in quadratic convergence of the iterates under the same conditions as those for SQP and simplifies to an existing dynamic programming approach when there are no constraints and the final time is fixed. A simple test problem and two application problems are presented. The application examples include a satellite dynamics problem and a set of brachistochrone problems involving viscous friction.     

Degeneracy in infinite horizon optimization

We consider sequential decision problems over an infinite horizon. The forecast or solution horizon approach to solving such problems requires that the optimal initial decision be unique. We show that multiple optimal initial decisions can exist in general and refer to their existence as degeneracy. We then present a conceptual cost perturbation algorithm for resolving degeneracy and identifying a forecast horizon. We also present a general near-optimal forecast horizon.This material is based on work supported by the National Science Foundation under Grants ECS-8409682 and ECS-8700836.