Random optimization (RO) is a family of numerical
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
methods that do not require the
gradient
In vector calculus, the gradient of a scalar-valued differentiable function of several variables is the vector field (or vector-valued function) \nabla f whose value at a point p is the "direction and rate of fastest increase". If the gradi ...
of the problem to be optimized and RO can hence be used on functions that are not
continuous
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous ...
or
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 its ...
. Such optimization methods are also known as direct-search, derivative-free, or black-box methods.
The name random optimization is attributed to Matyas
[ who made an early presentation of RO along with basic mathematical analysis. RO works by iteratively moving to better positions in the search-space which are sampled using e.g. a ]normal distribution
In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is
:
f(x) = \frac e^
The parameter \mu ...
surrounding the current position.
Algorithm
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 basic RO algorithm can then be described as:
* Initialize x with a random position in the search-space.
* Until a termination criterion is met (e.g. number of iterations performed, or adequate fitness reached), repeat the following:
** Sample a new position y by adding a normally distributed random vector to the current position x
** If (''f''(y) < ''f''(x)) then move to the new position by setting x = y
* Now x holds the best-found position.
This algorithm corresponds to a (1+1) evolution strategy
In computer science, an evolution strategy (ES) is an optimization technique based on ideas of evolution. It belongs to the general class of evolutionary computation or artificial evolution methodologies.
History
The 'evolution strategy' optimizat ...
with constant step-size.
Convergence and variants
Matyas showed the basic form of RO converges to the optimum of a simple unimodal function
In mathematics, unimodality means possessing a unique mode. More generally, unimodality means there is only a single highest value, somehow defined, of some mathematical object.
Unimodal probability distribution
In statistics, a unimodal pr ...
by using a limit-proof which shows convergence to the optimum is certain to occur if a potentially infinite number of iterations are performed. However, this proof is not useful in practice because a finite number of iterations can only be executed. In fact, such a theoretical limit-proof will also show that purely random sampling of the search-space will inevitably yield a sample arbitrarily close to the optimum.
Mathematical analyses are also conducted by Baba [ and Solis and Wets ][ to establish that convergence to a region surrounding the optimum is inevitable under some mild conditions for RO variants using other ]probability distribution
In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...
s for the sampling. An estimate on the number of iterations required to approach the optimum is derived by Dorea.[ These analyses are criticized through empirical experiments by Sarma ][ who used the optimizer variants of Baba and Dorea on two real-world problems, showing the optimum to be approached very slowly and moreover that the methods were actually unable to locate a solution of adequate fitness, unless the process was started sufficiently close to the optimum to begin with.
]
See also
* Random search Random search (RS) 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. Such optimization methods are also k ...
is a closely related family of optimization methods which sample from a hypersphere
In mathematics, an -sphere or a hypersphere is a topological space that is homeomorphic to a ''standard'' -''sphere'', which is the set of points in -dimensional Euclidean space that are situated at a constant distance from a fixed point, cal ...
instead of a normal distribution.
* Luus–Jaakola 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 generate ...
is a closely related optimization method using a uniform distribution in its sampling and a simple formula for exponentially decreasing the sampling range.
* Pattern search takes steps along the axes of the search-space using exponentially decreasing step sizes.
* Stochastic optimization
Stochastic optimization (SO) methods are optimization methods that generate and use random variables. For stochastic problems, the random variables appear in the formulation of the optimization problem itself, which involves random objective funct ...
References
{{DEFAULTSORT:Random Optimization
Optimization algorithms and methods