BOBYQA (PDFO)

Bound constrained Optimization BY Quadratic Approximation

← Back to Optimizer Competition
BOBYQA (Bound Optimization BY Quadratic Approximation; Powell, 2009) is a trust-region method that extends NEWUOA with explicit handling of simple bound constraints li ≤ xi ≤ ui. Like NEWUOA it uses a 2n + 1-point underdetermined interpolation set with the minimum-Frobenius-norm Hessian update, but the trust-region subproblem is solved within the active bound set (the "TRSBOX" subroutine in Powell's original Fortran). HumpDay's PRIMA_BOBYQA ports the algorithm directly with a bound-aware Cauchy/dogleg TR step and a finite-difference gradient fallback when the regression is rank-deficient.

HumpDay's BOBYQA at a glance

  • Bounds: the unit cube [0, 1]n. Initial points are placed inside the cube (not on the boundary).
  • Interpolation set: npt = 2·n + 1 with the min-Frobenius Hessian update.
  • Trust-region step: bound-aware Cauchy / dogleg; projects step components that would push x past an active bound.
  • Fallback: finite-difference gradient when the regression is rank-deficient.

Interactive 3D Visualization

See BOBYQA 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 2: medium (~1ms/iter; small linear-algebra updates). Eligible when measured eval_time ≥ 100 µs.
  • Dimensional cap: n_dim ≤ 30 — geometry/BIGLAG steps make each call take minutes past n=30.
  • Minimum trials: 2n + 5 — needs an underdetermined quadratic model fit.

Implementation Details

Component Details Links
Original Algorithm M.J.D. Powell
Trust-region method for bound-constrained problems
Extends NEWUOA with explicit bound handling
Published: 2009 		Paper
Reference Package PDFO (Python Derivative-Free Optimization)
Wraps Powell's original Fortran BOBYQA implementation
Handles bound constraints with numerical precision
Package: pdfo 		PDFO Source
HumpDay Python HumpDay PRIMA_BOBYQA
Pure-Python port: min-Frobenius Hessian update on 2n + 1 points, bound-aware TR step, FD-gradient fallback.
No required dependencies.
File: humpday/optimizers/prima_algorithms.py 		Source
HumpDay JavaScript Browser PRIMA_BOBYQA
Mirrors the Python port (rewritten in PR #83 to match Python's FD-gradient fallback).
Class: PRIMA_BOBYQA 		JS Port

Performance Characteristics

  • Best for: Smooth, bound-constrained problems — especially when the optimum is near a face of the cube where bound handling matters.
  • Worst for: Multimodal landscapes — like all PRIMA algorithms, BOBYQA is a local trust-region method.
  • Per iteration: one TR step + one evaluation. Bounds projected on both the step direction and the candidate point.
  • Relative to Py-BOBYQA at n_trials=200, n_dim=2: matches reference on sphere and Ackley, with a tiny gap on Rosenbrock. See SOTA status for the live numbers.

Educational Resources