Performance Analysis of Steepest Descent-Line Search Condition Combinations in Nonlinear Least Squares Fitting of CMM Data
Abstract
This paper presents a benchmarking study on the steepest descent (SD) method considering three different line search conditions including Backtracking (BC), Armijo-Backtracking (ABC) and Goldstein (GC) in nonlinear least squares fitting of measured data obtained from coordinate measuring machine (CMM). Within this scope, five primitive geometries such as circle, square, rectangle, triangle and ellipse were built via 3D printer. Those geometries were then scanned with CMM to acquire their 2D profiles to be fitted. To find best fitting parameters for each geometry, the nonlinear least squares approach along with the above-mentioned optimization method-line search condition combinations were employed. During the fitting process, the total number of function evaluations, when the combination converges to required tolerance, were used as a performance metric of the combination in question. With those data, the performance and data profiles for each combination were created to be able to carry out a reliable performance evaluation. Based on those profiles, it has been seen that the SD-ABC combination is the fastest one. In addition, it is successful on all the geometries while the others are not. For the second fastest combination, the SD-BC combination stands out. However, its successful rate is only 80%, which means it fails on a geometry. On the other hand, the SD-GC combination takes the last place in this study. All those results have shown that the line search conditions have a great contribution to the success and performance of the optimization algorithm being used. Besides, their performance may differ from problem-to-problem. The end-users should consider these facts to find best optimization method-line search condition combination for their problems.
Keywords
steepest descent method line search condition performance profiles data profiles nonlinear least squares fitting optimization
Thanks
The author acknowledges Design and Manufacturing Technologies Research Laboratory, Innovative Technologies Application and Research Center, Suleyman Demirel University where the experimental studies were performed.
References
- Cauchy, A. (1847). Methode generale pour la resolution des systemes d’equations simultanees. Comp. Rend. Sci. Paris, 25(2), 536-538.
- Zhu, L. M., Ding, H., Xiong, Y. L. (2003). A steepest descent algorithm for circularity evaluation. Computer-Aided Design, 35, 255-265.
- Xiao, W., Dunford, W. G., Palmer, P. R., Capel, A. (2007). Application of centered differentiation and steepest descent to maximum power point tracking. IEEE Transactıons on Industrıal Electronıcs, 54, 2539-2549.
- Dam, H. H., Nordholm, S., Low, S. Y., Cantoni, A. (2007). Blind signal separation using steepest descent method. IEEE Transactıons on Sıgnal Processıng, 55, 4198-4207.
- Kalousek, Z. (2017). Steepest descent method with random step lengths. Found Comput Math, 17, 359-422.
- Shirokanev, A. S., Kirsh, D.V., Kupriyanov, A.V. (2016). Applıcatıon of gradıent steepest descent method to the problem of crystal lattice parametric identification. In CEUR Workshop Proceedings, 1638, 393-400.
- Akbarzadeh, V., Lévesque, J. C., Gagné, C., Parizeau, M. (2014). Efficient sensor placement optimization using gradient descent and probabilistic coverage. Sensors, 14, 15525-15552.
- Exl, L., Bance, S., Reichel, F., Schrefl, T., H. Stimming, P., Mauser, N. J. (2014). LaBonte’s method revisited: An effective steepest descent method for micromagnetic energy minimization. Journal of applied physics, 115, 17D118.
- Andrei, N. (2006). An acceleration of gradient descent algorithm with backtracking for unconstrained Optimization. Numer Algor, 42, 63-73.
- Quiroz, E. A. P., Quispe, E. M., Oliveira, P. R. (2008). Steepest descent method with a generalized Armijo search for quasiconvex functions on Riemannian manifolds. J. Math. Anal. Appl., 341, 467-477.
- Samir, C., Absil, P. A., Srivastava, A., Klassen, E. (2012). A gradient-descent method for curve fitting on riemannian manifolds. Found Comput Math, 12, 49-73.
- https://www.desmos.com (Access date:16.05.2021).
- Jia, P. (2017). Fitting a parametric model to a cloud of points via optimization methods. Ph.D. thesis, Syracuse University, New York, USA.
- Nocedal, J., Wright, S. J. (2006). Numerical optimization, 2nd ed., New York, USA: Springer Science & Business Media.
- Dolan, E. D., More, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical programming, 91(2), 201-213.
- More, J. J., Wild, S. M. (2009). Benchmarking derivative-free optimization algorithms. SIAM Journal on Optimization, 20(1), 172-19.
Koordinat Ölçme Makinesi Verilerinin Doğrusal Olmayan En Küçük Kareler Uydurulmasında En Dik İniş-Doğru Boyunca Arama Şartı Kombinasyonlarının Performans Analizi
Abstract
Bu makale koordinat ölçme makinesinden (KÖM) elde edilen verilerin doğrusal olmayan en küçük kareler uydurulmasında Backtracking (BC), Armijo-Backtracking (ABC) ve Goldstein (GC) içeren üç farklı doğru boyunca arama şartlarını dikkate alarak en dik iniş (EDİ) yöntemi üzerine bir kıyaslama çalışması sunmaktadır. Bu kapsamda, daire, kare, dikdörtgen, üçgen ve elips şekillerindeki beş temel geometri 3B yazıcı ile imal edildi. Daha sonra bu geometrilerin uydurulacak 2B profillerini elde etmek için adı geçen geometriler KÖM ile tarandı. Her bir geometriye en iyi uydurma parametresini bulmak için, doğrusal olmayan en küçük kareler yaklaşımı yukarıda bahsedilen optimizasyon yöntemi-doğru boyunca arama şartı kombinasyonları ile birlikte kullanıldı. Uydurma süreci boyunca ilgili kombinasyon istenilen tolerans değerine yakınsadığında ortaya çıkan toplam fonksiyon değerlendirme sayısı kullanılan kombinasyonun bir performans metriği olarak dikkate alındı. Güvenilir bir performans analizi yapabilmek amacıyla bu veriler ile, her bir kombinasyon için performans ve veri profilleri oluşturuldu. Adı geçen profillere dayanarak EDİ-ABC kombinasyonun en hızlı olduğu görüldü. Ek olarak bu kombinasyon diğer kombinasyonların aksine tüm geometrilerde başarılıdır. İkinci en hızlı kombinasyon için EDİ-BC kombinasyonu ortaya çıkmaktadır. Fakat, adı geçen kombinasyonun başarı oranı sadece %80’dir, yani bir geometride başarısız olmaktadır. Öte yandan, EDİ-GC kombinasyonu bu çalışmada son sırayı almaktadır. Tüm bu sonuçlar gösteriyor ki, doğru boyunca arama şartlarının kullanılan optimizasyon yönteminin başarısına ve performansını büyük bir katkısı vardır. Ayrıca bu şartların performansı problemden probleme farklılık gösterebilir. Son kullanıcılar kendi problemleri için en iyi optimizasyon yöntemi-doğru boyunca arama şartı kombinasyonunu bulmak için bu bulguları dikkate almalıdır.
Keywords
En dik iniş metodu Doğru boyunca arama Performans profilleri Veri profilleri Doğrusal olmayan en küçük kareler uydurma Optimizasyon
References
- Cauchy, A. (1847). Methode generale pour la resolution des systemes d’equations simultanees. Comp. Rend. Sci. Paris, 25(2), 536-538.
- Zhu, L. M., Ding, H., Xiong, Y. L. (2003). A steepest descent algorithm for circularity evaluation. Computer-Aided Design, 35, 255-265.
- Xiao, W., Dunford, W. G., Palmer, P. R., Capel, A. (2007). Application of centered differentiation and steepest descent to maximum power point tracking. IEEE Transactıons on Industrıal Electronıcs, 54, 2539-2549.
- Dam, H. H., Nordholm, S., Low, S. Y., Cantoni, A. (2007). Blind signal separation using steepest descent method. IEEE Transactıons on Sıgnal Processıng, 55, 4198-4207.
- Kalousek, Z. (2017). Steepest descent method with random step lengths. Found Comput Math, 17, 359-422.
- Shirokanev, A. S., Kirsh, D.V., Kupriyanov, A.V. (2016). Applıcatıon of gradıent steepest descent method to the problem of crystal lattice parametric identification. In CEUR Workshop Proceedings, 1638, 393-400.
- Akbarzadeh, V., Lévesque, J. C., Gagné, C., Parizeau, M. (2014). Efficient sensor placement optimization using gradient descent and probabilistic coverage. Sensors, 14, 15525-15552.
- Exl, L., Bance, S., Reichel, F., Schrefl, T., H. Stimming, P., Mauser, N. J. (2014). LaBonte’s method revisited: An effective steepest descent method for micromagnetic energy minimization. Journal of applied physics, 115, 17D118.
- Andrei, N. (2006). An acceleration of gradient descent algorithm with backtracking for unconstrained Optimization. Numer Algor, 42, 63-73.
- Quiroz, E. A. P., Quispe, E. M., Oliveira, P. R. (2008). Steepest descent method with a generalized Armijo search for quasiconvex functions on Riemannian manifolds. J. Math. Anal. Appl., 341, 467-477.
- Samir, C., Absil, P. A., Srivastava, A., Klassen, E. (2012). A gradient-descent method for curve fitting on riemannian manifolds. Found Comput Math, 12, 49-73.
- https://www.desmos.com (Access date:16.05.2021).
- Jia, P. (2017). Fitting a parametric model to a cloud of points via optimization methods. Ph.D. thesis, Syracuse University, New York, USA.
- Nocedal, J., Wright, S. J. (2006). Numerical optimization, 2nd ed., New York, USA: Springer Science & Business Media.
- Dolan, E. D., More, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical programming, 91(2), 201-213.
- More, J. J., Wild, S. M. (2009). Benchmarking derivative-free optimization algorithms. SIAM Journal on Optimization, 20(1), 172-19.
Details
| Primary Language | English |
|---|---|
| Subjects | Engineering |
| Journal Section | Articles |
| Authors | |
| Publication Date | November 30, 2021 |
| Published in Issue | Year 2021 Issue: 28 |
