Dogleg Trust-Region Step

The dogleg method computes an approximate solution to the trust-region subproblem by restricting the search to a piecewise linear path. This path connects the origin, the Cauchy point (the minimizer along the steepest descent direction), and the unconstrained Newton point.

Worked Example

Consider the objective function f(x, y) = 0.5 * (x² + 4y²). At the point x=1, y=1, the gradient is g = (1, 4) and the Hessian is H = diag(1, 4). We want to find the trust-region step with a trust radius of 1.

1. Compute the unconstrained Newton step pN = -H⁻¹g: pN = (-1, -1) ||pN|| = sqrt(1² + 1²) ≈ 1.414 2. Compute the Cauchy step pU (steepest descent to model minimum): pU = - (g^T g) / (g^T H g) * g g^T g = 1² + 4² = 17 g^T H g = 1²*1 + 4²*4 = 1 + 64 = 65 pU = - (17 / 65) * (1, 4) ≈ (-0.2615, -1.0462) ||pU|| = (17 / 65) * sqrt(17) ≈ 1.078 3. Compare step lengths with Trust Radius (Delta = 1): Since ||pN|| > 1 and ||pU|| > 1, the step is restricted by the Cauchy boundary. p = (Delta / ||pU||) * pU = (1 / 1.0783...) * pU p ≈ (-0.2425, -0.9701)

Experiment

Use the module controls to explore how the step choice changes with the trust radius and the current point.

Set Point x to 1, Point y to 1, and Trust radius to 2. Notice that the step chosen is exactly the Newton point since it fits inside the large trust region.
Change the Trust radius to 1. The Newton point is now outside the region. The Cauchy point is also slightly outside, so the step is scaled back along the steepest descent direction, landing on the Cauchy boundary.
Set Point x to 0 and Point y to 0. At this stationary point, the gradient is zero, so the step is exactly zero regardless of the trust radius.

Limitations

The standard dogleg method assumes the Hessian matrix is positive definite. If the Hessian has negative eigenvalues (as can happen in non-convex optimization), the Newton step might point towards a saddle point or a maximum, and the dogleg path becomes undefined or inappropriate. In such cases, variations like the double-dogleg or subspace minimization methods are required. Additionally, on non-quadratic functions, the predicted reduction may not perfectly match the actual reduction, unlike this exact quadratic model.

References

The calculation of the piecewise dogleg path is defined by standard nonlinear optimization texts.

SciPy Documentation: minimize(method='dogleg') - Describes the dogleg optimization method and its implementation.

Dogleg Trust-Region Step