Luus–Jaakola
Encyclopedia
In computational engineering
, Luus–Jaakola (LJ) denotes a heuristic for global
optimization
of a real-valued function. 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. 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, 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.
Luus has applied LJ in optimal control
, transformer design
, metallurgical processes
, and chemical engineering
.
, 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:
When applied to twice continuously differentiable problems, the LJ heuristic's rate of convergence decreases as the number of dimensions increases.
Computational engineering
Computational science and engineering is a relatively new discipline of engineering. It is typically offered as a masters or doctorate program at several institutions...
, Luus–Jaakola (LJ) denotes a heuristic for global
Global optimization
Global optimization is a branch of applied mathematics and numerical analysis that deals with the optimization of a function or a set of functions to some criteria.- General :The most common form is the minimization of one real-valued function...
optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
of a real-valued function. In engineering use, LJ is not an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
that terminates with an optimal solution; nor is it an iterative method
Iterative method
In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the 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
Newton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
is recommended and enjoys a quadratic rate of convergence, while no convergence rate analysis has been given for the LJ heuristic. In practice, the LJ heuristic has been recommended for functions that need be neither convex
Convex function
In mathematics, a real-valued function f defined on an interval is called convex if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph is a convex set...
nor differentiable nor locally Lipschitz
Lipschitz continuity
In mathematical analysis, Lipschitz continuity, named after Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: for every pair of points on the graph of this function, the absolute value of the...
: The LJ heuristic does not use a gradient
Gradient
In vector calculus, the gradient of a scalar field is a vector field that points in the direction of the greatest rate of increase of the scalar field, and whose magnitude is the greatest rate of change....
or subgradient when one be available, which allows its application to non-differentiable and non-convex problems.
Proposed by Luus and Jaakola, 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
Uniform distribution (continuous)
In probability theory and statistics, the continuous uniform distribution or rectangular distribution is a family of probability distributions such that for each member of the family, all intervals of the same length on the distribution's support are equally probable. The support is defined by...
. With each iteration, the neighborhood decreases, which forces a subsequence of iterates to converge to a cluster point.
Luus has applied LJ in optimal control
Optimal control
Optimal control theory, an extension of the calculus of variations, is a mathematical optimization method for deriving control policies. The method is largely due to the work of Lev Pontryagin and his collaborators in the Soviet Union and Richard Bellman in the United States.-General method:Optimal...
, transformer design
Transformer
A transformer is a device that transfers electrical energy from one circuit to another through inductively coupled conductors—the transformer's coils. A varying current in the first or primary winding creates a varying magnetic flux in the transformer's core and thus a varying magnetic field...
, metallurgical processes
Metallurgy
Metallurgy is a domain of materials science that studies the physical and chemical behavior of metallic elements, their intermetallic compounds, and their mixtures, which are called alloys. It is also the technology of metals: the way in which science is applied to their practical use...
, and chemical engineering
Chemical engineering
Chemical engineering is the branch of engineering that deals with physical science , and life sciences with mathematics and economics, to the process of converting raw materials or chemicals into more useful or valuable forms...
.
Motivation
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 uniformUniform distribution (continuous)In probability theory and statistics, the continuous uniform distribution or rectangular distribution is a family of probability distributions such that for each member of the family, all intervals of the same length on the distribution's support are equally probable. The support is defined by...
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.
Convergence
Nair proved a convergence analysis. For twice continuously differentiable functions, the LJ heuristic generates a sequence of iterates having a convergent subsequence. 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 spaceBanach space
In mathematics, Banach spaces is the name for complete normed vector spaces, one of the central objects of study in functional analysis. A complete normed vector space is a vector space V with a norm ||·|| such that every Cauchy sequence in V has a limit in V In mathematics, Banach spaces is the...
, 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."
When applied to twice continuously differentiable problems, the LJ heuristic's rate of convergence decreases as the number of dimensions increases.
See also
- Random optimizationRandom optimizationRandom optimization is a family of numerical optimization methods that do not require the gradient of the problem to be optimized and RO can hence be used on functions that are not continuous or differentiable...
is a related family of optimization methods that sample from general distributions, for example the uniform distribution. - Random searchRandom searchRandom search is a family of numerical optimization methods that do not require the gradient of the problem to be optimized and RS can hence be used on functions that are not continuous or differentiable...
is a related family of optimization methods that sample from general distributions, for example, a uniform distribution on the unitUnit sphereIn mathematics, a unit sphere is the set of points of distance 1 from a fixed central point, where a generalized concept of distance may be used; a closed unit ball is the set of points of distance less than or equal to 1 from a fixed central point...
sphereHypersphereIn mathematics, an n-sphere is a generalization of the surface of an ordinary sphere to arbitrary dimension. For any natural number n, an n-sphere of radius r is defined as the set of points in -dimensional Euclidean space which are at distance r from a central point, where the radius r may be any...
. - Pattern searchPattern search (optimization)Pattern search is a family of numerical optimization methods that do not require the gradient of the problem to be optimized. Hence PS can be used on functions that are not continuous or differentiable. Such optimization methods are also known as direct-search, derivative-free, or black-box...
are used on noisy observations, especially in response surface methodologyResponse surface methodologyIn statistics, response surface methodology explores the relationships between several explanatory variables and one or more response variables. The method was introduced by G. E. P. Box and K. B. Wilson in 1951. The main idea of RSM is to use a sequence of designed experiments to obtain an...
in chemical engineeringChemical engineeringChemical engineering is the branch of engineering that deals with physical science , and life sciences with mathematics and economics, to the process of converting raw materials or chemicals into more useful or valuable forms...
. They do not require users to program gradients or hessians.