資料科學中的最佳化方法
Optimization for Data Science
學期
107-2
學分
3
學分
當期課號
5396
永久課號
IAM5832
開課單位
應用數學系
授課教師
林文偉
校區
光復
類別
選修
上課時間表
| 節 | 週三 | 週四 |
|---|---|---|
4 11:10–12:00 | 資料科學中的最佳化方法 SA223 | |
5 13:20–14:10 | 資料科學中的最佳化方法 SA223 2 節連堂 | |
6 14:20–15:10 |
* 根據陽明交大上課時間表所列
概述
1 Introduction 2 Fundamentals of Unconstrained Optimization 3 Line Search Methods 4 Trust-Region Methods 5 Conjugate Gradient Methods 6 Quasi-Newton Methods 7 Large-Scale Unconstrained Optimization 10 Least-Squares Problems 11 Nonlinear Equations 12 Theory of Constrained Optimization
先修科目
Linear algebra and Calculus.
評分方式
1. Homework 50% 2. Final Exam 50%
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | 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 |
| 第 1 週 | Search Directions for Line Search Methods Models for Trust-Region Methods Scaling 3 Line Search Methods |
| 第 2 週 | 3.1 Step Length The Wolfe Conditions The Goldstein Conditions Sufficient Decrease and Backtracking 3.2 Convergence of Line Search Methods |
| 第 3 週 | 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 |
| 第 3 週 | Adding a Multiple of the Identity Modified Cholesky Factorization Modified Symmetric Indefinite Factorization |
| 第 4 週 | 3.5 Step-Length Selection Algorithms Interpolation Initial Step Length A Line Search Algorithm for the Wolfe Conditions 4 Trust-Region Methods |
| 第 4 週 | Outline of the Trust-Region Approach 4.1 Algorithms Based on the Cauchy Point The Cauchy Point |
| 第 5 週 | 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 |
| 第 5 週 | 4.3 Iterative Solution of the Subproblem The Hard Case Proof of Theorem 4.1 Convergence of Algorithms Based on Nearly Exact Solutions |
| 第 6 週 | 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 |
| 第 6 週 | Conjugate Direction Methods Basic Properties of the Conjugate Gradient Method A Practical Form of the Conjugate Gradient Method |
| 第 8 週 | Rate of Convergence Preconditioning Practical Preconditioners 5.2 Nonlinear Conjugate Gradient Methods The Fletcher-Reeves Method |
| 第 8 週 | The Polak-Ribi`ere Method and Variants Quadratic Termination and Restarts Behavior of the Fletcher-Reeves Method |
| 第 9 週 | Global Convergence Numerical Performance 6 Quasi-Newton Methods 6.1 The BFGS Method Properties of the BFGS Method Implementation |
| 第 9 週 | 6.2 The SR1 Method Properties of SR1 Updating 6.3 The Broyden Class 6.4 Convergence Analysis |
| 第 10 週 | 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 |
| 第 10 週 | Trust-Region Newton-CG Method Preconditioning the Trust-Region Newton-CG Method Trust-Region Newton-Lanczos Method |
| 第 11 週 | 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 |
| 第 11 週 | 7.3 Sparse Quasi-Newton Updates 7.4 Algorithms for Partially Separable Functions 7.5 Perspectives and Software |
| 第 12 週 | 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 |
| 第 12 週 | Convergence of the Gauss-Newton Method The Levenberg-Marquardt Method Implementation of the Levenberg-Marquardt Method Convergence of the Levenberg-Marquardt Method |
| 第 13 週 | Methods for Large-Residual Problems 10.4 Orthogonal Distance Regression 11 Nonlinear Equations 11.1 Local Algorithms Newton’s Method for Nonlinear Equations |
| 第 13 週 | Inexact Newton Methods Broyden’s Method Tensor Methods |
| 第 14 週 | 11.2 Practical Methods Merit Functions Line Search Methods Trust-Region Methods |
| 第 14 週 | 11.3 Continuation/Homotopy Methods Motivation Practical Continuation Methods |
| 第 15 週 | 12 Theory of Constrained Optimization Local and Global Solutions Smoothness |
| 第 15 週 | 12.1 Examples A Single Equality Constraint |
| 第 15 週 | A Single Inequality Constraint Two Inequality Constraints |
| 第 16 週 | 12.2 Tangent Coneand Constraint Qualifications 12.3 First-Order Optimality |
| 第 17 週 | Exam |
教科書
1. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., Springer, 2006 2. S.C. Fang and S. Puthenpura, Linear optimization and extensions: theory and algorithms, Prentice-Hall, Inc., 1993