PRIMA_UOBYQA

Powell's full-quadratic-model trust-region method, with Steihaug-Toint TR subproblem and Powell-style geometry steps

← Back to Optimizer Competition
UOBYQA (Unconstrained Optimization BY Quadratic Approximation, Powell 2002) is a trust-region method for derivative-free optimization that builds a full quadratic model from (n+1)(n+2)/2 interpolation points. HumpDay's port uses three pieces that matter for correctness on non-quadratic objectives:
  1. Steihaug-Toint truncated CG for the trust-region subproblem — correctly handles indefinite fitted Hessians (the common case for the overdetermined regression on non-quadratic objectives).
  2. Unconditional base-point shifting at the end of every iteration so the model centre coincides with the current best.
  3. Periodic geometry step — every npt TR iterations, pick the worst-positioned interpolation point and find a step in the trust region that maximises its Lagrange polynomial. Closes the residual gap to PDFO on Rosenbrock.

Interactive 3D Visualization

See UOBYQA 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 3: heavy (~10ms/iter; full quadratic model or O(n3) eigendecomposition). Eligible when measured eval_time ≥ 1 ms.
  • Dimensional cap: n_dim ≤ 12 — needs (n+1)(n+2)/2 interpolation points.
  • Minimum trials: (n+1)(n+2)/2 + 5 — needs a full quadratic interpolation set.

Implementation Details

Component Details Links
Original Algorithm M.J.D. Powell
Trust-region method using quadratic interpolation models
Derivative-free optimization for unconstrained problems
Published: 2002 		Paper
Reference Package PDFO (Python Derivative-Free Optimization)
Wraps Powell's original Fortran implementation
Authoritative implementation with numerical robustness
Package: pdfo 		PDFO Source
HumpDay Python HumpDay PRIMA_UOBYQA
Pure-Python port: SVD-based regression on (n+1)(n+2)/2 points, Steihaug-Toint TR subproblem, periodic geometry step that maximises |Λt(x)| in the trust region.
No required dependencies.
File: humpday/optimizers/prima_algorithms.py 		Source
HumpDay JavaScript Browser PRIMA_UOBYQA
JS port shares the Steihaug-Toint TR solver but uses a different geometry-update path; bringing it into line with the Python port is tracked separately.
Class: PRIMA_UOBYQA 		JS Port

Performance characteristics

  • Best for: Smooth, low-dimensional problems where the full quadratic model gives a precise trust-region step.
  • Worst for: High dimensions — the interpolation set scales as (n+1)(n+2)/2, which becomes expensive to build and maintain past ~10 dimensions. NEWUOA's 2n+1 underdetermined model is the better choice there.
  • Per outer cycle: one TR descent step + one Steihaug-Toint solve. Every (n+1)(n+2)/2 cycles, one additional geometry-step evaluation.
  • Relative to PDFO uobyqa at n_trials=200, n_dim=2: matches reference on sphere, Rosenbrock, and Ackley — all three at the numerical noise floor. See SOTA status for the live numbers.

Educational Resources