Optimization: principles and algorithms, by Michel Bierlaire
dogleg.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 12.2: Dogleg method to find an approximation of the trust region subproblem. Implementation of algorithm 12.2 of \cite Bier15-book
3 %>
4 %> @author Michel Bierlaire
5 %> @date Sat Mar 21 15:43:44 2015
6 %> @ingroup Algorithms
7 %> @ingroup chap12
8 
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.
10 
11 %> @note Tested with \ref run1203dogleg.m
12 %> @note Calls \ref intersectionTrustRegion
13 %> @note Called by \ref newtonTrustRegion
14 %> @note Called by \ref symmetricRankOne
15 
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
25 %> - type 4: Dogleg
26 %>
27 function [dstar,type] = dogleg(g,H,delta)
28 
29  alpha = g' * g ;
30  beta = g' * H * g ;
31 
32 % Check if the model is convex along the gradient direction
33 
34  if (beta <= 0)
35  dstar = -delta * g / sqrt(alpha) ;
36  type = -1 ;
37  return
38  endif
39 
40  % Compute the Cauchy point
41 
42  dc = - (alpha / beta ) * g ;
43  normdc = alpha * sqrt(alpha) / beta ;
44 
45 
46  if (normdc >= delta)
47  % The Cauchy point is outside the trust
48  % region. We move along the Cauchy
49  % direction until the border of the trut
50  % region.
51 
52  dstar = (delta / normdc) * dc ;
53  type = 1 ;
54  return ;
55  endif
56 
57 % Compute Newton's point
58 
59  dn = - H \ g ;
60  normdn = norm(dn) ;
61 
62 % Check the convexity of the model along Newton's direction
63 
64  if (dn' * H * dn <= 0.0)
65  % Return the Cauchy point
66  dstar = dc ;
67  type = -2 ;
68  return ;
69  endif
70 
71  if (normdn <= delta)
72  % Newton's point is inside the trust region
73  dstar = dn ;
74  type = 2;
75  return ;
76 
77  endif
78  % Compute the dogleg point
79 
80  eta = 0.2 + (0.8 * alpha * alpha / (beta * abs(g' * dn))) ;
81 
82  partieldn = eta * normdn ;
83  if (partieldn <= delta)
84  % Dogleg point is inside the trust region
85  dstar = (delta / normdn) * dn ;
86  type = 3 ;
87  return ;
88  endif
89 
90 
91  % Between Cauchy and dogleg
92 
93  nu = eta * dn - dc ;
94  lambda = intersectionTrustRegion(dc,nu,delta) ;
95 
96 
97  dstar = dc + lambda * nu ;
98  type = 4 ;
99  return ;
100 
101 endfunction
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&#39;s algorithm with trust region to solve where . The parameters of the method are taken...
Copyright 2015-2016 Michel Bierlaire