FPGA-based acceleration of Davidon-Fletcher-Powell quasi-Newton optimization method

Abstract

Quasi-Newton methods are the most widely used methods to find local maxima and minima of functions in various engineering practices. However, they involve a large amount of matrix and vector operations, which are computationally intensive and require a long processing time. Recently, with the increasing density and arithmetic cores, field programmable gate array (FPGA) has become an attractive alternative to the acceleration of scientific computation. This paper aims to accelerate Davidon-Fletcher-Powell quasi-Newton (DFP-QN) method by proposing a customized and pipelined hardware implementation on FPGAs. Experimental results demonstrate that compared with a software implementation, a speed-up of up to 17 times can be achieved by the proposed hardware implementation.

Keywords

quasi-Newton method / hardware acceleration / field programmable gate array

References

[1] Pallaschke D, Rolewicz S. Foundations of Mathematical Optimization[M], 2009, Germany: Springer.

[2] Lewis A S, Overton M L. Nonsmooth optimization via quasi-Newton methods[J]. Mathematical Programming, 2013, 141(1): 135-163.

[3] Mokhtari A, Ribeiro A. A dual stochastic DFP algorithm for optimal resource allocation in wireless systems[C]. 2013 IEEE 14th Workshop on Signal Processing Advances in Wireless Communications, 2013.

[4] Kuwabara S, Kohira Y, Takashima Y. An effective overlap removable objective for analytical placement[J]. IEICETransaction on Fundamentals of Electronics, Communications and Computer Sciences, 2013, 6: 1348-1356.

[5] Alaei H K, Yazdizadeh A, Aliabadi A. Nonlinear predictive controller design for load frequency control in power system using quasi Newton optimization approach[C]. 2013 IEEE International Conference on Control Applications, 2013.

[6] Ninomiya H. Robust training of multilayer neural networks using parameterized online quasi-Newton algorithm [C]. 2011 Fourth International Conference on Machine Learning and Applications, 2011.

[7] De Matos G M, Neto H C. Memory optimized architecture for efficient Guass-Jordan matrix inversion[C]. 2007 3rd Southern Conference on Programmable Logic, 2007.

[8] Boland D, Constantinides G A. An FPGA-based implementation of the MINRES algorithm[C]. 2008 International Conference on Field Programmable Logic and Applications, 2008.

[9] Roldao A, Constantinides G A. A high throughput FPGAbased floating point conjugate gradient implementation for dense matrices[J]. ACM Transactions on Reconfigurable Technology and Systems, 2010.

[10] Munoz D M, Llanos C H, dos Coelho L S, et al. Comparison between two FPGA implementation of the particle swarm optimization algorithm for highperformance embedded applications[C]. 2010 IEEE Fifth International Conference on Bio-Inspired Computing:^Theories and Applications, 2010.

[11] Christou I T. Quantitative Methods in Supply Chain Management: Models and Algorithms[M], 2011, London, UK: Springer-Verlag.

[12] Liu Q, Qin Sishi. A DFP-neural networks algorithm for analysis of power system harmonics[C]. 2010 Asia-Pacific Power and Energy Engineering Conference, 2010.

[13] Press W H, Teukolsky S A, Vetterling W T, et al. Numerical Recipes: The Art of Scientific Computing[M], 2007, 3 New York, USA: Cambridge Press Publisher.

[14] Zhao Y, Ji H, Chen Zhonghui. Noisy chaotic neural network for resource allocation in high-speed train OFDMA system[J]. Transactions of Tianjin University, 2014, 20(5): 368-374.

[15] Wu Q, Zhao X, Zhao Quan. Application of artificial neural network in the research of the Bohai Bay eutrophication[J]. Transactions of Tianjin University, 2007, 13(6): 437-440.