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.