AJCM  Vol.3 No.1 , March 2013
A Derivative-Free Optimization Algorithm Using Sparse Grid Integration
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.
Cite this paper: S. Chen and X. Wang, "A Derivative-Free Optimization Algorithm Using Sparse Grid Integration," American Journal of Computational Mathematics, Vol. 3 No. 1, 2013, pp. 16-26. doi: 10.4236/ajcm.2013.31003.

[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.