A Survey of Optimization Methods from a Machine Learning Perspective <s> 6) Trust Region Method: <s> An algorithm for minimizing a nonlinear function subject to nonlinear inequality constraints is described. It applies sequential quadratic programming techniques to a sequence of barrier problems, and uses trust regions to ensure the robustness of the iteration and to allow the direct use of second order derivatives. This framework permits primal and primal-dual steps, but the paper focuses on the primal version of the new algorithm. An analysis of the convergence properties of this method is presented. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 6) Trust Region Method: <s> Preface 1 Introduction 1.1 Introduction 1.2 Mathematics Foundations 1.2.1 Norm 1.2.2 Inverse and Generalized Inverse of a Matrix 1.2.3 Properties of Eigenvalues 1.2.4 Rank-One Update 1.2.5 Function and Differential 1.3 Convex Sets and Convex Functions 1.3.1 Convex Sets 1.3.2 Convex Functions 1.3.3 Separation and Support of Convex Sets 1.4 Optimality Conditions for Unconstrained Case 1.5 Structure of Optimization Methods Exercises 2 Line Search 2.1 Introduction 2.2 Convergence Theory for Exact Line Search 2.3 Section Methods 2.3.1 The Golden Section Method 2.3.2 The Fibonacci Method 2.4 Interpolation Method 2.4.1 Quadratic Interpolation Methods 2.4.2 Cubic Interpolation Method 2.5 Inexact Line Search Techniques 2.5.1 Armijo and Goldstein Rule 2.5.2 Wolfe-Powell Rule 2.5.3 Goldstein Algorithm and Wolfe-Powell Algorithm 2.5.4 Backtracking Line Search 2.5.5 Convergence Theorems of Inexact Line Search Exercises 3 Newton's Methods 3.1 The Steepest Descent Method 3.1.1 The Steepest Descent Method 3.1.2 Convergence of the Steepest Descent Method 3.1.3 Barzilai and Borwein Gradient Method 3.1.4 Appendix: Kantorovich Inequality 3.2 Newton's Method 3.3 Modified Newton's Method 3.4 Finite-Difference Newton's Method 3.5 Negative Curvature Direction Method 3.5.1 Gill-Murray Stable Newton's Method 3.5.2 Fiacco-McCormick Method 3.5.3 Fletcher-Freeman Method 3.5.4 Second-Order Step Rules 3.6 Inexact Newton's Method Exercises 4 Conjugate Gradient Method 4.1 Conjugate Direction Methods 4.2 Conjugate Gradient Method 4.2.1 Conjugate Gradient Method 4.2.2 Beale's Three-Term Conjugate Gradient Method 4.2.3 Preconditioned Conjugate Gradient Method 4.3 Convergence of Conjugate Gradient Methods 4.3.1 Global Convergence of Conjugate Gradient Methods 4.3.2 Convergence Rate of Conjugate Gradient Methods Exercises 5 Quasi-Newton Methods 5.1 Quasi-Newton Methods 5.1.1 Quasi-Newton Equation 5.1.2 Symmetric Rank-One (SR1) Update 5.1.3 DFP Update 5.1.4 BFGS Update and PSB Update 5.1.5 The Least Change Secant Update 5.2 The Broyden Class 5.3 Global Convergence of Quasi-Newton Methods 5.3.1 Global Convergence under Exact Line Search 5.3.2 Global Convergence under Inexact Line Search 5.4 Local Convergence of Quasi-Newton Methods 5.4.1 Superlinear Convergence of General Quasi-Newton Methods 5.4.2 Linear Convergence of General Quasi-Newton Methods 5.4.3 Local Convergence of Broyden's Rank-One Update 5.4.4 Local and Linear Convergence of DFP Method 5.4.5 Superlinear Convergence of BFGS Method 5.4.6 Superlinear Convergence of DFP Method 5.4.7 Local Convergence of Broyden's Class Methods 5.5 Self-Scaling Variable Metric (SSVM) Methods 5.5.1 Motivation to SSVM Method 5.5.2 Self-Scaling Variable Metric (SSVM) Method 5.5.3 Choices of the Scaling Factor 5.6 Sparse Quasi-Newton Methods 5.7 Limited Memory BFGS Method Exercises 6 Trust-Region and Conic Model Methods 6.1 Trust-Region Methods 6.1.1 Trust-Region Methods 6.1.2 Convergence of Trust-Region Methods 6.1.3 Solving A Trust-Region Subproblem 6.2 Conic Model and Collinear Scaling Algorithm 6.2.1 Conic Model 6.2.2 Generalized Quasi-Newton Equation 6.2.3 Updates that Preserve Past Information 6.2.4 Collinear Scaling BFGS Algorithm 6.3 Tensor Methods 6.3.1 Tensor Method for Nonlinear Equations 6.3.2 Tensor Methods for Unconstrained Optimization Exercises <s> BIB002
Most of the methods introduced above are based on a one-dimensional line search. The process of update can be described as θ k + η k d k . The displacement of the point in the direction of d k can be written as s k . The typical trust region method (TRM) can be used for unconstrained nonlinear optimization problems BIB002 , BIB001 ,  . In the TRM, the displacement s k is directly determined without the search direction d k . For the problem min f θ (x), the TRM BIB002 uses the second-order Taylor expansion to approximate the objective function f θ (x), denoted as q (k) (s). Each search is done within the range of trust region with radius △ k . This problem can be described as where g k is the approximate gradient of the objective function f (x) at the current iteration point x k , g k ≈ ∇f (x k ), B k is a symmetric matrix, which is the approximation of Hessian matrix ∇ 2 f θ (x k ), and △ k > 0 is the radius of the trust region. If the L 2 norm is used in the constraint function, it becomes the Levenberg-Marquardt algorithm  . If s k is the solution of the trust region subproblem (80), the displacement s k of each update is limited by the trust region radius △ k . The core part of the TRM is the update of △ k . In each update process, the similarity of the quadratic model q(s k ) and the objective function f θ (x) is measured, and △ k is updated dynamically. The actual amount of descent in the kth iteration is BIB002  The predicted drop in the kth iteration is The ratio r k is defined to measure the approximate degree of both, It indicates that the model is more realistic than expected when r k is close to 1, and then we should consider expanding △ k . At the same time, it indicates that the model predicts a large drop and the actual drop is small when r k is close to 0, and then we should reduce △ k . Moreover, if r k is between 0 and 1, we can leave △ k unchanged. The thresholds 0 and 1 are generally set as the left and right boundaries of r k BIB002 .