Luus–Jaakola

In computational engineering, Luus–Jaakola (LJ) denotes a heuristic for global optimization of a real-valued function.[1] In engineering use, LJ is not an algorithm that terminates with an optimal solution; nor is it an iterative method that generates a sequence of points that converges to an optimal solution (when one exists). However, when applied to a twice continuously differentiable function, the LJ heuristic is a proper iterative method, that generates a sequence that has a convergent subsequence; for this class of problems, Newton's method is recommended and enjoys a quadratic rate of convergence, while no convergence rate analysis has been given for the LJ heuristic.[1] In practice, the LJ heuristic has been recommended for functions that need be neither convex nor differentiable nor locally Lipschitz: The LJ heuristic does not use a gradient or subgradient when one be available, which allows its application to non-differentiable and non-convex problems.

Proposed by Luus and Jaakola,[2] LJ generates a sequence of iterates. The next iterate is selected from a sample from a neighborhood of the current position using a uniform distribution. With each iteration, the neighborhood decreases, which forces a subsequence of iterates to converge to a cluster point.[1]

Luus has applied LJ in optimal control,[3] [4] transformer design,[5] metallurgical processes,[6] and chemical engineering.[7]

Motivation
When the current position x is far from the optimum the probability is 1/2 for finding an improvement through uniform random sampling.
As we approach the optimum the probability of finding further improvements through uniform sampling decreases towards zero if the sampling-range d is kept fixed.

At each step, the LJ heuristic maintains a box from which it samples points randomly, using a uniform distribution on the box. For a unimodal function, the probability of reducing the objective function decreases as the box approach a minimum. The picture displays a one-dimensional example.

Heuristic

Let f: ℝn → ℝ be the fitness or cost function which must be minimized. Let x ∈ ℝn designate a position or candidate solution in the search-space. The LJ heuristic iterates the following steps:

  • Initialize x ~ U(blo,bup) with a random uniform position in the search-space, where blo and bup are the lower and upper boundaries, respectively.
  • Set the initial sampling range to cover the entire search-space (or a part of it): d = bup − blo
  • 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: d = 0.95 d
  • Now x holds the best-found position.

Variations

Luus notes that ARS (Adaptive Random Search) algorithms proposed to date differ in regard to many aspects.[8]

  • Procedure of generating random trial points.
  • Number of internal loops (NIL, the number of random search points in each cycle).
  • Number of cycles (NEL, number of external loops).
  • Contraction coefficient of the search region size. (Some example values are 0.95 to 0.60.)
    • Whether the region reduction rate is the same for all variables or a different rate for each variable (called the M-LJ algorithm).
    • Whether the region reduction rate is a constant or follows another distribution (e.g. Gaussian).
  • Whether to incorporate a line search.
  • Whether to consider constraints of the random points as acceptance criteria, or to incorporate a quadratic penalty.

Convergence

Nair proved a convergence analysis. For twice continuously differentiable functions, the LJ heuristic generates a sequence of iterates having a convergent subsequence.[1] For this class of problems, Newton's method is the usual optimization method, and it has quadratic convergence (regardless of the dimension of the space, which can be a Banach space, according to Kantorovich's analysis).

The worst-case complexity of minimization on the class of unimodal functions grows exponentially in the dimension of the problem, according to the analysis of Yudin and Nemirovsky, however. The Yudin-Nemirovsky analysis implies that no method can be fast on high-dimensional problems that lack convexity:

"The catastrophic growth [in the number of iterations needed to reach an approximate solution of a given accuracy] as [the number of dimensions increases to infinity] shows that it is meaningless to pose the question of constructing universal methods of solving ... problems of any appreciable dimensionality 'generally'. It is interesting to note that the same [conclusion] holds for ... problems generated by uni-extremal [that is, unimodal] (but not convex) functions."[9]

When applied to twice continuously differentiable problems, the LJ heuristic's rate of convergence decreases as the number of dimensions increases.[10]

gollark: Did the situation with the end island get worked out?
gollark: Perhaps a giant claimwall around Switchcity?
gollark: Idea: place claims in places which people may one day use then sell them at exorbiant prices if they try to.
gollark: TERRORIST!
gollark: No, it doesn't. I thought that having it send to ingame accounts on the same switchcraft.kst thing would, then I realized that it just needed to switch the numbers around internally without going through the krist node.

See also

References
  1. Nair, G. Gopalakrishnan (1979). "On the convergence of the LJ search method". Journal of Optimization Theory and Applications. 28 (3): 429–434. doi:10.1007/BF00933384. MR 0543384.CS1 maint: ref=harv (link)
  2. Luus, R.; Jaakola, T.H.I. (1973). "Optimization by direct search and systematic reduction of the size of search region". AIChE Journal. 19 (4): 760–766. doi:10.1002/aic.690190413.
  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. Heinänen, Eero (October 2018). A Method for automatic tuning of PID controller following Luus-Jaakola optimization (PDF) (Master's Thesis ed.). Tampere, Finland: Tampere University of Technology. Retrieved Feb 1, 2019.
  5. Spaans, R.; Luus, R. (1992). "Importance of search-domain reduction in random optimization". Journal of Optimization Theory and Applications. 75: 635–638. doi:10.1007/BF00940497. MR 1194836.
  6. 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.
  7. 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. doi:10.1016/s0098-1354(99)00283-5.
  8. Luus, Rein (2010). "Formulation and Illustration of Luus-Jaakola Optimization Procedure". In Rangalah, Gade Pandu (ed.). Stochastic Global Optimization: Techniques and Applications in Chemical Engineering. World Scientific Pub Co Inc. pp. 17–56. ISBN 978-9814299206.
  9. Nemirovsky & Yudin (1983, p. 7)

    Page 7 summarizes the later discussion of Nemirovsky & Yudin (1983, pp. 36–39): Nemirovsky, A. S.; Yudin, D. B. (1983). Problem complexity and method efficiency in optimization. Wiley-Interscience Series in Discrete Mathematics (Translated by E. R. Dawson from the (1979) Russian (Moscow: Nauka) ed.). New York: John Wiley & Sons, Inc. pp. xv+388. ISBN 0-471-10345-4. MR 0702836.CS1 maint: ref=harv (link)

  10. Nair (1979, p. 433)

Nemirovsky, A. S.; Yudin, D. B. (1983). Problem complexity and method efficiency in optimization. Wiley-Interscience Series in Discrete Mathematics (Translated by E. R. Dawson from the (1979) Russian (Moscow: Nauka) ed.). New York: John Wiley & Sons, Inc. pp. xv+388. ISBN 0-471-10345-4. MR 0702836.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.