Misplaced Pages

Revision as of 13:56, 13 December 2010

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 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 the neighbourhood of the current position using a uniform distribution. The sampling-range is initially the full search-space and decreases exponentially during optimization.

LUS is similar to the Luus-Jaakola (LJ) optimizer with the main difference being an improvement in determining the exponential rate of sampling-range decrease, see below. These optimizers have been applied successfully in such diverse fields as optimal control , transformer design , metallurgical processes , chemical engineering , and machine translation , to name a few.

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.

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.

Criticism

LUS has been criticized 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.

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. ^ Luus, R.; 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. Bojkov, R.; Hansel, B.; Luus, R. (1993). "Application of direct search optimization to optimal control problems". Hungarian Journal of Industrial Chemistry. 21: 177–185.
4. Spaans, R.; Luus, R. (1992). "Importance of search-domain reduction in random optimization". Journal of Optimization Theory and Applications. 75: 635–638.
5. Papangelakis, V.G.; Luus, R. (1993). "Reactor optimization in the pressure oxidization process". Proc. Int. Symp. on Modelling, Simulation and Control of Metallurgical Processes. pp. 159–171. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
6. Lee, Y.P.; Rangaiah, G.P.; Luus, R. (1999). "Phase and chemical equilibrium calculations by direct search optimization". Computers & Chemical Engineering. 23 (9): 1183–1191.
7. Schuth, A.G. (2010). Tuning methods in statistical machine translation (PDF) (MSc thesis). University of Amsterdam.

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 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
• Mathematical optimization