The multidimensional moment-constrained maximum entropy problem: A BFGS algorithm with constraint scaling
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 56 times compared to the original algorithm.
maximum entropy problem moment constraints convex optimization numerical methods