Powell-Style Model-Based Derivative-Free Optimization with Complexity Guarantees
Abstract
We propose variants of model-based trust region derivative-free algorithms that are closest to methods initially proposed and implemented by Powell. These methods rely on low degree polynomial interpolation and carefully maintain geometry of the interpolation sets. We are able to derive complexity bounds for these methods that make them theoretically competitive to other derivative-free methods. Applying these methods in randomly generated subspaces recovers what we believe to be nearly tight complexity. This paper builds on recent results where complexity of a much simplified version of Powell's methods was derived. Here, we extend the analysis to fully incorporate Powell's geometry handling approach and conduct an extensive numerical comparison of the model-based trust region methods connecting practical and theoretical performance. We also extend the analysis of subspace model-based trust region methods to the case of noisy function evaluations.
Related
- A note on the complexity of random subspace model-based methods for derivative-free optimization
- Data-Driven MPC with Adaptively Sampled Non-Expert Demonstrations: Performance Guarantees and Sample Complexity
- Certified Inference and Training for Deep Equilibrium Networks: A Continuation Framework with Polynomial Complexity Guarantees
- A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
- From Consensus-Based Optimization to Particle Swarm Optimization: Convergence Guarantees under Drift-Diffusion Coupling
BibTeX
@misc{chaudhry2026powellstyle,
title = {{Powell-Style Model-Based Derivative-Free Optimization with Complexity Guarantees}},
author = {Abraar Chaudhry and Katya Scheinberg and Scholar Sun},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09441},
eprint = {2609.09441},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09441},
}
RIS
TY - UNPB
TI - Powell-Style Model-Based Derivative-Free Optimization with Complexity Guarantees
AU - Abraar Chaudhry
AU - Katya Scheinberg
AU - Scholar Sun
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.09441
UR - https://arxiv.org/abs/2609.09441
AB - We propose variants of model-based trust region derivative-free algorithms that are closest to methods initially proposed and implemented by Powell. These methods rely on low degree polynomial interpolation and carefully maintain geometry of the interpolation sets. We are able to derive complexity bounds for these methods that make them theoretically competitive to other derivative-free methods. Applying these methods in randomly generated subspaces recovers what we believe to be nearly tight complexity. This paper builds on recent results where complexity of a much simplified version of Powell's methods was derived. Here, we extend the analysis to fully incorporate Powell's geometry handling approach and conduct an extensive numerical comparison of the model-based trust region methods connecting practical and theoretical performance. We also extend the analysis of subspace model-based trust region methods to the case of noisy function evaluations.
ER -