Function minimization

[kth-competitive-programming]

Function minimization

[simonlindholm]

For high-dimensional problems, where derivatives are not available: https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method#One_possible_variation_of_the_NM_algorithm

[simonlindholm]

https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm is supposedly good; starts off with B^-1 = identity matrix, updates it according to some complex formula to get a search direction in each step. (Just like conjugated gradient descent also picks out a search direction).

Given the search direction we can use any old method to walk a reasonable distance in that direction, e.g. 1d hill climbing, or walking to the furthest point such that the improvement we see is still at least 0.5 times the gradient times the search vector (after that it's starting to become non-linear and we might not be using the right direction anymore -- the "Armijo rule" with c = 0.5). There's another fancy method one can use when deciding on how far to walk, which is the curvature rule. Define f(x) to be the gradient at x times the search vector, i.e. the expected improvement when walking 1 unit in the search direction starting at x. Now walk only to points y such that f(y) <= d * f(x) (i.e., if the search direction is still good, with f(y) > d * f(x), keep walking), where d is ~0.1 if using conjugated gradient descent or ~0.9 if using BFGS. Combining both rules with c < d results in the Wolfe condition, which guarantees that the gradient converges to 0, although it's not clear how to combine them (take the maximum?). If they conflict we have walked too far. Apparently c = 1e-4 is reasonable, somehow.

BFGS uses O(N^2) large matrices and might be bad for large N for that reason compared to conjugated gradient descent. Not sure what the typical runtime of the latter is though.

Stopping condition: L2(gradient) < 1e-6, or when walk step is small. For computing gradient, eps = 1e-6 might work.