Optimization

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

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

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

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

“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

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

Contents