數值最佳化與應用

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

Linear algebra and Calculus.

1. Homework 50% 2. Final Exam 50%

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