Improvement on the Nelder-Mead Simplex Algorithm and Its Application to Meteorology
-
摘要: Nelder-Mead Simplex (NMS) 算法是一种查找多元函数局地最小值的无微分算法,在现代科学计算中得到广泛应用,该文提出了一种对NMS算法的改进方法。改进后,大大简化了其计算过程,提高了该算法的收敛速度。利用改进后的算法对陆面过程参数进行了拟合计算,结果表明:改进的NMS算法对非线性公式具有非常高的拟合精度,可将其应用于气象学上非线性问题计算或非线性方程组求解。Abstract: Owing to computers providing great advantage in iterative calculation, the non-derivative algorithms have great potential applications to scientific research. Nelder-Mead Simplex (NMS) algorithm is a technique for minimizing an objective function in a multiple-dimensional space without differentiation, proposed by Nelder and Mead (1965). As a simple non-derivative technique, NMS algorithm is widely introduced in many computational books and used in numerical computations, and Matlab implements this algorithm for instance. Unfortunately, the method has some disadvantages such as slow converging and low precision, which need to be improved.Meteorological problems, usually nonlinear, are very complicated to solve, which require nonlinear fittings, solving the relationships between different meteorological variables, determining parameters in empirical formulas, solving the system of nonlinear equations and so forth. Conventionally, nonlinear problems are usually transformed into linear ones to solve, but this is not always practical. Fortunately the non-derivative algorithm could do this work, and an introduction to the application of the NMS algorithm to meteorological computations could be beneficial for meteorological community.An improvement on the NMS algorithm is proposed. To avoid the problems existing in the original NM simplex algorithm, a constraint is introduced to obtain next iterative point rather than finding the points of reflection, expansion, contraction and shrink, similar to that in the Powell's Method or in the Steepest Gradient algorithm. However, the searching direction is still along the downhill direction, i.e., the direction along the segment line between the vertex with the greatest functional value and the gravity center point. By introduction of the constraint, the multi-variable function will be transformed into a function with one variable, i.e., the constraint, which can be solved by the algorithms to calculate the minimum of a function with one variable, such as the Golden Section Search, Fibonacci Search and so forth. This approach will still keep the calculation without differentiation. After the improvement, the computation is greatly simplified, and its convergence will be accelerated.Some possible applications of the NMS algorithm to meteorology are also introduced, and it's also described how to implement the algorithm in fitting parameters in empirical formulas and solving the system of nonlinear equations.To testify this improvement, fitting experiments to some parameters in land surface process are made using the modified algorithm. Relationships between zero plane displacement and leaf area index (ILA) and between aerodynamic resistance and ILA at ground surface are calculated using the Least Square Method and the NMS algorithm to determine parameters. Experimental results show that the proposed algorithm have very high precision when fitting nonlinear formulas, therefore it can be used in computations for solving nonlinear issues or the system of nonlinear equations.
-
Key words:
- NMS algorithm;
- improvement;
- non-derivative;
- meteorology;
- nonlinear application
-
[1] Mordecai Avriel. Nonlinear Programming, Analysis and Methods. New Jersey: Prentice-Hall Inc, 1976. [2] William H P, Saul A T, William T V, et al. Numerical Recipes 3rd Edition: The Art of Scientific Computing, Chapter 9. Cambridge: Cambridge University Press, 2007. [3] Powell M J D. A method for minimizing a sum of squares of non-linear functions without calculating derivatives. Computer Journal, 1965, 7: 303-307. doi: 10.1093/comjnl/7.4.303 [4] Brent R P. Algorithms for Minimization Without Derivatives, Chapter 7. Dover, 2002. [5] Mathews J H, Kurtis K F. Numerical Methods Using Matlab, 4th Edition. New Jersey: Prentice-Hall Inc, 2004. [6] 钟爱华, 严华生, 李跃清, 等.青藏高原积雪异常与大气环流异常间关系分析.应用气象学报, 2010, 21(1):37-46. doi: 10.11898/1001-7313.20100105 [7] 郑栋, 张义军, 孟青, 等.北京地区雷暴过程闪电与地面降水的相关关系.应用气象学报, 2010, 21(3):287-297. doi: 10.11898/1001-7313.20100304 [8] 陈正洪, 王海军, 张小丽.水文学中雨强公式参数求解的一种最优化方法.应用气象学报, 2007, 18(2):237-241. doi: 10.11898/1001-7313.20070240 [9] 窦贤康, Amaye P.机载雷达定量测雨中雨滴谱参数的优化.应用气象学报, 1999, 10(3):293-298. http://qikan.camscma.cn/jams/ch/reader/view_abstract.aspx?file_no=19990371&flag=1 [10] 曾庆存.数值天气预报的数学物理基础 (第一卷).北京:科学出版社, 1979. [11] Nelder J A, Mead R. A simplex method for function minimization. Computer Journal, 1965, 7: 308-313. doi: 10.1093/comjnl/7.4.308 [12] Tomick J, Arnold S F, Barton R R. Sample Size Selection for Improved Nelder-Mead Performance. 1995 Winter Simulation Conference (WSC'95), 1995: 341-345. [13] Russell R B, John S I Jr. Nelder-Mead Simplex Modifications for Simulation Optimization. Management Science, 1996, 42(7): 954-973. doi: 10.1287/mnsc.42.7.954 [14] David G H, James R W. A revised simplex search procedure for stochastic simulation response surface optimization. Informs Journal on Computing, 2000, 12(4): 272-283. doi: 10.1287/ijoc.12.4.272.11879 [15] 王体健, 李宗恺.不同方案求解非线性化学动力方程组的比较.应用气象学报, 1996, 7(4):466-472. http://qikan.camscma.cn/jams/ch/reader/view_abstract.aspx?file_no=19960471&flag=1 [16] Yarbro L A, Stanley N D. Selection and preprocessing of factors for simplex optimization. Analytica Chimica Acta, 1974, 73: 391-398. doi: 10.1016/S0003-2670(01)85476-3 [17] Xue Y, Sellers P J, Kinter J L Ⅲ, et al. A simplified biosphere model for global climate studies. J Climate, 1991, 4: 345-364. doi: 10.1175/1520-0442(1991)004<0345:ASBMFG>2.0.CO;2 [18] Sellers P J, Randall D A, Collatz G J, et al. A revised land surface parameterization (SiB2) for atmospheric GCMs. Part Ⅰ: Model formulation. J Climate, 1996, 9: 676-705. doi: 10.1175/1520-0442(1996)009<0676:ARLSPF>2.0.CO;2