یک الگوریتم جدید ناحیه اطمینان مبتنی بر درونیاب تابع پایه شعاعی

نویسندگان
محمد احمدوند 1
محسن اسماعیل بیگی 2
احمد کمندی 3
فرج الله محمدی یعقوبی 4
1 دانشگاه آزاد اسلامی واحد ملایر
2 دانشگاه ملایر
3 دانشگاه علم و فناوری مازندران
4 دانشگاه آزاد اسلامی واحد همدان
چکیده
ORBIT یک الگوریتم بهینه­ سازی دارای ساختار ناحیه اطمینان بی­ نیاز از مشتق است. در این ساختار به جای استفاده از مدل­ های جایگزین چندجمله­ ای از مدل­ های جایگزین مبتنی بر درونیاب تابع پایه شعاعی استفاده می­ گردد. بنابراین با تعداد کمتری از ارزیابی­ های تابع هدف، قادر خواهیم بود مساله بهینه ­سازی را حل نماییم. در این الگوریتم در هر تکرار، نقاط درونیاب و مقادیر تابع در آنها ذخیره شده و در تکرارهای بعدی مورد استفاده قرار می­ گیرد. با این حال این الگوریتم توجهی به مرتب کردن نقاط درونیاب نمی­ کند. در این مقاله بر اساس دو ایده، یکی مرتب کردن نقاط درونیاب بر حسب مقادیر تابع و دیگری انتخاب نقطه­ ای به عنوان مرکز ناحیه اطمینان که کمترین مقدار تابع را دارد، یک الگوریتم جدید به نام SORT-ORBIT ارائه می ­کنیم. با استفاده از این رویکرد، تعداد دفعات ارزیابی تابع و تعداد تکرار­های الگوریتم ORBIT کاهش می­ یابد. نتایج عددی حاکی از آن است که کارایی الگوریتم جدید به ­طور مشهودی افزایش می­ یابد. برای بررسی عملکرد الگوریتم ارائه شده در این مقاله در مقایسه با الگوریتم اصلی از شاخص کارایی دولان- موری و شاخص داده موری-ویلد استفاده شده است.
کلیدواژه‌ها
الگوریتم ناحیه اطمینان
تابع پایه شعاعی
بهینه سازی نامقید
الگوریتم بی نیاز از مشتق
تغییر مرکز
آزمون همگرایی

عنوان مقاله English

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

نویسندگان English

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
چکیده English

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.

کلیدواژه‌ها English

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.