2021/09/23 by Tuyen Trung Truong, Truong, Tuyen Trung
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Algebraic Geometry (math.AG) #Complex Variables (math.CV) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Iterative Methods for Nonlinear Equations #Machine Learning (cs.LG) #Matrix Theory and Algorithms #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2109.11395
openalex publication_date 2021/09/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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:ℝm→ ℝ and a real number 0||A(x)ei(x)||ei(x);(we can also normalise by w(x)/max \1,||w(x)||\ when needed) γ(x)gt;0 learning rate chosen by Backtracking line search so that Armijo's condition is satisfied:f(x-γ(x)w(x))-f(x)≤ -(1)/(3)γ(x). The update rule for our algorithm is x↦ H(x)=x-γ(x)w(x). In New Q-Newton's method Backtracking, the choices are τ=1+α>1 and e1(x),… ,em(x)'s are eigenvectors of ∇ 2f(x). In this paper, we allow more flexibility and generality, for example τ can be chosen to be <1 or e1(x),… ,em(x)'s are not necessarily eigenvectors of ∇ 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.