Pattern Search (Hooke-Jeeves)

Exploratory move + pattern move, with restart on multimodal landscapes

← Back to Optimizer Competition
Pattern Search in HumpDay is the classical Hooke-Jeeves algorithm (1961). Each cycle does an exploratory move — try ±step on each axis, keep first improvement per coordinate — followed by a pattern move that extrapolates from the previous base point through the new exploratory point. A second exploratory move from the pattern point either confirms the pattern (accept it) or falls back to the bare exploratory move. The step is halved after sweeps with no improvement.

HumpDay's pattern search at a glance

  • Exploratory move: try ±step on each coordinate, keep first improvement per axis.
  • Pattern move: if the exploratory improved, extrapolate new_base = clip(x + (x - base)) and re-explore.
  • Step halving: failed sweep ⇒ halve the step.
  • Restart on multimodal trapping: when step ≤ 1e-6 with f > 1e-8, reinitialise from a random base. On smooth basins the run exits naturally before the restart fires.
  • Initial step 0.1, floor 1e-12, on the unit cube [0, 1]n.

Interactive 3D Visualization

See Pattern Search in action on 3D optimization surfaces:

Loading 3D visualization...

Requires WebGL support

Instructions: Choose a test function and algorithm, then click Start to watch the step-by-step optimization process.

Auto-selection metadata. Consulted by humpday.minimize() when picking a default algorithm.
  • Overhead tier 1: light (~100µs/iter). Eligible when measured eval_time ≥ 10 µs.
  • Dimensional cap: n_dim ≤ 30 — 2n directions per pattern.
  • Minimum trials: 10 — baseline minimum.

Implementation Details

Component Details Links
Algorithm Hooke-Jeeves direct search (1961)
Exploratory move + pattern move; step halved on failed sweeps.
One of the earliest published derivative-free methods.
Reference: Hooke & Jeeves (1961), "'Direct search' solution of numerical and statistical problems", J. ACM 8(2) 		Original Paper DFO Book
Reference Implementation MATLAB Global Optimization Toolbox
patternsearch() function with multiple pattern types
Also available in specialized direct search packages
Reference: MATLAB/Octave implementations 		MATLAB Docs
HumpDay Python HumpDay PatternSearch
Faithful Hooke-Jeeves: exploratory + pattern move, step halved on failed sweep, restart on multimodal trapping.
Pure Python; no required dependencies.
File: humpday/optimizers/search_algorithms.py 		Source
HumpDay JavaScript Browser PatternSearch
Mirrors the Python port. Used in the contest and the in-browser visualizer.
Class: PatternSearch 		JS Port

Performance characteristics

  • Best for: Smooth, low-dimensional black-box objectives where the pattern move can race along a valley.
  • Worst for: Highly multimodal landscapes (Ackley) where Hooke-Jeeves traps in local basins. HumpDay's restart trigger softens this but doesn't eliminate it — Hooke-Jeeves is local, not global.
  • Dimensions: Each exploratory sweep is O(n_dim) evaluations; pattern move adds one more per cycle.
  • Relative to a textbook Hooke-Jeeves reference at n_trials=200, n_dim=2: ties on Rosenbrock; the restart trigger leaves a small precision gap on sphere and Ackley (see SOTA status).

Educational Resources

Algorithm Components

  • Mesh: Discrete set of points where function is evaluated
  • Pattern: Set of directions defining search pattern
  • Polling: Systematic evaluation of pattern points
  • Mesh Refinement: Decrease mesh size when no improvement found
  • Mesh Coarsening: Increase mesh size after successful iterations

Pattern Types

  • Coordinate Patterns: ±eᵢ directions (axis-aligned)
  • Maximal Basis: 2n directions ensuring positive spanning
  • Minimal Basis: n+1 directions forming simplex
  • GPS Patterns: Generalized pattern search conforming patterns
  • Custom Patterns: Problem-specific direction sets

️ Pattern Search Variants

  • Hooke-Jeeves: Exploratory + pattern moves
  • Coordinate Search: Simple alternating coordinate directions
  • GPS (Generalized Pattern Search): Theoretical framework
  • MADS (Mesh Adaptive Direct Search): Dense direction sets
  • GSS (Generating Set Search): Positive basis guarantee

Convergence Theory

  • Clarke Stationarity: GPS converges to Clarke stationary points
  • Mesh Size Limit: lim inf Δₘ = 0 under standard conditions
  • Sufficient Decrease: Armijo-like conditions for step acceptance
  • Positive Spanning: Pattern directions must positively span ℝⁿ

Applications

  • Engineering Design: When objective function has discontinuities
  • Simulation Optimization: Noisy, expensive function evaluations
  • Control System Tuning: Parameter optimization with constraints
  • Financial Modeling: Portfolio optimization with discrete constraints
  • Environmental Modeling: Parameter estimation in climate models

️ Implementation Details

  • Initial Mesh Size: Δ₀ typically 1.0 or problem-scaled
  • Mesh Expansion: Δₖ₊₁ = τΔₖ where τ > 1 (often τ = 2)
  • Mesh Contraction: Δₖ₊₁ = Δₖ/τ when no improvement
  • Polling Order: Opportunistic vs complete polling
  • Termination: Δₖ < tolerance or max evaluations

When to Use Pattern Search

  • Discontinuous Objectives: Traditional methods fail on non-smooth functions
  • Expensive Evaluations: Systematic exploration reduces waste
  • Constrained Problems: Natural handling of bound constraints
  • Black-Box Functions: No gradient or Hessian information available
  • Integer Variables: Can be adapted for mixed-integer problems