Luus–Jaakola
   HOME

TheInfoList



OR:

In
computational engineering Computational Engineering is an emerging discipline that deals with the development and application of computational models for engineering, known as Computational Engineering Models or CEM. Computational engineering uses computers to solve eng ...
, Luus–Jaakola (LJ) denotes a
heuristic A heuristic or heuristic technique (''problem solving'', '' mental shortcut'', ''rule of thumb'') is any approach to problem solving that employs a pragmatic method that is not fully optimized, perfected, or rationalized, but is nevertheless ...
for
global Global may refer to: General *Globe, a spherical model of celestial bodies *Earth, the third planet from the Sun Entertainment * ''Global'' (Paul van Dyk album), 2003 * ''Global'' (Bunji Garlin album), 2007 * ''Global'' (Humanoid album), 198 ...
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
of a real-valued function. In engineering use, LJ is not an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
that terminates with an optimal solution; nor is it an
iterative method In computational mathematics, an iterative method is a Algorithm, mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''i''-th approximation (called an " ...
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 In numerical analysis, the Newton–Raphson method, also known simply as Newton's method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a ...
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 or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytop ...
nor
differentiable In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non- vertical tangent line at each interior point in ...
nor locally Lipschitz: The LJ heuristic does not use a
gradient In vector calculus, the gradient of a scalar-valued differentiable function f of several variables is the vector field (or vector-valued function) \nabla f whose value at a point p gives the direction and the rate of fastest increase. The g ...
or
subgradient In mathematics, the subderivative (or subgradient) generalizes the derivative to convex functions which are not necessarily differentiable. The set of subderivatives at a point is called the subdifferential at that point. Subderivatives arise in c ...
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 Optimal control theory is a branch of control theory that deals with finding a control for a dynamical system over a period of time such that an objective function is optimized. It has numerous applications in science, engineering and operations ...
, transformer design, metallurgical processes, and
chemical engineering Chemical engineering is an engineering field which deals with the study of the operation and design of chemical plants as well as methods of improving production. Chemical engineers develop economical commercial processes to convert raw materials ...
.


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: \mathbb^n \rarr \mathbb be the fitness or cost function which must be minimized. Let \textbf \isin \mathbb^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 A uniform is a variety of costume worn by members of an organization while usually participating in that organization's activity. Modern uniforms are most often worn by armed forces and paramilitary organizations such as police, emergency serv ...
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. * 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. For this class of problems, Newton's method is the usual optimization method, and it has
quadratic convergence In mathematical analysis, particularly numerical analysis, the rate of convergence and order of convergence of a sequence that converges to a limit are any of several characterizations of how quickly that sequence approaches its limit. These are ...
(''regardless of the dimension'' of the space, which can be a
Banach space In mathematics, more specifically in functional analysis, a Banach space (, ) is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the computation of vector length and distance between vectors and ...
, 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 n the number of iterations needed to reach an approximate solution of a given accuracyas he number of dimensions increases to infinityshows 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 onclusionholds for ... problems generated by uni-extremal hat is, unimodal(but not convex) functions." Page 7 summarizes the later discussion of .
When applied to twice continuously differentiable problems, the LJ heuristic's rate of convergence decreases as the number of dimensions increases.


See also

*
Random optimization Random optimization (RO) is a family of numerical optimization methods that do not require the gradient of the optimization problem and RO can hence be used on functions that are not continuous or differentiable. Such optimization methods are als ...
is a related family of optimization methods that sample from general distributions, for example the uniform distribution. *
Random search Random search (RS) is a family of numerical optimization methods that do not require the gradient of the optimization problem, and RS can hence be used on functions that are not continuous or differentiable. Such optimization methods are also kno ...
is a related family of optimization methods that sample from general distributions, for example, a uniform distribution on the unit
sphere A sphere (from Ancient Greek, Greek , ) is a surface (mathematics), surface analogous to the circle, a curve. In solid geometry, a sphere is the Locus (mathematics), set of points that are all at the same distance from a given point in three ...
. * Pattern search are used on noisy observations, especially in response surface methodology in
chemical engineering Chemical engineering is an engineering field which deals with the study of the operation and design of chemical plants as well as methods of improving production. Chemical engineers develop economical commercial processes to convert raw materials ...
. They do not require users to program gradients or hessians.


References

{{DEFAULTSORT:Luus-Jaakola Optimization algorithms and methods Heuristic algorithms