×

The multidimensional moment-constrained maximum entropy problem: A BFGS algorithm with constraint scaling. (English) Zbl 1157.65381

Summary: In [the author, ibid. 226, No. 1, 621–644 (2007; Zbl 1125.65010)], 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.

MSC:

65K05 Numerical mathematical programming methods

Citations:

Zbl 1125.65010

Software:

LBFGS-B
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramov, R., A practical computational framework for the multidimensional moment-constrained maximum entropy principle, J. Comp. Phys., 211, 1, 198-209 (2006) · Zbl 1080.65007
[2] Abramov, R., An improved algorithm for the multidimensional moment-constrained maximum entropy problem, J. Comp. Phys., 226, 621-644 (2007) · Zbl 1125.65010
[3] Abramov, R.; Majda, A., Quantifying uncertainty for non-Gaussian ensembles in complex systems, SIAM J. Sci. Comp., 26, 2, 411-447 (2003) · Zbl 1137.94004
[4] Abramov, R.; Majda, A.; Kleeman, R., Information theory and predictability for low frequency variability, J. Atmos. Sci., 62, 1, 65-87 (2005)
[5] Bandyopadhyay, K.; Bhattacharya, A.; Biswas, P.; Drabold, D., Maximum entropy and the problem of moments: A stable algorithm, Phys. Rev. E, 71, 5 (2005)
[6] Broyden, C., The convergence of a class of double-rank minimization algorithms, J. Inst. Math. Appl., 6, 76-90 (1970) · Zbl 0223.65023
[7] Byrd, R.; Lu, P.; Nocedal, J., A limited memory algorithm for bound-constrained optimization, SIAM J. Sci. Comp., 16, 6, 1190-1208 (1995) · Zbl 0836.65080
[8] Dax, A., A modified Gram-Schmidt algorithm with iterative orthogonalization and column pivoting, Linear Algebra Appl., 310, 25-42 (2000) · Zbl 0990.65047
[9] Fletcher, R., A new approach to variable metric algorithms, Comp. J., 13, 317-322 (1970) · Zbl 0207.17402
[10] Giraud, L.; Langou, J., When modified Gram-Schmidt generates a well-conditioned set of vectors, IMA J. Num. Anal., 22, 521-528 (2002) · Zbl 1027.65050
[11] L. Giraud, J. Langou, M. Rozložník. On the round-off error analysis of the Gram-Schmidt algorithm with reorthogonalization. Technical Report TR/PA/02/33, CERFACS, 2002.; L. Giraud, J. Langou, M. Rozložník. On the round-off error analysis of the Gram-Schmidt algorithm with reorthogonalization. Technical Report TR/PA/02/33, CERFACS, 2002.
[12] L. Giraud, J. Langou, M. Rozložník. On the loss of orthogonality in the Gram-Schmidt orthogonalization process. Technical Report TR/PA/03/25, CERFACS, 2003.; L. Giraud, J. Langou, M. Rozložník. On the loss of orthogonality in the Gram-Schmidt orthogonalization process. Technical Report TR/PA/03/25, CERFACS, 2003. · Zbl 1085.65037
[13] Goldfarb, D., A family of variable metric updates derived by variational means, Math. Comp., 24, 23-26 (1970) · Zbl 0196.18002
[14] Golub, G.; Van Loan, C., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 0865.65009
[15] Haven, K.; Majda, A.; Abramov, R., Quantifying predictability through information theory: Small sample estimation in a non-Gaussian framework, J. Comp. Phys., 206, 334-362 (2005) · Zbl 1088.62502
[16] Haydock, R.; Nex, C., Comparison of quadrature and termination for estimating the density of states within the recursion method, J. Phys. C: Solid State Phys., 17, 4783-4789 (1984)
[17] Haydock, R.; Nex, C., A general terminator for the recursion method, J. Phys. C: Solid State Phys., 18, 235-2248 (1985)
[18] McCalpin, J., The statistics and sensitivity of a double-gyre model: The reduced gravity, quasigeostrophic case, J. Phys. Oceanogr., 25, 806-824 (1995)
[19] McCalpin, J.; Haidvogel, D., Phenomenology of the low-frequency variability in a reduced-gravity, quasigeostrophic double-gyre model, J. Phys. Oceanogr., 26, 739-752 (1996)
[20] Ormoneit, D.; White, H., An efficient algorithm to compute maximum entropy densities, Econ. Rev., 18, 2, 127-140 (1999) · Zbl 0932.62006
[21] Shanno, D., Conditioning of quasi-Newton methods for function minimization, Math. Comp., 24, 647-656 (1970) · Zbl 0225.65073
[22] Turek, I., A maximum-entropy approach to the density of states with the recursion method, J. Phys. C, 21, 3251-3260 (1988)
[23] Wu, X., Calculation of maximum entropy densities with application to income distribution, J. Econ., 115, 347-354 (2003) · Zbl 1016.62094
[24] Wu, Z.; Phillips, G.; Tapia, R.; Zhang, Y., A fast Newton algorithm for entropy maximization in phase determination, SIAM Rev., 43, 4, 623-642 (2001) · Zbl 0992.65069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.