Back to Nonlinear Equations.

### Trust-Region Methods

A *trust-region version* of Newton's method for nonlinear equations takes the view that the linear model of the function is valid only when the step is not too large, so it places a restriction on the size of the step. That is, if we let \(J(x_k)\) denote the Jacobian matrix and \(p_k\) be the step, then a trust-region method limits \(p_k\) to ensure that the linear model

\[f(x_k) + J(x_k) p_k,\]

is a valid for \(f(x_k + p_k)\).

In a general trust-region method, the Jacobian matrix is replaced by an approximation \(B_k\), and the step is obtained as an approximate solution of the subproblem

\[\min \{ {\|f(x_k) + B_k s\| : \|D_k s \|_2 \leq \Delta_k} \}, \quad\quad(1)\]

where \(D_k\) is a scaling matrix and \(\Delta_k\) is the trust-region radius. The step is accepted if the ratio

\[\rho_k = \frac{\|f(x_k)\| - \|f(x_k + s_k)\|}{\|f(x_k)\| - \|f(x_k) + B_k s_k \|} \,\]

of the actual-to-predicted decrease in \(\|f(x) \|\) is greater than some constant \(\sigma_0\), e.g., 0.0001. If the step is not accepted, the trust-region radius is decreased and the ratio is recomputed. The trust-region radius may also be updated between iterations according to how close the ratio \(\rho_k\) is to its ideal value of 1.

### Line-Search Methods

Given an approximation \(B_k\) to the Jacobian matrix, a *line-search method* obtains a search direction \(d_k\) by solving the system of linear equations

\[B_k d_k =-f(x_k)\]

and then defining the next iterate as \(x_{k+1} = x_k + \alpha_k d_k \,\), where the line search parameter \(\alpha_k > 0\) is chosen by the line-search procedure so that \( \|f(x_{k+1})\| < \|f(x_k)\| \).

When the "approximate" Jacobian is "exact", as in Newton's method, \(d_k\) is a downhill direction 2-norm, so there is certain to be an \(\alpha_k > 0\) such that \(\|f(x_{k+1}) \|_2 < \|f(x_k) \|_2\). This descent property does not necessarily hold for other choices of the approximate Jacobian, so line-search methods are used only when \(B_k\) is either the exact Jacobian or a close approximation to it.

In an ideal line-search Newton method, we would compute the search direction by solving

\[f^\prime(x_k) d_k = -f(x_k)\]

and choose the line-search parameter \(\alpha_k\) to minimize the scalar function \(\phi_\alpha = \| f(x_k + \alpha d_k) \|_2^2.\)

However, since it is usually too time-consuming to find the \(\alpha\) that exactly minimizes \(\phi\), we usually settle for an approximate solution that satisfies the conditions

\[\phi(\alpha_k) \leq \phi(0) + \mu \alpha_k \phi^\prime(0), \quad\mbox{and} \quad |\phi^\prime(\alpha_k)| \leq \eta |\phi^\prime(0)| \]

where \( \mu\) and \(\eta\) are two constants. Typical values are \(\mu = 0.001\) and \(\eta=0.9\).

The first of these conditions ensures that \(\|f(x) \|_2^2\) decreases by a significant amount, while the second condition ensures that we move far enough along the search direction by insisting on a significant reduction in the size of the gradient.

*Updated: October 9, 2013*