Mustersuchen

Mustersuchen, in optimization literature often called pattern search, is a class of derivative-free optimization algorithms. It aims to minimize or maximize an objective function using only objective evaluations, without explicit gradient information.

The method proceeds iteratively. From a current point x, a predefined pattern of trial points is generated around x, typically by moving along coordinate directions or along a symmetric base. Each trial is evaluated; if a trial improves the objective, the current point is replaced by that trial and the pattern may be expanded or the stepsize increased. If no trial yields improvement, the stepsize or mesh size is reduced and a new set of trials is generated.

Variants include the original Hooke–Jeeves pattern search, and more modern mesh-adaptive direct search (MADS) frameworks, which provide convergence guarantees under certain conditions. Many implementations use constraints handling via projection, penalty methods, or feasible-region search, and may incorporate restarts or filtering to escape poor basins.

Applications are common in engineering and applied sciences where objective evaluations come from simulations that are expensive or noisy, or where derivatives are unavailable. Strengths include simplicity, robustness to non-smoothness, and applicability to black-box functions. Limitations include potential slow convergence in high-dimensional problems and sensitivity to the choice of pattern and tuning parameters.

See also: derivative-free optimization, Hooke–Jeeves method, MADS.