From Wakapon
Jump to: navigation, search
Line 8: Line 8:
  
 
== Optimization ==
 
== Optimization ==
 +
 +
=== Unconstrained Optimization ===
 +
* Descent methods
 +
* Line search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
 +
* Descent methods with trust region . . . . . . . . . . . . . . . . . 26
 +
* Steepest descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
 +
* Quadratic models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
 +
* Conjugate gradient methods . . . . . . . . . . . . . . . . . . . . . . . . 31
 +
 +
=== Newton-Type Methods ===
 +
* Newton’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
 +
* Damped Newton methods . . . . . . . . . . . . . . . . . . . . . . . . . . 48
 +
* Quasi–Newton methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
 +
* DFP formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
 +
* BFGS formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
 +
* Quasi–Newton implementation . . . . . . . . . . . . . . . . . . . . . 63
 +
 +
=== Direct Search ===
 +
* Simplex method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
 +
* Method of Hooke and Jeeves . . . . . . . . . . . . . . . . . . . . . . . 70
 +
 +
=== Linear Data Fitting ===
 +
* “Best” fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
 +
* Linear least squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
 +
* Weighted least squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
 +
* Generalized least squares . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
 +
* Polynomial fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
 +
* Spline fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
 +
* Choice of knots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
 +
 +
=== Nonlinear Least Squares Problems ===
 +
* Gauss–Newton method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
 +
* The Levenberg–Marquardt method . . . . . . . . . . . . . . . . . 120
 +
* Powell’s Dog Leg Method . . . . . . . . . . . . . . . . . . . . . . . . . . 125
 +
* Secant version of the L–M method . . . . . . . . . . . . . . . . . 130
 +
* Secant version of the Dog Leg method . . . . . . . . . . . . . . 134

Revision as of 19:18, 30 July 2017

This page is a rough summary of the various methods for optimization, curve fitting/linear regression, etc.

First, some definitions:

  • In statistics, linear regression is basically a way to make a curve fit a set of data points

Linear Regression.png

Optimization

Unconstrained Optimization

  • Descent methods
  • Line search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
  • Descent methods with trust region . . . . . . . . . . . . . . . . . 26
  • Steepest descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
  • Quadratic models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
  • Conjugate gradient methods . . . . . . . . . . . . . . . . . . . . . . . . 31

Newton-Type Methods

  • Newton’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
  • Damped Newton methods . . . . . . . . . . . . . . . . . . . . . . . . . . 48
  • Quasi–Newton methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
  • DFP formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
  • BFGS formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
  • Quasi–Newton implementation . . . . . . . . . . . . . . . . . . . . . 63

Direct Search

  • Simplex method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
  • Method of Hooke and Jeeves . . . . . . . . . . . . . . . . . . . . . . . 70

Linear Data Fitting

  • “Best” fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
  • Linear least squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
  • Weighted least squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
  • Generalized least squares . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
  • Polynomial fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
  • Spline fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
  • Choice of knots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

Nonlinear Least Squares Problems

  • Gauss–Newton method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
  • The Levenberg–Marquardt method . . . . . . . . . . . . . . . . . 120
  • Powell’s Dog Leg Method . . . . . . . . . . . . . . . . . . . . . . . . . . 125
  • Secant version of the L–M method . . . . . . . . . . . . . . . . . 130
  • Secant version of the Dog Leg method . . . . . . . . . . . . . . 134