2 %> Algorithm 12.3: Truncated conjugate gradients method to find an approximation of the trust region subproblem. Implementation of algorithm 12.3 of \cite Bier15-book
4 %> @author Michel Bierlaire
5 %> @date Sat Mar 21 15:49:09 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 truncated conjugate gradients method to find an approximate solution.
11 %> @note Tested with \ref run1203tcg.m
15 %> @param g the gradient \f$ \nabla f(\widehat{x})\f$
16 %> @param H the hessian \f$ \nabla^2 f(\widehat{x})\f$
17 %> @param delta the radius \f$ \Delta\f$ of the trust region
18 %> @
return [dstar,type]
19 %> @
return dstar: the approximate solution
20 %> @
return type: the type of outcome of the method, based on the following code:
21 %> - type 1: convergence
22 %> - type 2: out of the trust region
23 %> - type 3: negative curvature detected
31 if (dk
' * H * dk <= 0) 35 c = xk' * xk - delta * delta ;
36 rho = b * b - 4 * a * c ;
37 step = xk + ((-b + sqrt(rho)) / (2*a)) * dk ;
40 alphak = - (dk
' * gk) / (dk' * H * dk) ;
41 xkp1 = xk + alphak * dk ;
42 if (norm(xkp1) > delta)
46 c = xk
' * xk - delta * delta ; 47 rho = b * b - 4 * a * c ; 48 step = xk + ((-b + sqrt(rho)) / (2*a)) * dk ; 53 betak = (gkp1' * gkp1) / (gk
' * gk) ; 54 dk = -gkp1 + betak * dk ; 56 if (norm(gkp1) <= tol) 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 truncatedConjugateGradient(in g, in H, in delta)
Given a current iterate , consider the trust region subproblem subject to Apply the truncated conju...
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...