資料科學中的最佳化方法

1 Introduction 2 Fundamentals of Unconstrained Optimization 2.1 What Is a Solution? Recognizing a Local Minimum Nonsmooth Problems 2.2 Overview of Algorithms Two Strategies: Line Search and Trust Region

Search Directions for Line Search Methods Models for Trust-Region Methods Scaling 3 Line Search Methods

3.1 Step Length The Wolfe Conditions The Goldstein Conditions Sufficient Decrease and Backtracking 3.2 Convergence of Line Search Methods

3.3 Rate of Convergence Convergence Rate of Steepest Descent Newton’s Method Quasi-Newton Methods 3.4 Newton’s Method with Hessian Modification Eigenvalue Modification

Adding a Multiple of the Identity Modified Cholesky Factorization Modified Symmetric Indefinite Factorization

3.5 Step-Length Selection Algorithms Interpolation Initial Step Length A Line Search Algorithm for the Wolfe Conditions 4 Trust-Region Methods

Outline of the Trust-Region Approach 4.1 Algorithms Based on the Cauchy Point The Cauchy Point

Improving on the Cauchy Point The Dogleg Method Two-Dimensional Subspace Minimization 4.2 Global Convergence Reduction Obtained by the Cauchy Point Convergence to Stationary Points

4.3 Iterative Solution of the Subproblem The Hard Case Proof of Theorem 4.1 Convergence of Algorithms Based on Nearly Exact Solutions

4.4 Local Convergence of Trust-Region Newton Methods 4.5 Other Enhancements Scaling Trust Regions in Other Norms 5 Conjugate Gradient Methods 5.1 The Linear Conjugate Gradient Method

Conjugate Direction Methods Basic Properties of the Conjugate Gradient Method A Practical Form of the Conjugate Gradient Method

Rate of Convergence Preconditioning Practical Preconditioners 5.2 Nonlinear Conjugate Gradient Methods The Fletcher-Reeves Method

The Polak-Ribi`ere Method and Variants Quadratic Termination and Restarts Behavior of the Fletcher-Reeves Method

Global Convergence Numerical Performance 6 Quasi-Newton Methods 6.1 The BFGS Method Properties of the BFGS Method Implementation

6.2 The SR1 Method Properties of SR1 Updating 6.3 The Broyden Class 6.4 Convergence Analysis

Global Convergence of the BFGS Method Superlinear Convergence of the BFGS Method Convergence Analysis of the SR1 Method 7 Large-Scale Unconstrained Optimization 7.1 Inexact Newton Methods Local Convergence of Inexact Newton Methods Line Search Newton-CG Method

Trust-Region Newton-CG Method Preconditioning the Trust-Region Newton-CG Method Trust-Region Newton-Lanczos Method

7.2 Limited-Memory Quasi-Newton Methods Limited-Memory BFGS Relationship with Conjugate Gradient Methods General Limited-Memory Updating Compact Representation of BFGS Updating Unrollingthe Update

7.3 Sparse Quasi-Newton Updates 7.4 Algorithms for Partially Separable Functions 7.5 Perspectives and Software

10 Least-Squares Problems 10.1 Background 10.2 Linear Least-Squares Problems 10.3 Algorithms for Nonlinear Least-Squares Problems The Gauss-Newton Method

Convergence of the Gauss-Newton Method The Levenberg-Marquardt Method Implementation of the Levenberg-Marquardt Method Convergence of the Levenberg-Marquardt Method

Methods for Large-Residual Problems 10.4 Orthogonal Distance Regression 11 Nonlinear Equations 11.1 Local Algorithms Newton’s Method for Nonlinear Equations

Inexact Newton Methods Broyden’s Method Tensor Methods

11.2 Practical Methods Merit Functions Line Search Methods Trust-Region Methods

11.3 Continuation/Homotopy Methods Motivation Practical Continuation Methods

12 Theory of Constrained Optimization Local and Global Solutions Smoothness

12.1 Examples A Single Equality Constraint

A Single Inequality Constraint Two Inequality Constraints

12.2 Tangent Coneand Constraint Qualifications 12.3 First-Order Optimality

Exam