Line Searches, Trust Regions, And Convergence Checks

Why Optimization Needs Safeguards

Likelihood algorithms construct a sequence of parameter values intended to increase the log likelihood. Yet a mathematically motivated update is not automatically a safe update: a direction that points uphill near the current estimate can lead to a lower likelihood when followed too far. Curvature approximations, nonlinear response surfaces, and numerical error can all make an unmodified step unreliable.

Line searches and trust regions address this problem in different ways. A line search chooses how far to move along a proposed direction. A trust region instead limits the size of the move while relying on a local approximation to the objective. Neither method replaces convergence checks: a sequence of accepted increases may still be far from a stationary point.

Setup: Let \(\ell(\theta)\) be the log likelihood for a parameter vector \(\theta\), defined on an admissible parameter space. At a current value \(\theta_k\), write \(g_k=\nabla\ell(\theta_k)\) for the score vector and \(d_k\) for a proposed search direction. A trial update has the form \(\theta_k+t d_k\), where \(t>0\) is the step length. The trial must remain in the admissible parameter space.

The score gives the local rate of change in the log likelihood. In particular, the directional derivative along \(d_k\) is \(g_k^\mathsf{T}d_k\). A direction with \(g_k^\mathsf{T}d_k>0\) is an ascent direction: sufficiently small positive steps increase the log likelihood, provided the objective is differentiable in a neighborhood of the current value. This local statement does not guarantee that a large step will increase it.

Step Halving and Backtracking Line Searches

A basic safeguard is step halving. Try the full update first, then successively halve the step length until the trial value increases the log likelihood. More generally, backtracking uses a factor \(\beta\) with \(0<\beta<1\), testing \(t=1,\beta,\beta^2,\ldots\). The common choice \(\beta=1/2\) gives step halving.

A stricter version is the Armijo sufficient-increase condition. It requires the actual increase to be at least a chosen fraction \(c\) of the increase predicted by the local directional derivative, where \(0<c<1\):

\ell(\theta_k+t d_k)\ \geq\ \ell(\theta_k)+c\,t\,g_k^\mathsf{T}d_k.

The condition is meaningful when \(g_k^\mathsf{T}d_k>0\). It does not demand that the local linear approximation be exact; it asks for a positive increase commensurate with the direction's initial uphill slope. A simple monotonicity search accepts any trial with \(\ell(\theta_k+t d_k)>\ell(\theta_k)\), while the Armijo rule may reject a small but technically positive increase.

Worked Example: Step Halving After a Decreasing Full Step

Suppose a hypothetical one-parameter log likelihood is \(\ell(\theta)=2\theta-\theta^2\). At \(\theta_0=0\), the score is \(g_0=2\). An algorithm proposes \(d_0=3\), an ascent direction because \(g_0d_0=6>0\). Test the full step and then halve it.

The current log likelihood is \(\ell(0)=0\). The full step gives \(\theta_0+d_0=3\), with \[ \ell(3)=2(3)-3^2=6-9=-3. \] This decreases the objective, so reject it. The half-step gives \(\theta=0+(1/2)(3)=1.5\), with \[ \ell(1.5)=2(1.5)-(1.5)^2=3-2.25=0.75. \] Since \(0.75>0\), the monotonicity rule accepts the half-step. The directional derivative was positive, but the full step was too long.

Worked Example: Applying the Armijo Rule

Use the same hypothetical log likelihood, starting value, score, and direction as above. Set \(c=0.1\) and halve the step length after each rejection. The current value is \(\ell(0)=0\), and \(g_0d_0=6\), so the Armijo threshold at step length \(t\) is \(0+0.1t(6)=0.6t\).

At \(t=1\), the trial value is \(\ell(3)=-3\), below the required \(0.6\), so reject. At \(t=1/2\), the trial value is \(\ell(1.5)=0.75\), below the required \(0.3\)? No: \(0.75\geq0.3\), so this step satisfies Armijo and is accepted. The rule stops at the half-step; it does not continue to smaller steps once a trial passes.

This calculation also illustrates why the acceptance rule must be applied as written: compare the trial objective with the threshold for that same \(t\). The Armijo test is stronger than merely requiring an increase, but in this example the half-step passes both rules.

If repeated backtracking fails, first check that the direction is genuinely an ascent direction. If \(g_k^\mathsf{T}d_k\leq0\), shrinking the step cannot generally produce the desired local increase. The direction or the local approximation used to construct it may need attention. If the direction is an ascent direction but the search still fails, possible causes include an invalid parameter value along the path or numerical problems evaluating the likelihood.

Trust Regions: Limiting the Local Step

A trust-region method builds a local approximation to the log likelihood and chooses a step within a region where that approximation is treated as informative. A common quadratic model is

m_k(s)=\ell(\theta_k)+g_k^\mathsf{T}s+\tfrac12 s^\mathsf{T}B_k s, \qquad \|s\|_k\leq\Delta_k.

Here \(B_k\) is a curvature matrix used in the local model, \(\|\cdot\|_k\) is a chosen norm that can account for parameter scaling, and \(\Delta_k>0\) is the trust-region radius. The method selects a step \(s_k\) within this region, often by approximately maximizing \(m_k(s)\) subject to the radius constraint. The constraint prevents the algorithm from relying on a local approximation over an arbitrarily large move.

The model's predicted improvement and the actual improvement can be compared using their ratio:

\operatorname{pred}_k=m_k(s_k)-m_k(0), \qquad \operatorname{ared}_k=\ell(\theta_k+s_k)-\ell(\theta_k), \qquad \rho_k=\frac{\operatorname{ared}_k}{\operatorname{pred}_k}.

This ratio is used when \(\operatorname{pred}_k>0\). A small or negative ratio means the actual likelihood did not match the model's prediction well, so the step may be rejected and the radius reduced. A ratio close to one means prediction and outcome agree; when the step also reaches the boundary, the radius may be increased. Exact thresholds and radius adjustments are implementation choices. A rejected step leaves the current parameter value unchanged.

Worked Example: Evaluating a Trust-Region Step

Consider the hypothetical log likelihood \(\ell(\theta_1,\theta_2)=-(\theta_1-1)^2-4(\theta_2-1)^2\), starting from \(\theta_k=(0,0)\). Its value is \(-5\), its score is \((2,8)^\mathsf{T}\), and its exact quadratic model has curvature matrix \(B_k=\operatorname{diag}(-2,-8)\). Suppose the trust-region radius is \(\Delta_k=0.5\) under the Euclidean norm, and the proposed step is \(s_k=(0.3,0.4)^\mathsf{T}\).

The step is on the boundary because \(\|s_k\|=\sqrt{0.3^2+0.4^2}=0.5\). Its predicted improvement is \[ g_k^\mathsf{T}s_k+\tfrac12s_k^\mathsf{T}B_ks_k = (2)(0.3)+(8)(0.4)-0.3^2-4(0.4^2) =3.8-0.73=3.07. \] The updated parameter is \((0.3,0.4)\), giving \[ \ell(0.3,0.4)=-(0.3-1)^2-4(0.4-1)^2 =-0.49-1.44=-1.93. \] Thus the actual improvement is \(-1.93-(-5)=3.07\), and \(\rho_k=3.07/3.07=1\). The model predicts this exact quadratic objective perfectly. The step should be accepted; because it reaches the boundary and the ratio is high, a typical method would consider enlarging the radius.

Convergence Requires More Than One Check

An optimizer should not declare success merely because an update was accepted. At an interior stationary point, the score vector is zero. In computation, convergence is assessed using tolerances rather than exact equality, and it is prudent to examine several complementary diagnostics:

Objective change: Is the increase in log likelihood small relative to its scale?
Score norm: Is the score vector small, using a suitable scaling for its components?
Parameter-step size: Is the latest change in parameters small relative to their scales?

For example, an implementation may monitor \(|\ell(\theta_{k+1})-\ell(\theta_k)|/(1+|\ell(\theta_k)|)\), a scaled norm of \(g_{k+1}\), and a scaled norm of \(\theta_{k+1}-\theta_k\). The particular norms and tolerances depend on parameter units, numerical precision, and the application. Scaling matters: a change of \(0.01\) can be negligible for a parameter measured in thousands but substantial for one naturally near \(0.001\).

A small objective change alone is weak evidence of convergence. It can occur because the algorithm took a tiny step, even when the score remains appreciable. Likewise, a small parameter step may result from a restrictive trust region or repeated backtracking. Conversely, a modest score norm does not ensure that a particular stopping tolerance has been met if parameters have very different scales. Record the stopping criteria and the diagnostics, rather than reporting only that the software “converged.”

Worked Example: Distinguishing a Small Objective Change From Convergence

For the hypothetical log likelihood \(\ell(\theta)=-(\theta-1)^2\), compare an update from \(\theta=0.90\) to \(\theta=0.99\), followed by an update to \(\theta=0.999\). The score is \(g(\theta)=-2(\theta-1)\).

At \(\theta=0.90\), \(\ell=-0.01\); at \(\theta=0.99\), \(\ell=-0.0001\). The increase is \(0.0099\), the step size is \(0.09\), and the score at the new value is \(0.02\). For the next update, \(\ell(0.999)=-0.000001\), so the increase is \(0.000099\), the step size is \(0.009\), and the new score is \(0.002\).

Suppose, only for illustration, that the objective-change tolerance is \(0.01\), the score-norm tolerance is \(0.005\), and the step-size tolerance is \(0.01(1+|\theta|)\). After the first update, the objective increase is below its tolerance, but the score \(0.02\) exceeds its tolerance and the step \(0.09\) exceeds its tolerance of \(0.0199\). That update alone should not be taken as evidence of convergence. After the second update, the increase \(0.000099\), score \(0.002\), and step \(0.009\) are each below their respective tolerances (the step tolerance is \(0.01999\)). These checks jointly support stopping under the stated illustrative rules.

Practical Interpretation and Common Pitfalls

These safeguards matter because optimization is numerical, not simply symbolic. They make the path to a maximum more robust when a likelihood surface is nonlinear or a proposed local model is imperfect. However, an accepted step or a small score establishes neither that the global maximum has been found nor that the statistical model is correctly specified. Optimization diagnostics concern the numerical search at the values examined.

Mistake: “The direction is uphill, so the full step must improve the likelihood.” A positive directional derivative guarantees an increase only for sufficiently small steps under the local differentiability condition. The worked step-halving example shows a full step can decrease the objective.
Mistake: “The log likelihood barely changed, so the algorithm converged.” A small change can result from a tiny step while the score remains too large. Check the score and parameter-step size as well.
Mistake: “A trust-region step was rejected, so the current estimate is invalid.” Rejection means the proposed move was not sufficiently supported by the local model. The method can retain the current value, reduce the radius, and try a more cautious step.
Mistake: “A high trust-region ratio proves the likelihood is globally maximized.” The ratio measures local predictive accuracy for one proposed step; it is not a global optimality certificate.

Key takeaway: Use a line search to control distance along a direction, or a trust region to limit the step while assessing a local model. Then judge stopping with objective change, score norm, and parameter-step size together, using scales and tolerances suited to the parameters.

Check Your Understanding

Answer each question using the definitions and safeguards above.

What does a positive value of \(g_k^\mathsf{T}d_k\) establish, and what does it not establish about a full step?
For an Armijo search, why must the trial objective be compared with a threshold that depends on the tested step length?
What does a trust-region ratio near one indicate? What additional fact would make enlarging the radius a typical choice?
Explain how an optimizer could show a very small objective change while still having a score norm that argues against convergence.
Why should parameter-step diagnostics account for parameter scales?