Convergence analysis of truncated incomplete Hessian Newton minimization method and application in biomolecular potential energy minimization. (English) Zbl 1219.90189
Summary: This paper gives a general convergence analysis to the truncated incomplete Hessian Newton method (T-IHN). It shows that T-IHN is globally convergent even with an indefinite incomplete Hessian matrix or an indefinite preconditioner, which may happen in practice. It also proves that when the T-IHN iterates are close enough to a minimum point, T-IHN has a Q-linear rate of convergence, and an admissible line search steplength of one. Moreover, a particular T-IHN algorithm is constructed for minimizing a biomolecular potential energy function, and numerically tested for a protein model problem based on a widely used molecular simulation package, CHARMM. Numerical results confirm the theoretical results, and demonstrate that T-IHN can have a better performance (in terms of computer CPU time) than most CHARMM minimizers.
Keywords:
truncated-Newton method; incomplete Hessian Newton method; convergence analysis; molecular potential minimizationReferences:
| [1] | Allen, M.P., Tildesley, D.J.: Computer Simulation of Liquids. Oxford University Press, London (1990) · Zbl 0703.68099 |
| [2] | Baker, N.A.: Improving implicit solvent simulations: a Poisson-centric view. Curr. Opin. Struct. Biol. 15, 137–143 (2005) · doi:10.1016/j.sbi.2005.02.001 |
| [3] | Brooks, B.R., Bruccoleri, R.E., Olafson, B.D., States, D.J., Swaminathan, S., Karplus, M.: CHARMM: a program for macromolecular energy, minimization, and dynamics calculations. J. Comput. Chem. 4, 187–217 (1983) · doi:10.1002/jcc.540040211 |
| [4] | Chu, J.W., Trout, B.L., Brooks, B.R.: A super-linear minimization scheme for the nudged elastic band method. J. Chem. Phys. 119(24), 12708–12717 (2003) · doi:10.1063/1.1627754 |
| [5] | Cornell, W.D., Cieplak, P., Bayly, C.I., Gould, I.R., Merz, K.M. Jr., Ferguson, D.M., Spellmeyer, D.C., Fox, T., Caldwell, J.W., Kollman, P.A.: A second generation force field for the simulation of proteins, nucleic acids, and organic molecules. J. Am. Chem. Soc. 117, 5179–5197 (1995) · doi:10.1021/ja00124a002 |
| [6] | Dembo, R.S., Steihaug, T.: Truncated-Newton algorithms for large-scale unconstrained optimization. Math. Program. 26, 190–212 (1983) · Zbl 0523.90078 · doi:10.1007/BF02592055 |
| [7] | Dennis, J.E. Jr., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Inc., Englewood Cliffs (1983). Reprinted with corrections by SIAM, Philadelphia (1996) · Zbl 0579.65058 |
| [8] | Derreumaux, P., Zhang, G., Brooks, B., Schlick, T.: A truncated-Newton method adapted for CHARMM and biomolecular applications. J. Comput. Chem. 15, 532–552 (1994) · doi:10.1002/jcc.540150506 |
| [9] | Fletcher, R., Reeves, C.M.: Function minimization by conjugate gradients. Comput. J. 7(2), 149–154 (1964) · Zbl 0132.11701 · doi:10.1093/comjnl/7.2.149 |
| [10] | Gill, P.E., Murray, W.: Newton-type methods for unconstrained and linearly constrained optimization. Math. Program. 28, 311–350 (1974) · Zbl 0297.90082 · doi:10.1007/BF01585529 |
| [11] | Golub, G.H., van Loan, C.F.: Matrix Computations, 2nd edn. John Hopkins University Press, Baltimore (1986) · Zbl 1118.65316 |
| [12] | Hess, B., Kutzner, C., van der Spoel, D., Lindahl, E.: Gromacs 4: algorithms for highly efficient, load-balanced, and scalable molecular simulation. J. Chem. Theor. Comput. 4, 435–447 (2008) · doi:10.1021/ct700301q |
| [13] | MacKerell, A.D. Jr., Foloppe, N.: All-atom empirical force field for nucleic acids: I. Parameter optimization based on small molecule and condensed phased macromolecular target data. J. Comput. Chem. 21, 86–104 (2000) · doi:10.1002/(SICI)1096-987X(20000130)21:2<86::AID-JCC2>3.0.CO;2-G |
| [14] | MacKerell, A.D. Jr., Foloppe, N.: All-atom empirical force field for nucleic acids: II. Application to molecular dynamics simulations of DNA and RNA in solution. J. Comput. Chem. 21, 105–120 (2000) · doi:10.1002/(SICI)1096-987X(20000130)21:2<105::AID-JCC3>3.0.CO;2-P |
| [15] | Molecular mechanics and modeling. Chem. Rev. 93(7), (1993). Special issue |
| [16] | Moré, J.J., Thuente, D.J.: Line search algorithms with guaranteed sufficient decrease. ACM Trans. Math. Softw. 20, 286–307 (1994) · Zbl 0888.65072 · doi:10.1145/192115.192132 |
| [17] | Nelson, M., Humphrey, W., Gursoy, A., Dalke, A., Kalé, L., Skeel, R.D., Schulten, K.: NAMD–a parallel, object-oriented molecular dynamics program. Int. J. Supercomput. Appl. High Perform. Comput. 10(4), 251–268 (1996) · doi:10.1177/109434209601000401 |
| [18] | Neumaier, A.: Molecular modeling of proteins and mathematical prediction of protein structure. SIAM Rev. 39, 407–460 (1997) · Zbl 0939.92013 · doi:10.1137/S0036144594278060 |
| [19] | Nocedal, J., Wright, S.: Numerical Optimization, 2nd edn. Springer, New York (2006) · Zbl 1104.65059 |
| [20] | Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, San Diego (1970) · Zbl 0241.65046 |
| [21] | Roux, B., Simonson, T.: Implicit solvent models. Biophys. Chem. 78, 1–20 (1999) · doi:10.1016/S0301-4622(98)00226-9 |
| [22] | Schlick, T.: Geometry optimization. In: von Ragué Schleyer, P.R., Allinger, N.L., Clark, T., Gasteiger, J., Kollman, P.A., Schaefer, H.F. III (eds.) Encyclopedia of Computational Chemistry, vol. 2, pp. 1136–1157. Wiley, New York (1998) |
| [23] | Schlick, T.: Molecular Modeling and Simulation, an Interdisciplinary Guide. Springer, New York (2002) · Zbl 1011.92019 |
| [24] | Schlick, T., Overton, M.L.: A powerful truncated Newton method for potential energy functions. J. Comput. Chem. 8, 1025–1039 (1987) · doi:10.1002/jcc.540080711 |
| [25] | Schlick, T., Fogelson, A.: TNPACK–a truncated Newton minimization package for large-scale problems: I. Algorithm and usage. ACM Trans. Math. Softw. 14, 46–70 (1992) · Zbl 0892.65030 · doi:10.1145/128745.150973 |
| [26] | Scott, W.R.P., Hünenberger, P.H., Tironi, I.G., Mark, A.E., Billeter, S.R., Fennen, J., Torda, A.E., Huber, T., Krüger, P., van Gunsteren, W.F.: The GROMOS biomolecular simulation program package. J. Phys. Chem. A 103, 3596–3607 (1999) · doi:10.1021/jp984217f |
| [27] | Sundaram, R.K.: A First Course in Optimization Theory. Cambridge University Press, Cambridge (1996) · Zbl 0885.90106 |
| [28] | Xie, D.: An Effective Compressed Sparse Preconditioner for Large Scale Biomolecular Simulations. Lecture Notes in Computer Science, vol. 3314, pp. 64–70. Springer, Berlin (2004) · Zbl 1117.92300 |
| [29] | Xie, D., Schlick, T.: Efficient implementation of the truncated Newton method for large-scale chemistry applications. SIAM J. Optim. 10(1), 132–154 (1999) · Zbl 0956.65049 · doi:10.1137/S1052623497313642 |
| [30] | Xie, D., Schlick, T.: Remark on the updated truncated Newton minimization package, algorithm 702. ACM. Trans. Math. Softw. 25(1), 108–122 (1999) · Zbl 0963.65064 · doi:10.1145/305658.305698 |
| [31] | Xie, D., Schlick, T.: Visualization of chemical databases using the singular value decomposition and truncated-Newton minimization. In: Floudas, C.A., Pardalos, P. (eds.) Optimization in Computational Chemistry and Molecular Biology: Local and Global Approaches, pp. 267–286. Kluwer Academic, Dordrecht (2000) · Zbl 0955.92017 |
| [32] | Xie, D., Schlick, T.: A more lenient stopping rule for line search algorithms. Optim. Methods Softw. 17(4), 683–700 (2002) · Zbl 1040.90039 · doi:10.1080/1055678021000049363 |
| [33] | Xie, D., Zhou, S.: A new minimization protocol for solving nonlinear Poisson-Boltzmann mortar finite element equation. BIT 47, 853–871 (2007) · Zbl 1147.65096 · doi:10.1007/s10543-007-0145-9 |
| [34] | Xie, D., Ni, Q.: An incomplete Hessian Newton minimization method and its application in a chemical database problem. Comput. Optim. Appl. Published online: 12 January 2008 · Zbl 1181.90195 |
| [35] | Xie, D., Singh, S.B., Fluder, E.M., Schlick, T.: Principal component analysis combined with truncated-Newton minimization for dimensionality reduction of chemical databases. Math. Program. 95(1), 161–185 (2003) · Zbl 1030.90514 · doi:10.1007/s10107-002-0345-7 |
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.
