FPGA-based Acceleration of Davidon-Fletcher-Powell Quasi-Newton Optimization Method

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.

Quasi-Newton Method for Optimal Blank Allowance Balancing

A balancing technique for casting or forging parts to be machined is presented in this paper.It allows an optimal part setup to make sure that no shortage of material(undercut)will occur during machining.Particularly in the heavy part in- dustry,where the resulting casting size and shape may deviate from expectations,the balancing process discovers whether or not the design model is totally enclosed in the actual part to be machined.The alignment is an iterative process involving nonlinear con- strained optimization,which forces data points to lie outside the nominal model under a specific order of priority.Newton methods for non-linear numerical minimization are rarely applied to this problem because of the high cost of computing.In this paper, Newton methods are applied to the balancing of blank part.The aforesaid algorithm is demonstrated in term of a marine propeller blade,and result shows that The Newton methods are more efficient and accurate than those implemented in past research and have distinct advantages compared to the registration methods widely used today.

OPTIMAL MOTION PLANNING FOR A RIGID SPACECRAFT WITH TWO MOMENTUM WHEELS USING QUASI-NEWTON METHOD

An optimal motion planning scheme based on the quasi-Newton method is proposed for a rigid spacecraft with two momentum wheels. A cost functional is introduced to incorporate the control energy, the final state errors and the constraints on states. The motion planning for determining control inputs to minimize the cost functional is formulated as a nonlinear optimal control problem. Using the control parametrization, one can transform the infinite dimensional optimal control problem to a finite dimensional one that is solved via the quasi-Newton methods for a feasible trajectory which satisfies the nonholonomic constraint. The optimal motion planning scheme was applied to a rigid spacecraft with two momentum wheels. The simulation results show the effectiveness of the proposed optimal motion planning scheme.

An Improved Quasi-Newton Method for Unconstrained Optimization

We present an improved method. If we assume that the objective function is twice continuously differentiable and uniformly convex, we discuss global and superlinear convergence of the improved quasi-Newton method.

A Study of BCI Signal Pattern Recognition by Using Quasi-Newton-SVM Method

The recognition of electroencephalogram (EEG) signals is the key of brain computer interface (BCI). Aimed at the problem that the recognition rate of EEG by using support vector machine (SVM) is low in BCI, based on the assumption that a well-defined physiological signal which also has a smooth form "hides" inside the noisy EEG signal, a Quasi-Newton-SVM recognition method based on Quasi-Newton method and SVM algorithm was presented. Firstly, the EEG signals were preprocessed by Quasi-Newton method and got the signals which were fit for SVM. Secondly, the preprocessed signals were classified by SVM method. The present simulation results indicated the Quasi-Newton-SVM approach improved the recognition rate compared with using SVM method; we also discussed the relationship between the artificial smooth signals and the classification errors.

BFGS quasi-Newton location algorithm using TDOAs and GROAs

With the emergence of location-based applications in various fields, the higher accuracy of positioning is demanded. By utilizing the time differences of arrival （TDOAs） and gain ratios of arrival （GROAs）, an efficient algorithm for estimating the position is proposed, which exploits the Broyden-Fletcher-Goldfarb-Shanno （BFGS） quasi-Newton method to solve nonlinear equations at the source location under the additive measurement error. Although the accuracy of two-step weighted-least-square （WLS） method based on TDOAs and GROAs is very high, this method has a high computational complexity. While the proposed approach can achieve the same accuracy and bias with the lower computational complexity when the signal-to-noise ratio （SNR） is high, especially it can achieve better accuracy and smaller bias at a lower SNR. The proposed algorithm can be applied to the actual environment due to its real-time property and good robust performance. Simulation results show that with a good initial guess to begin with, the proposed estimator converges to the true solution and achieves the Cramer-Rao lower bound （CRLB） accuracy for both near-field and far-field sources.

Structural Stress-Fatigue Life Curve Improvement of Spot Welding Based on Quasi‑Newton Method

ΔF-N curves are usually used to predict the fatigue life of spot welding in engineering,but they are time-consuming and laborious and not universal.For the purpose of predicting the fatigue life of spot welding accurately and efficiently,tensile-shear fatigue tests were conducted to obtain the fatigue life of spot-welded specimens with different sheet thicknesses combinations.These specimens were simulated by using the finite element method,and the structural stress was theoretically calculated.In the double logarithmic coordinate system,the structural stress-fatigue life(S-N)curve of spot welding was fitted by the least-squares method,based on the quasi-Newton method.The square of the correlation coefficient of the S-N curve was taken as the optimization objective,with the correction coefficients of force,bending moment,spot welding diameter,and sheet thickness as the variables.During the optimization process,three different ways were utilized to get three optimized spot welding S-N curves,which are suitable for different situations.The results show that the fitting effect of the S-N curve is improved,the data points are more compact,and the optimization effect is significant.These S-N curves can be used to predict the fatigue life,which provide the basis for practical engineering application.

An Overview of Stochastic Quasi-Newton Methods for Large-Scale Machine Learning

Numerous intriguing optimization problems arise as a result of the advancement of machine learning.The stochastic first-ordermethod is the predominant choicefor those problems due to its high efficiency.However,the negative effects of noisy gradient estimates and high nonlinearity of the loss function result in a slow convergence rate.Second-order algorithms have their typical advantages in dealing with highly nonlinear and ill-conditioning problems.This paper provides a review on recent developments in stochastic variants of quasi-Newton methods,which construct the Hessian approximations using only gradient information.We concentrate on BFGS-based methods in stochastic settings and highlight the algorithmic improvements that enable the algorithm to work in various scenarios.Future research on stochastic quasi-Newton methods should focus on enhancing its applicability,lowering the computational and storage costs,and improving the convergence rate.

基于非结构网格的三维大地电磁法有限内存拟牛顿反演研究（英文）

相比于传统的基于结构化网格的三维大地电磁法正反演算法,基于非结构网格的算法可以更高精度地模拟复杂的地下电性结构,克服了传统的基于规则网格算法提高计算精度代价高和难以适应实现直接带地形反演的缺陷。结合基于非结构网格的有限元法,本文采用有限内存拟牛顿(L-BFGS)方法,进行三维大地电磁法反演。该方法不需要显式计算海森矩阵,只需要存储约2×M×m个数据(其中M为反演单元个数,m为值较小的数,本文设为5),因此极大地减少内存需求,在第一次迭代后,近似海森矩阵的逆已经逼近了真实值,牛顿步长(设定值为1)即可保证充分下降,每次迭代只需要计算一次目标函数和梯度,提高了计算效率,适合于大规模大地电磁法数据反演。我们分别对带地形和不带地形的理论数据进行反演,结果与实际模型吻合较好,验证了基于非结构有限元法和有限内存拟牛顿法对地形和地下复杂目标体进行反演的有效性。

A QP-FREE AND SUPERLINEARLY CONVERGENT ALGORITHM FOR INEQUALITY CONSTRAINED OPTIMIZATIONS

In this paper, a new mixed quasi-Newton method for inequality constrained optimization problems is proposed. The feature of the method is that only the systems of linear equations are solved in each iteration, other than the quadratic programming, which decrease the amount of computations and is also efficient for large scale problem. Under some mild assumptions without the strict complementary condition., the method is globally and superlinearly convergent.

A CLASS OF FACTORIZED QUASI-NEWTON METHODS FOR NONLINEAR LEAST SQUARES PROBLEMS

This paper gives a class of descent methods for nonlinear least squares solution. A class of updating formulae is obtained by using generalized inverse matrices. These formulae generate an approximation to the second part of the Hessian matrix of the objective function, and are updated in such a way that the resulting approximation to the whole Hessian matrix is the convex class of Broyden-like up-dating formulae. It is proved that the proposed updating formulae are invariant under linear transformation and that the class of factorized quasi-Newton methods are locally and superlinearly convergent. Numerical results are presented and show that the proposed methods are promising.

Inverse problem of elastica of a variable-arc-length beam subjected to a concentrated load

An inverse problem of elastica of a variable-arclength beam subjected to a concentrated load is investigated. The beam is fixed at one end, and can slide freely over a hinge support at the other end. The inverse problem is to determine the value of the load when the deflection of the action point of the load is given. Based on the elasitca equations and the elliptic integrals, a set of nonlinear equations for the inverse problem are derived, and an analytical solution by means of iterations and Quasi-Newton method is presented. From the results, the relationship between the loads and deflections of the loading point is obtained.

Global Convergence of the Broyden's Class of Quasi-Newton Methods with Nonmonotone Linesearch

Abstract In this paper, the Broyden class of quasi-Newton methods for unconstrained optimization is investigated. Non-monotone linesearch procedure is introduced, which is combined with the Broyden's class. Under the convexity assumption on objective function, the global convergence of the Broyden's class is proved.

Global convergence of quasi-Newton methods for unconstrained optimization

The convergence of quasi-Newton methods for unconstrained optimization has at-tracted much attention. Powell proved a global convergence result for the BFGS algorithmusing inexact linesearch which satisfies the Wolfe conditions. Byrd, Nocedal and Yuanextended this result to the convex Broyden class of quasi-Newton methods except the DFPmethod. However, the global convergence of the DFP method, the first quasi-Newtonmethod, using the same linesearch strategy, is still an open question (see ref. [2]).

A SELF-ADAPTIVE ALGORITHM FOR NONLINEAR LEAST SQUARES WITH LINEAR CONSTRAINTS

An algorithm for solving nonlinear least squares problems with general linear inequality constraints is described.At each step,the problem is reduced to an unconstrained linear least squares problem in a subs pace defined by the active constraints,which is solved using the quasi-Newton method.The major update formula is similar to the one given by Dennis,Gay and Welsch (1981).In this paper,we state the detailed implement of the algorithm,such as the choice of active set,the solution of subproblem and the avoidance of zigzagging.We also prove the globally convergent property of the algorithm.

IDENTIFICATION OF TIME-VARIANT CONTINUOUS SYSTEM BY A QUASI-NEWTON METHOD

A quasi-Newton method (QNM) for solving an unconstrained optimization problem in infinite dimensional spaces is presented in this paper. We apply the QNM algorithm to an identification problem for a nonlinear system of differential equations, that is, to identify the parameter vector q = q(t) appearing in the following system of differential equations, based on the measurement of the state , where is a measurement operator. We give two examples to show the algorithm.

QUASI-NEWTON WAVEFORM RELAXATION BASED ON ENERGY METHOD

A quasi-Newton waveform relaxation （WR） algorithm for semi-linear reaction-diffusion equations is presented at first in this paper. Using the idea of energy estimate, a general proof method for convergence of the continuous case and the discrete case of quasi-Newton WR is given, which appears to be the superlinear rate. The semi-linear wave equation and semi-linear coupled equations can similarly be solved by quasi-Newton WR algorithm and be proved as convergent with the energy inequalities. Finally several parallel numerical experiments are implemented to confirm the effectiveness of the above theories.

SOURCE TERM IDENTIFICATION WITH DISCONTINUOUS DUAL RECIPROCITY A PPROXIM ATION AND QUASI-NEWTON METHOD FROM BOUNDARY OBSERVATIONS

This paper deals with discontinuous dual reciprocity boundary element method for solving an inverse source problem.The aim of this work is to determine the source term in elliptic equations for nonhomogenous anisotropic media,where some additional boundary measurements are required.An equivalent formulation to the primary inverse problem is established based on the minimization of a functional cost,where a regularization term is employed to eliminate the oscillations of the noisy data.Moreover,an efficient algorithm is presented and tested for some numerical examples.

Basins of Attraction in the Copenhagen Problem Where the Primaries Are Magnetic Dipoles

We deal with the Copenhagen problem where the two big bodies of equal masses are also magnetic dipoles and we study some aspects of the dynamics of a charged particle which moves in the electromagnetic field produced by the primaries. We investigate the equilibrium positions of the particle and their parametric variations, as well as the basins of attraction for various numerical methods and various values of the parameter λ.

A QUASI-NEWTON METHOD IN INFINITE-DIMENSIONAL SPACES AND ITS APPLICATION FOR SOLVING A PARABOLIC INVERSE PROBLEM

A Quasi-Newton method in Infinite-dimensional Spaces (QNIS) for solving operator equations is presellted and the convergence of a sequence generated by QNIS is also proved in the paper. Next, we suggest a finite-dimensional implementation of QNIS and prove that the sequence defined by the finite-dimensional algorithm converges to the root of the original operator equation providing that the later exists and that the Frechet derivative of the governing operator is invertible. Finally, we apply QNIS to an inverse problem for a parabolic differential equation to illustrate the efficiency of the finite-dimensional algorithm.