BUP-TR: Bayesian Underdetermined Projection Trust-Region Methods for Derivative-Free Optimization

Underdetermined quadratic interpolation is a standard model-construction tool in model-based derivative-free trust-region methods: it keeps the number of function evaluations manageable, but leaves many quadratic models consistent with the sampled values. Classical solvers remove this ambiguity by prescribing a norm or a model-change measure, such as the least-Frobenius Hessian update in Powell-type methods. We propose BUP-TR (Bayesian Underdetermined Projection Trust-Region), which replaces this prescribed completion rule by a prior-regularized one. At each iteration, the interpolation equations are imposed as exact constraints, and the model is chosen as the maximum-a-posteriori (MAP) element of the affine family of interpolating quadratics, equivalently as the projection of a prior model onto this family in the norm defined by the precision matrix. The precision matrix used in this completion also defines a geometry test for the interpolation set, leading to MAP-poisedness and a corresponding repair procedure. Under standard smoothness, geometry, and prior-accuracy assumptions, the hard-MAP models are fully linear, and the resulting trust-region method attains global first-order convergence with O(epsilon^{-2}) evaluation complexity, including repair evaluations. A NEWUOA-style implementation, BUP-NEWUOA, improves performance under fixed evaluation budgets over NEWUOA and other standard derivative-free solvers on the test set considered.