Sequential Importance Sampling Algorithms for Dynamic Stochastic Programming

This paper gives a comprehensive treatment of EVPI-based sequential importance sampling algorithms for dynamic (multistage) stochastic programming problems. Both theory and computational algorithms are discussed. Under general assumptions it is shown that both an expected value of perfect information (EVPI) process and the corresponding marginal EVPI process (the supremum norm of the conditional expectation of its generalized derivative) are nonanticipative nonnegative supermartingales. These processes are used as importance criteria in the class of sampling algorithms treated in the paper. When their values are negligible at a node of the current sample problem scenario tree, scenarios descending from the node are replaced by a single scenario at the next iteration. On the other hand, high values lead to increasing the number of scenarios descending from the node. Both the small sample and asymptotic properties of the sample problem estimates arising from the algorithms are established, and the former are evaluated numerically in the context of a financial planning problem. Finally, current and future research is described. Bibliography: 49 titles. __________ Published in Zapiski Nauchnykh Seminarov POMI, Vol. 312, 2004, pp. 94–129.     

A Dynamic Programming Formulation with Diverse Applications

A dynamic programming formulation is shown to have applications in such diverse fields as archaeological sequencing and rehearsal scheduling.     

Robust Process Control by Dynamic Stochastic Programming

Unnecessarily conservative behavior of standard process control techniques can be avoided by stochastic programming models when the distribution of random disturbances is known. In an earlier study we have investigated such an approach for tank level constraints of a distillation process. Here we address techniques that have accelerated the numerical solution of the large and expensive stochastic programs by a factor of six, and then present a refined optimization model for the same application. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Dynamic Programming Formulation of the Redundancy Allocation Problem

Dynamic programming formulation for obtaining the optimum number of redundancies at each stage in a system is explained in detail. It is also emphasized and illustrated by examples, that the ‘summation’ form of functional equations, as suggested in the paper, provide a faster solution to an otherwise computationally voluminous method.     

基于随机动态规划的有限库存ATO系统优化控制

本文研究n维组件单一产品,有限库存的ATO系统。通过建立马尔可夫决策过程模型(MDP),构造优化算法,研究组件生产与库存的最优控制策略。最优策路可以表示为状态依赖型库存阈值,系统内任一组件的控制策略受其它组件库存状态的影响。利用最优控制理论动态规划方法和数值计算方法对最优控制策略的存在性、最优值的数值计算进行研究,建立更符合实际生产的ATO系统决策模型,进行相应的理论和实验验证,研究系统参数对最优策略的影响。     

Case Studies for a First-Order Robust Nonlinear Programming Formulation

In this paper, we conduct three case studies to assess the effectiveness of a recently proposed first-order method for robust nonlinear programming [Zhang, Y.: J. Optim. Theory Appl. 132, 111–124 (2007)]. Three robust nonlinear programming problems were chosen from the literature using the criteria that results calculated using other methods must be available and the problems should be realistic, but fairly simple. Our studies show that the first-order method produced reasonable solutions when the level of uncertainty was small to moderate. In addition, we demonstrate a method for leveraging a theoretical result to eliminate constraint violations. Since the first-order method is relatively inexpensive in comparison to other robust optimization techniques, our studies indicate that, under moderate uncertainty, the first-order approach may be more suitable than other methods for large problems. The authors recognize funding from NSF Grants DMS-0405831 and DMS-0240058.     

General Robust-Optimization Formulation for Nonlinear Programming

Most research in robust optimization has been focused so far on inequality-only, convex conic programming with simple linear models for the uncertain parameters. Many practical optimization problems, however, are nonlinear and nonconvex. Even in linear programming, the coefficients may still be nonlinear functions of the uncertain parameters. In this paper, we propose robust formulations that extend the robust-optimization approach to a general nonlinear programming setting with parameter uncertainty involving both equality and inequality constraints. The proposed robust formulations are valid in a neighborhood of a given nominal parameter value and are robust to the first-order, thus suitable for applications where reasonable parameter estimations are available and uncertain variations are moderate. This work was supported in part by NSF Grant DMS-0405831     

Decomposition Algorithms for Stochastic Programming on a Computational Grid

We describe algorithms for two-stage stochastic linear programming with recourse and their implementation on a grid computing platform. In particular, we examine serial and asynchronous versions of the L-shaped method and a trust-region method. The parallel platform of choice is the dynamic, heterogeneous, opportunistic platform provided by the Condor system. The algorithms are of master-worker type (with the workers being used to solve second-stage problems), and the MW runtime support library (which supports master-worker computations) is key to the implementation. Computational results are presented on large sample-average approximations of problems from the literature.     

Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation

Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n × n matrix-valued function of a certain form into the positivity constraint on n scalar variables while keeping the number of variables unchanged. Based on this transformation, they proposed a first-order interior-point algorithm for solving a special class of linear semidefinite programs. In this paper, we extend this approach and apply the transformation to general linear semidefinite programs, producing nonlinear programs that have not only the n positivity constraints, but also n additional nonlinear inequality constraints. Despite this complication, the transformed problems still retain most of the desirable properties. We propose first-order and second-order interior-point algorithms for this type of nonlinear program and establish their global convergence. Computational results demonstrating the effectiveness of the first-order method are also presented.     

多属性决策中的目标规划

针对只有部分权重信息的对方案有偏好的多属性决策问题,本文给出了一种简单的目标规划模型,通过对该模型的求解却可得到决策方案的排序。最后给出了一个算例。     

二层随机规划基于随机模拟的遗传算法

本提出了二层随机规划模型，给出了求解二层随机规划问题的基于随机模拟的遗传算法。实际算例表明算法是可行的、有效的。     

Converging Marriage in Honey-Bees Optimization and Application to Stochastic Dynamic Programming

In this paper, we first refine a recently proposed metaheuristic called “Marriage in Honey-Bees Optimization” (MBO) for solving combinatorial optimization problems with some modifications to formally show that MBO converges to the global optimum value. We then adapt MBO into an algorithm called “Honey-Bees Policy Iteration” (HBPI) for solving infinite horizon-discounted cost stochastic dynamic programming problems and show that HBPI also converges to the optimal value.     

Ergodicity for Nonlinear Stochastic Equations in Variational Formulation

This paper is concerned with nonlinear partial differential equations of the calculus of variation (see [13]) perturbed by noise. Well-posedness of the problem was proved by Pardoux in the seventies (see [14]), using monotonicity methods. The aim of the present work is to investigate the asymptotic behaviour of the corresponding transition semigroup P_t. We show existence and, under suitable assumptions, uniqueness of an ergodic invariant measure ν. Moreover, we solve the Kolmogorov equation and prove the so-called "identite du carre du champs". This will be used to study the Sobolev space W^1,2(H,ν) and to obtain information on the domain of the infinitesimal generator of P_t.