2 %> Algorithm 12.2: Dogleg method to find an approximation of the trust region subproblem. Implementation of algorithm 12.2 of \cite Bier15-book
4 %> @author Michel Bierlaire
5 %> @date Sat Mar 21 15:43:44 2015
9 %> Given a current iterate \f$\widehat{x}\f$, consider the trust region subproblem \f[ \min_d d^T \nabla f(\widehat{x}) + \frac{1}{2} d^T \nabla^2 f(\widehat{x}) d \f] subject to \f[\|d\|_2 \leq \Delta. \f] Apply the Dogleg method to find an approximate solution.
11 %> @note Tested with \ref run1203dogleg.m
16 %> @param g the gradient \f$ \nabla f(\widehat{x})\f$
17 %> @param H the hessian \f$ \nabla^2 f(\widehat{x})\f$
18 %> @param delta the radius \f$ \Delta\f$ of the trust region
19 %> @
return [dstar,type] dstar: the approximate solution, type: the type of outcome of the method, based on the following code:
20 %> - type -2: negative curvature along Newton
's direction 21 %> - type -1: negative curvature along Cauchy's direction (i.e. along the gradient)
22 %> - type 1: Partial Cauchy step
23 %> - type 2: Newton step
24 %> - type 3: Partial Newton step
27 function [dstar,type] =
dogleg(g,H,delta)
32 % Check
if the model is convex along the gradient direction
35 dstar = -delta * g / sqrt(alpha) ;
40 % Compute the Cauchy point
42 dc = - (alpha / beta ) * g ;
43 normdc = alpha * sqrt(alpha) / beta ;
47 % The Cauchy point is outside the trust
48 % region. We move along the Cauchy
49 % direction until the border of the trut
52 dstar = (delta / normdc) * dc ;
57 % Compute Newton
's point 62 % Check the convexity of the model along Newton's direction
64 if (dn
' * H * dn <= 0.0) 65 % Return the Cauchy point 72 % Newton's point is inside the trust region
80 eta = 0.2 + (0.8 * alpha * alpha / (beta * abs(g
' * dn))) ; 82 partieldn = eta * normdn ; 83 if (partieldn <= delta) 84 % Dogleg point is inside the trust region 85 dstar = (delta / normdn) * dn ; 91 % Between Cauchy and dogleg 94 lambda = intersectionTrustRegion(dc,nu,delta) ; 97 dstar = dc + lambda * nu ; function intersectionTrustRegion(in x, in d, in delta)
Calculate the step along a direction that is on the border of the trust region centered at 0...
function symmetricRankOne(in obj, in x0, in delta0, in eps, in tr)
Applies SR1 algorithm with trust region to solve where . The parameters of the method are taken from...
function dogleg(in g, in H, in delta)
Given a current iterate , consider the trust region subproblem subject to Apply the Dogleg method t...
function newtonTrustRegion(in obj, in x0, in delta0, in eps, in tr)
Applies Newton's algorithm with trust region to solve where . The parameters of the method are taken...