The multidimensional moment-constrained maximum entropy problem: A BFGS algorithm with constraint scaling
The multidimensional moment-constrained maximum entropy problem: A BFGS algorithm with constraint scaling
复制标题
DOI：
10.1016/j.jcp.2008.08.020
复制
发表时间：
2009-01-10
影响因子：
4.1
通讯作者：
Abramov, Rafail V.
中科院分区：
文献类型：
--
作者：
Abramov, Rafail V.
在最近的一篇文章中，我们发展了一种新的算法来求解多维情形下的矩约束最大熵问题，在拉格朗日乘子的对偶空间中使用多维正交多项式基来实现数值稳定性和牛顿迭代的快速收敛。在这里，我们对现有算法进行了两个新的改进，在有许多矩约束的情况下，增加了显著的计算加速比，而原始算法的收敛速度很慢。第一个改进是使用BFGS迭代在连续的多项式重新正交化之间进行，而不是在单个牛顿步长之间进行，典型地减少了相同最大熵问题的计算代价高昂的多项式重新正交化的总数。第二个改进是约束重标度，目的是减小不同矩约束之间在量级上的相对差异，由于不同约束对拉格朗日乘子变化的敏感性降低，从而提高迭代的数值稳定性。我们观察到，与原始算法相比，这两个改进可以产生平均挂钟时间加速比5-6倍。(C)2008 Elsevier Inc.保留所有权利。
In a recent paper we developed a new algorithm for the moment-constrained maximum entropy problem in a multidimensional setting, using a multidimensional orthogonal polynomial basis in the dual space of Lagrange multipliers to achieve numerical stability and rapid convergence of the Newton iterations. Here we introduce two new improvements for the existing algorithm, adding significant computational speedup in situations with many moment constraints, where the original algorithm is known to converge slowly. The first improvement is the use of the BFGS iterations to progress between successive polynomial reorthogonalizations rather than single Newton steps, typically reducing the total number of computationally expensive polynomial reorthogonalizations for the same maximum entropy problem. The second improvement is a constraint rescaling, aimed to reduce relative difference in the order of magnitude between different moment constraints, improving numerical stability of iterations due to reduced sensitivity of different constraints to changes in Lagrange multipliers. We observe that these two improvements can yield an average wall clock time speedup of 5-6 times compared to the original algorithm. (C) 2008 Elsevier Inc. All rights reserved.