A Derivative-Free Optimization Algorithm Using Sparse Grid Integration

Shengyuan Chen, Xiaogang Wang

Department of Mathematics and Statistics, York University, Toronto, Canada.

DOI: 10.4236/ajcm.2013.31003                

Abstract

We present a new derivative-free optimization algorithm based on the sparse grid numerical integration. The algorithm applies to a smooth nonlinear objective function where calculating its gradient is impossible and evaluating its value is also very expensive. The new algorithm has: 1) a unique starting point strategy; 2) an effective global search heuristic; and 3) consistent local convergence. These are achieved through a uniform use of sparse grid numerical integration. Numerical experiment result indicates that the algorithm is accurate and efficient, and benchmarks favourably against several state-of-art derivative free algorithms.

Keywords

Nonlinear Programming; Derivative Free Optimization; Sparse Grid Numerical Integration; Conditional Moment

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	J. D. Pinter, “Global Optimization in Action,” Kluwer, Dordrecht, 1996. doi:10.1007/978-1-4757-2502-5
[2]	A. J. Booker, J. E. Dennis Jr., P. D. Frank, D. W. Moore and D. B. Serafini, “Managing Surrogate Objectives to Optimize a Helicopter Rotor Design: Further Experiments,” Proceedings of 8th AIAA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, St. Louis, 1998.
[3]	C. Audet and D. Orban, “Finding Optimal Algorithmic Parameters Using Derivative-Free Optimization,” SIAM Journal on Optimization, Vol. 17, No. 3, 2006, pp. 642-664.
[4]	R. Oeuvary and M. Bierlaire, “A New Derivative-Free Algorithm for the Medical Image Registration Problem,” International Journal of Modelling and Simulation, Vol. 27, No. 2, 2007, pp. 115-124.
[5]	T. Levina, Y. Levin, J. Mcgill and M. Nediak, “Dynamic Pricing with Online Learning and Strategic Consumers: An Application of the Aggregation Algorithm,” Operations Research, Vol. 57, No. 2, 2009, pp. 327-341.
[6]	P. Mugunthan, C. A. Showmaker and R. G. Regis, “Comparison of Function Approximation, Heuristic and Derivative-Based Methods for Automatic Calibration of Computationally Expensive Groundwater Bioremediation Models,” Water Resources, Vol. 41, 2005.
[7]	J. A. Neldder and R. Mead, “A Simplex Method for Function Minimization,” The Computer Journal, Vol. 7, No. 4, 1965, pp. 308-313. doi:10.1093/comjnl/7.4.308
[8]	C. Audet and J. E. dennis Jr., “Analysis of Generalized Pattern Searches,” SIAM Journal on Optimization, Vol. 13, No. 3, 2003, pp. 889-903. doi:10.1137/S1052623400378742
[9]	T. G. Kolda, R. M. Lewis and V. Torczon, “Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods,” SIAM Review, Vol. 45, No. 3, 2003, pp. 385-482. doi:10.1137/S003614450242889
[10]	T. A. Winslow, R. J. Trew, P. Gilmore and C. T. Kelley. “Doping Profiles for Optimum Class B Performance of GaAs MESFET Amplifiers,” Proceedings of the IEEE/ Cornell Conference on Advanced Concepts in High Speed Devices and Circuits, Ithaca, 5-7 August 1991, pp. 188-197.
[11]	A. R. Conn, K. Scheinberg and P. L. Toint, “On the Convergence of Derivative-Free Methods for Unconstrained Optimization,” Approximation Theory and Optimization: Tributes to M. J. D. Powell, Cambridge University Press, Cambridge, 1997, pp. 83-108.
[12]	M. J. D. Powell, “The NEWUOA Software for Unconstrained Optimization without Derivatives,” Technical Report, DAMTP 2004/NA08, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, 2004.
[13]	M. Marazzi and J. Nocedal, “Wedge Trust Region Methods for Derivative Free Optimization,” Mathematical Programming, Vol. 91, No. 2, 2002, pp. 289-305. doi:10.1007/s101070100264
[14]	A. R. Conn, K. Scheinberg and L. N. Vicent, “Introduction to Derivative-Free Optimization,” MOS-SIAM Series on Optimization, SIAM, Philadelphia, 2009. doi:10.1137/1.9780898718768
[15]	C. Audet and J. E. Dennis Jr., “Mesh Adaptive Direct Search Algorithms for Constrained Optimization,” SIAM Journal on Optimization, Vol. 17, No. 1, 2006, pp. 188-217. doi:10.1137/040603371
[16]	D. Jones, C. Perttunen and B. Stuckman, “Lipschitzian Optimization without the Lipschitz Constant,” Journal of Optimization Theory Applications, Vol. 79, No. 1, 1993, pp. 157-181, doi:10.1007/BF00941892
[17]	W. Huyer and A. Neumaier, “Global Optimization by Multileve Coordinate Search,” Journal of Global Optimization, Vol. 14, No. 4, 1999, pp. 331-355. doi:10.1023/A:1008382309369
[18]	X. Wang, D. Liang, X. Feng and L. Ye, “A Derivative-Free Optimization Algorithm Based on Conditional Moments,” Journal of Mathematical Analysis and Applications, Vol. 331, No. 2, 2006, pp. 1337-1360.
[19]	G. W. Wasilkowsi and H. Wozniakowski, “Explicit Cost Bounds of Algorithms for Multivariate Tensor Product problems,” Journal of Complexity, Vol. 11, No. 1, 1995, pp. 1-56. doi:10.1006/jcom.1995.1001
[20]	M. S. Bazarra, H. D. Sherali and C. M. Shetty, “Nonlinear Programming: Theory and Algorithms,” 3rd Edition, Wiley, John & Sons, Hoboken, 2006.
[21]	H.-J. Bungartz and M. Griebel, “Sparse Grids,” Acta Numerica, Vol. 13, 2004, pp. 147-269.
[22]	T. Gerstner and M. Griebel, “Numerical Integration Using Sparse Grid,” Numerical Algorithms, Vol. 18, 1998, pp. 209-232.
[23]	F.-J. Delvos, “D-Variate Boolean Interpolation,” Journal of Approximation Theory, Vol. 34, No. 2, 1982, pp. 99-114. doi:10.1016/0021-9045(82)90085-5
[24]	A. R. Conn, N. I. M. Gould and P. L. Toint, “Trust-Region Methods,” MOS-SIAM Series on Optimization, SIAM, Philadelphia, 2000. doi:10.1137/1.9780898719857
[25]	Z. Ugray, L. Lasdon, J. Plummer, F. Glover, J. Kelly and R. Marti, “Scatter Search and Local NLP Solvers: A Multistart Framework for Global Optimization,” INFORMS Journal on Computing, Vol. 19, No. 3, 2007, pp. 328-340. doi:10.1287/ijoc.1060.0175
[26]	F. Glover, “A Template for Scatter Search and Path Relinking,” In: J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer and D.Snyers, Eds., Artificial Intelligence, Springer, Berlin, Heidelberg, 1998, pp. 13-54.
[27]	D. E. Goldberg, “Genetic Algorithms in Search,” Optimization & Machine Learning, Addison-Wesley, Boston, 1989.
[28]	L. C. W. Dixon and G. P. Szego, “The Global Optimization Problem: An Introduction,” Towards Global Optimisation 2, North-Holland Pub. Co, Amsterdam, 1978, pp. 1-15.