NEWUOA is an advanced trust-region method that builds underdetermined quadratic models using fewer interpolation points than UOBYQA. Developed by M.J.D. Powell as an improvement over UOBYQA, it uses 2n+ interpolation points instead of the full (n+)(n+2)/2, making it more efficient for higher-dimensional problems while maintaining good approimation quality.
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.
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: 2 |
š Paper |
| Reference Package |
PDO (Python Derivative-ree Optimization) Wraps Powell's original ortran implementation Authoritative implementation with numerical robustness Package: pdfo |
š¦ PDO Source |
| HumpDay Python Implementation |
Humpday Integration Calls PDO's NEWUOA implementation Standardized interface for optimization contests ile: humpday/optimizers/prima_algorithms.py |
Implementation |
| Humpday JavaScript Port |
Browser Implementation JavaScript port attempting to match PDO behavior Underdetermined quadratic model building Class: PRIMA_NEWUOA |
JS Port |
| Dependencies |
Reference: PDO package (wraps Powell's ortran) Humpday Python: pdfo, numpy Humpday JS: None (standalone port) |
š¦ PyPI |
š Performance Characteristics
- Best for: Smooth, unconstrained problems in moderate to high dimensions
- Dimensions: Particularly effective for n > where UOBYQA becomes epensive
- unction evaluations: Uses 2n+ points, more efficient than UOBYQA's (n+)(n+2)/2
- Convergence: Ecellent convergence on smooth functions
- Robustness: Handles moderate noise, good balance of eploration and eploitation
ā Validation Status: IMPLEMENTATION ISSUES
JavaScript implementation currently has errors preventing proper validation:
- Error Detected: "Pts is not defined" in JavaScript implementation
- Test Results: /3 test functions complete successfully
- PDO Reference: Working perfectly (achieves f = . on test functions)
- Required i: Variable naming and initialization issues need resolution
Latest test: 22-5-2 - JavaScript implementation needs debugging before validation possible
š Educational Resources
- NEWUOA Wikipedia
- PDO Documentation
- Powell's NEWUOA Paper (2)
- Trust Region Methods Overview
- Derivative-ree Optimization Methods
Algorithm Theory
- Interpolation Set: 2n+ points vs UOBYQA's (n+)(n+2)/2 points
- Quadratic Models: Underdetermined system solved with minimum robenius 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 > where UOBYQA becomes prohibitive
- Limited Budget: When function evaluations are very epensive
- Smooth unctions: 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+ 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