...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematics of operations research >On constraint sampling in the linear programming approach to approximate dynamic programming
【24h】

On constraint sampling in the linear programming approach to approximate dynamic programming

机译：关于线性规划方法中的约束采样近似动态规划

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the linear programming approach to approximate dynamic programming, one tries to solve a certain linear program-the ALP-that has a relatively small number K of variables but an intractable number M of constraints. In this paper, we study a scheme that samples and imposes a subset of m much less than M constraints. A natural question that arises in this context is: How must m scale with respect to K and M in order to ensure that the resulting approximation is almost as good as one given by exact solution of the ALP? We show that, given an idealized sampling distribution and appropriate constraints on the K variables, m can be chosen independently of M and need grow only as a polynomial in K. We interpret this result in a context involving controlled queueing networks.
机译：在近似于动态规划的线性规划方法中，人们试图求解一种线性规划-ALP，该规划具有相对较小的变量K和有限的约束M。在本文中，我们研究了一种采样并施加m个子集的方案，该子集比M个约束要少得多。在这种情况下出现的一个自然问题是：m如何相对于K和M缩放，以确保所得近似值几乎与ALP精确解给出的近似值一样好？我们表明，在理想的采样分布和对K变量适当约束的情况下，可以独立于M选择m，并且仅需要将其增长为K中的多项式。我们在涉及受控排队网络的上下文中解释此结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号