Does pattern search estimate a gradient?

The basic polling approach can operate without constructing one, although hybrid methods may add other information.

Are trial points always random?

No. Basic generalized pattern search can use fixed directions; other variants generate changing or randomized directions.

Can it handle constraints?

Suitable variants can, but simply ignoring invalid points is not a complete general treatment of every nonlinear constraint problem.

AI Glossary / Mathematics and optimization / Intermediate

Pattern search (optimization)

Definition

Pattern search is a family of derivative-free optimization methods that look for better solutions by evaluating an objective function at a structured set of nearby points. The method moves when it finds an improvement and refines its search scale when it does not. Here, pattern refers to directions used to generate trial points, not to recognizing patterns in images, text or customer behavior.

What it means

An objective function assigns a score or cost to each candidate setting. Sometimes that function is available only through a simulator, a legacy program or an experiment, and reliable derivatives are difficult to obtain. Pattern search can work with function values directly. It remains an optimization method with assumptions and limitations: derivative-free does not mean evaluation-free, globally optimal or automatically reliable on arbitrary noisy data. Generalized pattern search, generating set search and mesh adaptive direct search are related approaches with different direction rules and convergence analyses.

How it works

Begin with a feasible point, a search scale and a suitable collection of directions. In a basic two-variable coordinate pattern, try positive and negative moves along each axis. A poll evaluates candidate points formed by adding scaled directions to the current point. An opportunistic poll stops at the first acceptable improvement; a complete poll evaluates the full set before choosing an improving candidate. If the poll fails, keep the current point and reduce the scale. Successful steps may enlarge or retain it, depending on the algorithm. Some implementations add an optional broader search step before polling. Constraints, scaling and sufficient-decrease rules must be handled according to the chosen variant.

Three practical examples

A simulation team can tune a few continuous equipment settings when each trial returns a cost but no usable gradient.
A signal-processing workflow can adjust filter parameters against a deterministic validation objective while respecting parameter bounds.
A machine-learning experiment can use pattern search for a small set of continuous hyperparameters, provided evaluation noise and validation reuse are controlled. It is not automatically the right tool for categorical choices or millions of model weights.

Think of it this way

Think of exploring a dark room by taking measured steps north, south, east and west while an instrument reports whether conditions improved. When large steps no longer help, try smaller ones. The analogy captures local probing, but a mathematically sound direction set and update rules matter; arbitrary wandering with smaller steps does not inherit a pattern-search convergence theorem.

Worked example

Minimize f(x, y) = (x − 1.3)² + (y + 0.7)². Start at (0, 0), where f = 2.18, and use a complete coordinate poll with step size one. The four candidates have values f(1, 0) = 0.58, f(−1, 0) = 5.78, f(0, 1) = 4.58 and f(0, −1) = 1.78. Choose (1, 0). For this illustrative rule, retain the step size after success. Its next poll finds (1, −1), with value 0.18. At that point, the unit-step candidates have values 0.58, 1.78, 0.58 and 1.78, so none improves the current value. Keep (1, −1) and halve the step to 0.5. Now (1.5, −1) has value 0.13, as does (1, −0.5); either is an improving choice under a stated tie rule. The failed unit poll did not prove optimality: the exact minimum is zero at (1.3, −0.7). The example shows why scale refinement matters and uses an explicit update rule rather than implying every implementation follows these exact steps.

Illustrative case study

In a fictional project, Hazel Process adjusts two simulator settings to reduce modeled energy consumption. An analytic gradient is unavailable, so the team tests a pattern-search method. It rescales the settings because one is measured in thousands and the other in small fractions, then logs every evaluation and constraint violation. When repeated runs return slightly different costs, it investigates simulator randomness before interpreting tiny improvements. The case illustrates preparation and diagnostics without claiming a measured energy saving or presenting a local candidate as a globally certified design.

Common misconceptions and mistakes

Derivative-free methods can still require many expensive evaluations. A failed poll means that the tested points did not improve the objective at that scale; it is not a universal statement about all nearby or distant points. A small mesh or exhausted evaluation budget is a stopping condition, not a certificate of global optimality. Convergence claims depend on the algorithm and conditions such as regularity, direction coverage and constraint treatment. Measurement noise can make an apparent improvement misleading. Also, a method marketed within a global optimization toolbox does not thereby guarantee discovery of the global minimum in every run.

Business use

Use pattern search when function evaluations are available, the number of adjustable variables is manageable and derivative-based alternatives are impractical or unreliable. Define the evaluation budget and meaningful improvement threshold before starting. Normalize variables or select scales consistent with their physical ranges. Recheck the final candidate with an independent simulation run or assessment dataset, especially when the search repeatedly evaluates the same validation data. Consider multiple starts when different basins matter, while recognizing that this increases cost and still does not prove global optimality. Report the returned objective, feasibility and termination reason together.

Check your understanding

No unit-step trial improves the objective, but a half-step trial does. Was the original point a confirmed minimum?

Answer: No. The unsuccessful poll only described the tested scale and directions. Refining the scale revealed a better point.

Related terms

Derivative-free optimization
direct search
mesh adaptive direct search
coordinate search
black-box optimization
local minimum

Learn next

implement the worked complete poll and then switch to stopping at the first improvement. Compare the number of objective evaluations and the resulting path, keeping the same starting point and update rules. Add bounded variables and document how candidate feasibility is enforced.

Sources

Sources: MathWorks, How Pattern Search Polling Works, https://www.mathworks.com/help/gads/how-pattern-search-polling-works.html ; Pattern Search Terminology, https://www.mathworks.com/help/gads/pattern-search-terminology.html ; Searching and Polling, https://www.mathworks.com/help/gads/searching-and-polling.html . The quadratic example and fictional simulator project are original illustrations, with update choices stated explicitly.

Previous: Pattern recognition Next: Pattern theory