# Random optimization > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Random_optimization > Markdown URL: https://mediated.wiki/source/Random_optimization.md > Source: https://en.wikipedia.org/wiki/Random_optimization > Source revision: 1328888463 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) Optimization technique in mathematics **Random optimization (RO)** is a family of numerical [optimization](/source/Optimization_(mathematics)) methods [that do not require the gradient](/source/Derivative-free_optimization) of the optimization problem and RO can hence be used on functions that are not [continuous](/source/Continuous_function) or [differentiable](/source/Differentiable_function). Such optimization methods are also known as direct-search, derivative-free, or black-box methods. The name random optimization is attributed to Matyas [1] 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](/source/Normal_distribution) surrounding the current position. ## Algorithm See also: [Simulated annealing](/source/Simulated_annealing) Let f : R n → R {\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} } be the fitness or cost function which must be minimized. Let x ∈ R n {\displaystyle x\in \mathbb {R} ^{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](/source/Normal_distribution) 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](/source/Evolution_strategy) with constant step-size. ## Convergence and variants Matyas showed the basic form of RO converges to the optimum of a simple [unimodal function](/source/Unimodal_function) by using a [limit-proof](/source/Limit_(mathematics)) 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 [2] and Solis and Wets [3] to establish that convergence to a region surrounding the optimum is inevitable under some mild conditions for RO variants using other [probability distributions](/source/Probability_distribution) for the sampling. An estimate on the number of iterations required to approach the optimum is derived by Dorea.[4] These analyses are criticized through empirical experiments by Sarma [5] 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](/source/Random_search) is a closely related family of optimization methods which sample from a [hypersphere](/source/Hypersphere) instead of a normal distribution. - [Luus–Jaakola](/source/Luus%E2%80%93Jaakola) is a closely related optimization method using a [uniform distribution](/source/Uniform_distribution_(continuous)) in its sampling and a simple formula for exponentially decreasing the sampling range. - [Pattern search](/source/Pattern_search_(optimization)) takes steps along the axes of the search-space using exponentially decreasing step sizes. - [Stochastic optimization](/source/Stochastic_optimization) ## References 1. **[^](#cite_ref-matyas65random_1-0)** Matyas, J. (1965). ["Random optimization"](https://www.mathnet.ru/eng/at11288). *Automation and Remote Control*. **26** (2): 246–253. 1. **[^](#cite_ref-baba81convergence_2-0)** Baba, N. (1981). "Convergence of a random optimization method for constrained optimization problems". *Journal of Optimization Theory and Applications*. **33** (4): 451–461. [doi](/source/Doi_(identifier)):[10.1007/bf00935752](https://doi.org/10.1007%2Fbf00935752). 1. **[^](#cite_ref-solis81random_3-0)** Solis, Francisco J.; [Wets, Roger J.-B.](/source/Roger_J-B_Wets) (1981). "Minimization by random search techniques". *[Mathematics of Operations Research](/source/Mathematics_of_Operations_Research)*. **6** (1): 19–30. [doi](/source/Doi_(identifier)):[10.1287/moor.6.1.19](https://doi.org/10.1287%2Fmoor.6.1.19). 1. **[^](#cite_ref-dorea83expected_4-0)** Dorea, C.C.Y. (1983). "Expected number of steps of a random optimization method". *Journal of Optimization Theory and Applications*. **39** (3): 165–171. [doi](/source/Doi_(identifier)):[10.1007/bf00934526](https://doi.org/10.1007%2Fbf00934526). 1. **[^](#cite_ref-sarma90convergence_5-0)** Sarma, M.S. (1990). "On the convergence of the Baba and Dorea random optimization methods". *Journal of Optimization Theory and Applications*. **66** (2): 337–343. [doi](/source/Doi_(identifier)):[10.1007/bf00939542](https://doi.org/10.1007%2Fbf00939542). v t e Major subfields of optimization Convex programming Fractional programming Integer programming Quadratic programming Nonlinear programming Stochastic programming Robust optimization Combinatorial optimization Infinite-dimensional optimization Metaheuristics Constraint satisfaction Multiobjective optimization Simulated annealing --- Adapted from the Wikipedia article [Random optimization](https://en.wikipedia.org/wiki/Random_optimization) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Random_optimization?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.