A Stochastic Approximation Algorithm with Varying Bounds
A Stochastic Approximation Algorithm with Varying Bounds
复制标题
一种变界随机逼近算法
DOI：
10.1287/opre.43.6.1037
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
S. Andradóttir
中科院分区：
文献类型：
--
作者：
S. Andradóttir
许多传统方法难以解决的优化问题将屈服于随机逼近算法。这是因为这些算法可用于优化无法分析评估但必须估计（例如通过模拟）或测量的函数。因此，随机近似算法可用于仿真中的优化。不幸的是，经典的随机逼近算法有时会因为无界问题而发散。我们研究了在不断增长的紧集序列上定义的随机近似变体的收敛性。我们证明，与经典算法相比，该变体在更一般的条件下收敛于目标函数，同时保持相同的渐近收敛速度。我们还提供了经验证据，表明该算法有时比经典算法收敛得快得多。
Many optimization problems that are intractable with conventional approaches will yield to stochastic approximation algorithms. This is because these algorithms can be used to optimize functions that cannot be evaluated analytically, but have to be estimated (for instance, through simulation) or measured. Thus, stochastic approximation algorithms can be used for optimization in simulation. Unfortunately, the classical stochastic approximation algorithm sometimes diverges because of unboundedness problems. We study the convergence of a variant of stochastic approximation defined over a growing sequence of compact sets. We show that this variant converges under more general conditions on the objective function than the classical algorithm, while maintaining the same asymptotic convergence rate. We also present empirical evidence that shows that this algorithm sometimes converges much faster than the classical algorithm.