Does the objective need to be random?

No. The proposal process can be random while every objective evaluation is deterministic.

Will Gaussian proposals eventually try the exact optimum?

In continuous spaces, hitting one exact point has probability zero under an ordinary continuous proposal distribution; convergence concerns approaching suitable neighborhoods or objective values.

Can the method leave a local basin?

A sufficiently large proposal can land in a better basin, but its probability may be too small to be useful within the available budget.

AI Glossary / Mathematics and optimization / Intermediate

Random optimization

Definition

Random optimization is an optimization approach that proposes random changes to a current solution and uses objective evaluations to decide whether to accept them. In the specific classical method associated with Mátyáš, random perturbations, commonly Gaussian, are drawn around the current point and improving candidates are retained. The phrase is also used more broadly, so the proposal rule and acceptance rule should always be stated.

What it means

The method requires a way to score candidate settings but does not require a supplied gradient. Its randomness lies in where it searches; the objective itself may be completely deterministic. This is different from optimizing a problem whose costs are inherently uncertain, although the two can occur together. Unlike blind random sampling across a fixed domain, localized random optimization centers new proposals on the current retained solution. It therefore uses some information from earlier evaluations while preserving the possibility of proposing movement in many directions.

How it works

Choose an initial feasible point and a perturbation distribution with scales appropriate to the variables. Draw a random vector, add it to the current point and handle any constraint violation according to a specified rule, such as resampling. Evaluate the candidate. For the basic minimizing version, accept it only if its objective is lower; otherwise retain the current point. Repeat within an evaluation budget. Gaussian proposals have unbounded support before constraint handling, but large jumps may be extremely unlikely. Adaptive step scales, restarts and alternative acceptance rules create variants whose theoretical behavior must be assessed separately. A deterministic seed supports reproducibility of pseudorandom proposals, not a guarantee of solution quality.

Three practical examples

A simulator can expose a few continuous settings and a deterministic cost, allowing random optimization to serve as a simple derivative-free baseline.
An audio-processing experiment can perturb continuous filter parameters and retain settings that improve a fixed comparison score.
A model-tuning study can compare locally centered random proposals with independent sampling from a predefined hyperparameter domain. These uses need explicit evaluation budgets and validation procedures; a random search path does not remove the possibility of overfitting a repeatedly used score.

Think of it this way

Think of trying small, randomly chosen adjustments to a device and keeping only changes that improve its measured performance. The analogy captures proposing and accepting moves. It does not imply that every adjustment must be small, that rejected trials teach a full model of the device, or that a finite sequence of improvements reaches the best possible setting.

Worked example

Minimize f(x) = (x − 2)² on the interval [0, 5], starting at x = 0 with objective 4. Use Gaussian perturbations with standard deviation one and resample any proposal outside the interval. Suppose an illustrative sequence of rounded perturbations is +0.8, −0.3, +0.9 and +0.6. The first candidate is 0.8, with objective 1.44, so accept it. The next candidate is 0.5, with objective 2.25, so reject it and remain at 0.8. The third candidate is therefore 1.7, not 1.4; its objective is 0.09, so accept it. The fourth candidate is 2.3, also with objective 0.09 in exact arithmetic. Under a strict-improvement rule, reject the tie and retain 1.7. The retained score has decreased from 4 to 0.09, but the known optimum at 2 has value zero. These chosen rounded proposals illustrate bookkeeping; they are not claimed to be outputs from a particular random seed or a statistical performance experiment.

Illustrative case study

In a fictional project, Willow Simulation uses random optimization as a baseline for tuning a small control model. The team runs multiple seeds with the same evaluation budget, records the distribution of final costs and compares against a structured search method. When a noisy simulator occasionally makes a poor candidate look better, the analysts introduce a justified evaluation procedure and reassess the comparison. The case illustrates experimental discipline without claiming that the random method is universally effective or that one lucky run establishes superiority.

Common misconceptions and mistakes

Randomness does not automatically confer a global-optimality guarantee within a practical budget. Asymptotic convergence results depend on conditions such as continuity, domain properties and the exact proposal mechanism. Shrinking the proposal scale changes those conditions and may make distant regions effectively inaccessible. Accepting only improvements differs from simulated annealing, which can accept worsening moves under its rule. A decreasing recorded objective does not prove that the true objective decreases when evaluations are noisy. Finally, random optimization is not the same as stochastic gradient descent: the basic method does not estimate or follow a gradient merely because it uses random numbers.

Business use

Use it as a transparent baseline or a candidate method when evaluations are available and derivatives are inconvenient. Define variable scales, feasible bounds, tie handling and stopping rules before comparing results. Count objective evaluations rather than only accepted steps, because rejected proposals still consume resources. Report variability across seeds and retain the best candidate under a stated selection procedure. Reevaluate a final candidate independently if measurement noise or validation reuse could bias its score. Where an evaluation is costly, consider whether a method that learns more from each observation would justify its additional complexity.

Check your understanding

A proposal is rejected at x = 0.8. Should the next perturbation be added to the rejected candidate?

Answer: No. In the basic method, the current point remains 0.8, so the next proposal is centered there.

Related terms

Derivative-free optimization
Hill climbing
Simulated annealing
random search
Gaussian proposal
stochastic optimization

Learn next

implement the worked accept-or-reject process and compare several proposal scales across many seeds. Plot best objective against evaluation count. Then add controlled observation noise and examine how often the retained measured improvement fails to improve the underlying deterministic objective.

Sources

Sources: James C. Spall, Stochastic Optimization, localized random search section, author-hosted chapter, https://www.jhuapl.edu/SPSA/Comp_Stat_handbook_2nd-edition_Spall.pdf ; Mátyáš, Random Optimization, original publication record, https://www.mathnet.ru/eng/at11288 . The original record's abstract was retrieved through search; its full text was not accessible. The scalar proposal sequence and fictional study are original examples.

Previous: Random neural network Next: Random perturbation