Model Construction for Convex-Constrained Derivative-Free Optimization

We develop a new approximation theory for linear and quadratic interpolation models, suitable for use in convex-constrained derivative-free optimization (DFO). Most existing model-based DFO methods for constrained problems assume the ability to construct sufficiently accurate approximations via interpolation, but the standard notions of accuracy (designed for unconstrained problems) may not be achievable by only sampling feasible points, and so may not give practical algorithms. In this work, we demonstrate that linear regression models and underdetermined quadratic interpolation models (in the minimum Frobenius sense) can be made sufficiently accurate (in a sense appropriate for convex-constrained problems) using only feasible points. For the underdetermined quadratic interpolation case, we provide a simple procedure for constructing such feasible interpolation sets, providing a theoretical basis for practical and strictly feasible methods for constrained DFO.