Misplaced Pages

This is an old revision of this page, as edited by MrOllie (talk | contribs) at 17:30, 6 December 2010. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Local unimodal sampling (LUS) is a method for doing numerical optimization which does not require the gradient of the problem to be optimized and LUS can hence be used on functions that are not continuous or differentiable. Such optimization methods are also known as direct-search, derivative-free, or black-box methods.

LUS is attributed to Pedersen and works by maintaining 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 the 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. Pedersen noted that pattern search works well for optimizing unimodal functions and translated its halving of the sampling-range 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.

The main differences between LUS and the Luus–Jaakola (LJ) method are that the decrease-factor α depends on the dimensionality of the search-space n where as LJ typically just sets α = 0.95, and that LUS starts out by sampling the entire search-space where as LJ starts out by sampling only a fraction of the search-space.

Usage and criticism

LUS is used in meta-optimization for tuning the behavioural parameters of another optimization method, see e.g. Pedersen , because it is simple and usually finds satisfactory solutions using few iterations, which is necessary for such computationally expensive optimization problems. The rapidity of LUS is achieved by its exponential decrease of the sampling-range which works well for unimodal problems, but it is a weakness for multi-modal problems as it sometimes decreases the sampling-range too rapidly before it finds the basin holding the global minimum. This means LUS must typically be run several times to locate the minimum of multi-modal problems and sometimes fails completely.

LUS has also been criticized informally amongst researchers for using a greedy update rule and it has been suggested to use a stochastic update rule as in the Metropolis–Hastings algorithm or simulated annealing, but it was noted in section 2.3.3 of that such stochastic update rules are not useful when sampling real-valued search-spaces as they merely cause the optimizer to move back and forth towards the optimum with a still low probability of escaping local optima and a now lowered probability of converging to any optimum.

History

The abbreviation LUS is the word for louse in the Danish language. According to Pedersen the name was chosen as a humorous tribute to the Marx Brothers who have several louse-puns in their films, and not because the method has any resemblance to the movement of a real louse. The LUS method was developed in Hundested and Copenhagen, Denmark.

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.
2. Jaakola, T.H.I. (1973). "Optimization by direct search and systematic reduction of the size of search region". American Institute of Chemical Engineers Journal (AIChE). 19 (4): 760–766.
3. Pedersen, M.E.H. (2010). "Simplifying particle swarm optimization" (PDF). Applied Soft Computing. 10: 618–628. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

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

• Proposed deletion as of 6 December 2010
• Optimization algorithms
• Mathematical optimization