NEWUOA (PDFO)

New Unconstrained Optimization by Quadratic Approximation

← Back to Optimizer Competition
NEWUOA (Powell, 2006) is a trust-region method for derivative-free optimization that builds underdetermined quadratic models from 2n + 1 interpolation points (compared to UOBYQA's full (n+1)(n+2)/2). The underdetermination is resolved by Powell's minimum-Frobenius-norm update: pick the Hessian closest in Frobenius norm to the previous Hessian, subject to the interpolation constraints. This lets NEWUOA capture cross-coupling (e.g., Rosenbrock's (b − a2)2 term) despite using only 2n + 1 points. HumpDay's PRIMA_NEWUOA implements the min-Frobenius update directly, with a dogleg trust-region step and unconditional base-point shifting.

HumpDay's NEWUOA at a glance

  • Interpolation set: npt = 2·n + 1 points. Initial design: base point + ±ρ along each coordinate.
  • Model fit: minimum-Frobenius-norm Hessian update (Powell's recipe) — keeps H as close as possible to the previous Hessian, subject to the interpolation constraints.
  • Trust-region step: dogleg path (Cauchy → Newton).
  • Geometry: furthest-from-new-position replacement for the interpolation set.
  • Base-point shifting: unconditional at the end of each iteration, so XPT[kopt] ≈ 0 at the start of every model fit.

Interactive 3D Visualization

See NEWUOA 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 ≤ 25 — underdetermined quadratic model fit.
  • Minimum trials: 2n + 5 — needs an underdetermined quadratic model fit.

Implementation Details

Component Details Links
Original Algorithm M.J.D. Powell
Underdetermined quadratic models with trust regions
Improved efficiency over UOBYQA for higher dimensions
Published: 2004 		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_NEWUOA
Pure-Python port: minimum-Frobenius-norm Hessian update on a 2n + 1-point interpolation set, dogleg trust-region step, furthest-from-new-position geometry, unconditional base-point shifting.
No required dependencies.
File: humpday/optimizers/prima_algorithms.py 		Source
HumpDay JavaScript Browser PRIMA_NEWUOA
Mirrors the Python port.
Class: PRIMA_NEWUOA 		JS Port

Performance Characteristics

  • Best for: Smooth, unconstrained problems in moderate to high dimensions. The 2n+1-point design scales better than UOBYQA's full-quadratic and the min-Frobenius update keeps the model curvature informative.
  • Worst for: Multimodal landscapes — like all PRIMA algorithms, NEWUOA is a local trust-region method.
  • Per iteration: one TR step + one evaluation. Each iteration also requires a small linear-algebra solve for the min-Frobenius Hessian update.
  • Relative to PDFO NEWUOA at n_trials=200, n_dim=2: matches reference across sphere, Rosenbrock, and Ackley. See SOTA status for the live numbers.

Educational Resources

Algorithm Theory

  • Interpolation Set: 2n+1 points vs UOBYQA's (n+1)(n+2)/2 points
  • Quadratic Models: Underdetermined system solved with minimum Frobenius norm
  • Trust Region: Adaptive radius based on model agreement
  • Lagrange Basis: Efficient update of interpolation functions
  • Geometry Improvement: Automatic point replacement for better conditioning

️ NEWUOA vs UOBYQA Trade-offs

  • Efficiency: NEWUOA scales better - O(n) vs O(n²) interpolation points
  • Model Quality: UOBYQA has fully determined models, NEWUOA underdetermined
  • Memory: NEWUOA uses less memory for high dimensions
  • Accuracy: UOBYQA may be more precise on low-dimensional smooth problems
  • Dimension Limit: NEWUOA practical for much higher dimensions

When to Use NEWUOA

  • High Dimensions: n > 10 where UOBYQA becomes prohibitive
  • Limited Budget: When function evaluations are very expensive
  • Smooth Functions: Continuous, differentiable (but derivatives unknown)
  • Unconstrained: No bounds or constraints (use BOBYQA for bounds)
  • Global Search: Combined with multi-start for global optimization

Implementation Details

  • Initial Geometry: 2n+1 points around starting point
  • Model Building: Minimum norm solution for underdetermined system
  • Trust Region Subproblem: Dogleg or conjugate gradient methods
  • Point Replacement: Replace worst-conditioned points
  • Convergence: Trust region radius and gradient norm criteria