Random optimization is a family of numerical 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....

 methods that do not require the 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....

 of the problem to be optimized and RO can hence be used on functions that are not continuous

Continuous function

In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...

 or differentiable. 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 surrounding the current position.

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 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.

Convergence and variants

Matyas showed the basic form of RO converges to the optimum of a simple unimodal function by using a limit-proof

Limit (mathematics)

In mathematics, the concept of a "limit" is used to describe the value that a function or sequence "approaches" as the input or index approaches some value. The concept of limit allows mathematicians to define a new point from a Cauchy sequence of previously defined points within a complete metric...

 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 practise 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

Probability distribution

In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....

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
  Random 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 closely related family of optimization methods which sample from a hypersphere
  Hypersphere
  In 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...
  
   instead of a normal distribution.
• Luus–Jaakola
  Luus–Jaakola
  In computational engineering, Luus–Jaakola 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...
  
   is a closely related optimization method 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...
  
   in its sampling and a simple formula for exponentially decreasing the sampling range.
• Pattern search
  Pattern 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...
  
   takes steps along the axes of the search-space using exponentially decreasing step sizes.
• Stochastic optimization
  Stochastic optimization
  Stochastic optimization 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 involve random objective functions or random constraints, for example. Stochastic...