Generalisations and improvements of New Q-Newton's method Backtracking

In this paper, we propose a general framework for the algorithm New Q-Newton's method Backtracking, developed in the author's previous work. For a symmetric, square real matrix A, we define minsp(A):=min ||e||=1 ||Ae||. Given a C2 cost function f:ℝmrightarrow ℝ and a real number 0<τ , as well as m+1 fixed real numbers δ 0,ldots ,δ m, we define for each x∈ ℝm with nabla f(x)not= 0 the following quantities: kappa :=min inot= j|δ i-δ j|; A(x):=nabla 2f(x)+δ ||nabla f(x)||τId, where δ is the first element in the sequence δ 0,ldots ,δ m for which minsp(A(x))≥ kappa ||nabla f(x)||τ; e1(x),ldots ,em(x) are an orthonormal basis of ℝm, chosen appropriately; w(x)= the step direction, given by the formula: w(x)=sum i=1mfrac<nabla f(x),ei(x)>||A(x)ei(x)||ei(x); (we can also normalise by w(x)/max 1,||w(x)|| when needed) γ (x)>0 learning rate chosen by Backtracking line search so that Armijo's condition is satisfied: f(x-γ (x)w(x))-f(x)≤ -frac13γ (x)<nabla f(x),w(x)>. The update rule for our algorithm is xmapsto H(x)=x-γ (x)w(x). In New Q-Newton's method Backtracking, the choices are τ =1+α >1 and e1(x),ldots ,em(x)'s are eigenvectors of nabla 2f(x). In this paper, we allow more flexibility and generality, for example τ can be chosen to be <1 or e1(x),ldots ,em(x)'s are not necessarily eigenvectors of nabla 2f(x). New Q-Newton's method Backtracking (as well as Backtracking gradient descent) is a special case, and some versions have flavours of quasi-Newton's methods. Several versions allow good theoretical guarantees. An application to solving systems of polynomial equations is given.