A new trust-region algorithm based on radial basis function interpolation

Authors
Mohammad Ahmadvand 1
Mohsen Esmaeilbeigi 2
Ahmad Kamandi 3
Farajollah Mohammadi Yaghoobi 4
1 Islamic Azad University Malayer branch
2 Malayer University
3 University of Science and Technology of Mazandaran
4 Hamedan Branch, Islamic Azad University
Abstract
Optimization using radial basis functions as an interpolation tool in trust-region (ORBIT), is a derivative-free framework based on fully linear models to solve unconstrained local optimization, especially when the function evaluations are computationally expensive. This algorithm stores the interpolation points and function values to using at subsequent iterations. Despite the comparatively advanced management used for interpolation points, we maintain that ORBIT ignores sorting the interpolation points based on the function values. In this paper, we propose an improved version SORT-ORBIT by sorting the interpolation points and selecting a point as the trust-region center in which the objective function reaches its minimum value. Numerical results indicate the efficiency of the improved version compared with the original version. In addition, to estimate high-accuracy solutions, we equip the ORBIT with a new gradient-free convergence test.
Keywords
Trust-region algorithm
Radial basis function
Unconstrained optimization
Derivative-free algorithm
Center changing
Convergence test
1. Andrei, N., ''An unconstrained optimization test functions collection'', Adv Model. Optim, vol. 10, no. 1 (2008) 147-161

2. Armijo, L‎., ''Minimization of functions having Lipschitz continuous first partial derivatives‎'', ‎Pacific J‎. ‎Math‎.‎,‎‎vol. 16 (1966) 11-30‎.

3. Bertsekas, D. P., ''Nonlinear Programming'', Massachusetts Institute of Technology, Athena Scientific, Belmont, Massachusetts, second edition (1999).

4. Björkman, M., Holmström, K., ''Global optimization of costly nonconvex functions using radial basis functions'', Optim. Eng., vol. 1 (2000) 373-397.

5. Buhmann, M. D., ''Radial Basis Functions'', Cambridge University Press New York, NY, USA (2003).

6. Conn, A. R., Scheinberg, K., Toint, Ph. L., ''Recent progress in unconstrained nonlinear optimization without derivatives'', Math. Program., vol. 79 (1997) 345-397.

7.‎ Conn‎, ‎A‎. ‎R‎., ‎Scheinberg, K‎.,‎Vicente‎, L‎.‎ N‎.,‎ ''Global convergence of general derivative-free trust-region algorithms to first and second order critical points‎'', ‎SIAM J‎.‎ Optim.‎, ‎vol. 20‎ ‎(2009) 387-415‎.

8.‎ Dolan‎, E‎.,‎‎ More'‎, J‎. ‎J‎.,‎ ''Benchmarking optimization software with performance profiles'', Math‎. ‎Program.‎, ‎vol. 91 ‎(2002). ‎201-213‎.

9. Elster, C., Neumaier, A., ''A grid algorithm for bound constrained optimization of noisy function'', IMA J. Numer. Anal., vol. 15 (1995) 585- 608.

10. Günther, C.,Tammer, C., ''Relationships between constrained and unconstrained multi-objective optimization and application in location theory'', Math. Meth. Oper. Res., vol. 84, no. 2 (2016) 359-387.

11. Gutmann, H. M., ''A radial basis function method for global optimization'', J. Global. Optim., vol. 19 (2001) 201-227.

12. More', J., Wild, S. M., ''Benchmarking derivative-free optimization algorithms'', SIAM J. Optim., vol. 20, no. 1 (2009) 172-191.

13. Oeuvray‎, R‎., ‎‎Bierlaire‎, ‎M‎., ''A new derivative-free algorithm for the medical image registration problem''‎, ‎Int‎.‎ J‎. ‎Modelling and Simulation.‎, vol. 27 (2007) ‎115-124‎.

14. Powell, M. J. D., ''A new algorithm for unconstrained optimization'', in: Rosen, J. B., Mangassarian, O.L., Ritter, K., editors, Nonlinear Programming, Academic Press, New York, (1970) 31-66.

15. Powell, M. J. D.,‎‎ ''The NEWUOA software for unconstrained optimization without derivatives''‎.‎ In ‎Di Pillo, G‎.,‎ Roma‎, M‎., ‎editors‎, ‎Large-Scale Nonlinear Optimization‎, ‎Springer‎, (2006)‎ 255-297‎.

16. Powell, M. J. D.,‎‎ ''UOBYQA‎‎unconstrained optimization by quadratic approximation‎'', ‎Math‎.‎ Program.‎, ‎vol. 92 ‎(2002) 555-582‎.

17. Regis, R.G., Shoemaker, C. A., ''A stochastic radial basis function method for the global optimization of expensive functions'', INFORMS J. Comput., vol. 19 (2007) 497-509.

18. Winfield, D., ''Function minimization by interpolation in a data table, J. Inst. Math. Appl., vol. 12 (1973) 339-347.

19. Wild, S. M., Regis, R. G., Shoemaker, C. A., ''Optimization by radial basis function interpolation in trust-region'', SIAM J. Sci Comput., vol. 30, no. 6 (2008) 3197-3219.

20. Wild, S. M., Shoemaker, C. A., ''Global convergence of radial basis function trust region derivative-free algorithms''. SIAM J. Optim, vol. 21, no. 3 (2011) 761-781.