Application Of New Trust Region Methods, The Quasi-newton Equation

In the classical trust region method for unconstrained optimization, the choice of thequadratic model and the size of the trust region are crucial to the effectiveness of thealgorithm. For example, the trust region Newton method which based on settingB_k=▽~2f(x_k) has the local Q-quadratic convergence rate. But if the Hessian is toocomputational expenssive to get, most people choose the quasi-Newton equation togenerate B_k. On the other hand, if the trust region is large enough to generate a larger stepin each iterate, the convergence rate will naturally increased. Many people added linesearch strategy to adjust the trust region when the trial step s_k of the subproblem is failed.Since the new qausi-Newton equation can get a higher approximation to the Hessianmatrix, we in this paper choose MBFGS update to generate B_k. When the subprolemsolution s_k is computed, we use the line search stategy to find a pointα_ks_k that satisfiesWolfe condition. So the matrix B_k can naturally maintain positive-definite and thesubprolem is convenient to compute. We also give a condtion which can incorportate linesearch method with trust region method and useα_k to adjust the size of the new trustregion. When the subproblem's solution s_k is not acceptable, that isρ_k＜η, we set the sizeof the next trust region to beα_k‖s_k‖. If by this time, we get an adequate reduction of theobjective function using the line search technique andα_k≥1. In contrast with the classicaltrust region method, our method keeps the size of the trust region increasing. That is to say,though s_k is not acceptable forρ_k＞η, it satifises the wolfe condition and is acceptablefor the line search strategy. Then it's reasonable to set the size of the trust region accordingtoα_ks_k, so the line search strategy not only guarantees the reduction of the algorithm, butalso improves the adjustment of the trust region size.We construct a new algorithm basedon the above analysis. We show that the algorithm preserves the first order globalconvergence of the classical trust region algorithm, and the local superlinear convergencerate. Numercial results are presented to show the algorithm is efficient for small sizeproblem.