Misplaced Pages

This is an old revision of this page, as edited by Kiefer.Wolfowitz (talk | contribs) at 17:26, 22 February 2011 (simplify lead. If it works on discontinuous functions, then don't worry about gradients). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Local unimodal sampling (LUS) is an optimization procedure that can be used on functions that are not continuous. Such optimization methods are also known as direct-search, derivative-free, purely primal, or black-box methods.

LUS works by having a single position in the search-space and moving to a new position in case of improvement to the fitness or cost function. New positions are sampled from a neighbourhood of the current position using a uniform distribution. The sampling-range is initially the full search-space and decreases exponentially during optimization.

Motivation

Using a fixed sampling-range for randomly sampling the search-space of a unimodal function the probability of finding improved positions will decrease as we approach the optimum. This is because a decreasing portion of the sampling-range will yield improved fitness (see pictures for the single-dimensional case.) Hence, the sampling range must be decreased somehow. Pattern search works well for optimizing unimodal functions and its halving of the sampling-range was translated into a formula that would have similar effect when using a uniform distribution for the sampling.

Algorithm

Let f: ℝ → ℝ be the fitness or cost function which must be minimized. Let x ∈ ℝ designate a position or candidate solution in the search-space. The LUS algorithm can then be described as:

• Initialize x~U(b_lo,b_up) with a random uniform position in the search-space, where b_lo and b_up are the lower and upper boundaries, respectively.
• Set the initial sampling range to cover the entire search-space: d = b_up − b_lo
• Until a termination criterion is met (e.g. number of iterations performed, or adequate fitness reached), repeat the following:
  • Pick a random vector a ~ U(−d, d)
  • Add this to the current position x to create the new potential position y = x + a
  • If (f(y) < f(x)) then move to the new position by setting x = y, otherwise decrease the sampling-range by multiplying with factor q (see below): d = q d
• Now x holds the best-found position.

Sampling-range decrease factor

The factor q for exponentially decreasing the sampling-range is defined by: q = 2 where n is the dimensionality of the search-space and α is a user-adjustable parameter. Setting 0<α<1 causes slower decrease of the sampling-range and setting α > 1 causes more rapid decrease of the sampling-range. Typically it is set to α = 1/3

Note that decreasing the sampling-range n times by factor q results in an overall decrease of q = 2 and for α = 1 this would mean a halving of the sampling-range.

See also

• Random optimization is a related family of optimization methods which sample from a normal distribution instead of a uniform distribution.
• Random search is a related family of optimization methods which sample from a hypersphere instead of a uniform distribution.
• Pattern search takes steps along the axes of the search-space using exponentially decreasing step sizes.

References

1. Pedersen, M.E.H. (2010). Tuning & Simplifying Heuristical Optimization (PDF) (PhD thesis). University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group.

v t e Optimization: Algorithms, methods, and heuristics
Unconstrained nonlinear Functions Golden-section search Powell's method Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Collinear gradients method Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method
Constrained nonlinear General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming
Convex optimization Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke Active-set method
Combinatorial Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow
Metaheuristics Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search
Software

• Optimization algorithms