...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Automatic Control, IEEE Transactions on >Optimal Approximation Schedules for a Class of Iterative Algorithms, With an Application to Multigrid Value Iteration
【24h】

Optimal Approximation Schedules for a Class of Iterative Algorithms, With an Application to Multigrid Value Iteration

机译：一类迭代算法的最佳逼近进度表及其在多网格值迭代中的应用

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

摘要

Many iterative algorithms employ operators which are difficult to evaluate exactly, but for which a graduated range of approximations exist. In such cases, “coarse-to-fine” algorithms are often used, in which a crude initial operator approximation is gradually refined with new iterations. In such algorithms, because the computational complexity increases over iterations, the algorithm's convergence rate is properly calculated with respect to cumulative computation time. This suggests the problem of determining an optimal rate of refinement for the operator approximation. This paper shows that, for linearly convergent algorithm, the optimal rate of refinement approaches the rate of convergence of the exact algorithm itself, regardless of the tolerance-complexity relationship. We illustrate this result with an analysis of “coarse-to-fine” grid algorithms for Markov decision processes with continuous state spaces. Using the methods proposed here we deduce an algorithm that presents optimal complexity results and consists solely of a non-adaptive schedule for the gradual decrease of grid size.
机译：许多迭代算法采用的运算符很难精确评估，但是存在近似的渐变范围。在这种情况下，通常使用“粗到精”算法，其中粗略的初始算子近似值通过新的迭代逐渐完善。在这样的算法中，由于计算复杂度随着迭代的增加而增加，因此相对于累积计算时间可以适当地计算算法的收敛速度。这提示了确定用于算子逼近的最佳细化率的问题。本文表明，对于线性收敛算法，无论容差与复杂度之间的关系如何，最优细化率都接近精确算法本身的收敛率。我们通过分析具有连续状态空间的Markov决策过程的“粗到精”网格算法来说明此结果。使用此处提出的方法，我们推导了一种算法，该算法可呈现最佳复杂性结果，并且仅包含用于网格大小逐渐减小的非自适应调度。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号