1 Non-linear Optimization: Newton — Gauss Method
The Newton–Gauss method is a second-order optimization technique for quadratic functions, utilizing a linear approximation of the optimized function at each step. It is applied to solve nonlinear least squares problems, effectively reducing them to a sequence of linear least squares problems.
11 Gradient and Hessian of the Loss Function
Given the quadratic loss function
we can express the gradient and Hessian of the function in terms of the model’s parameters:
gradient is the column vector:
The gradient components are
The Hessian components are
12 Linear Approximation of the Algorithm
Apply a Taylor series expansion of the algorithm up to the linear term near the current approximation of the parameter vector :
is constant, and the linear term is the sum of the partial derivatives of with respect to the parameters . The higher-order terms are negligible and will be omitted below.
Differentiate the linear approximation of the algorithm:
The components of the sum depending on was zeroed out in the differentiation over .
Substitute the obtained derivative into the expression for the Hessian:
The linear term will be zeroed out in the second differentiation and will not enter the Hessian.
13 Matrix Formulation of the Optimization Step
Introduce the matrix of first partial derivatives and the algorithm’s response vector at the current approximation of the parameters :
matrix and vector depend on the point of expansion and are recalculated at each optimization step.
The gradient and Hessian (at each step) are calculated using the matrix :
Newton — Rafson method is a second-order optimization technique that provides fast convergence. Newton–Gauss method is an approximate second-order method that uses a linear approximation of the optimized function at each step.
The optimization step of the Newton — Rafson method is also expressed in terms of the matrix :
The nonlinear optimization problem is reduced to a sequence of linear problems: at each iteration, a linear expansion of the function is made, matrices are calculated, and a (new) system of linear equations is solved.
The optimization step vector at each iteration can be determined from the linear system in any of these formulations:
The method is a second-order approximation method, providing fast convergence and slightly inferior accuracy compared to the Newton–Raphson method.