Avoiding Geometry Improvement in Derivative-Free Model-Based Methods via Randomization

We present a technique for model-based derivative-free optimization called \emph{basis sketching}. Basis sketching consists of taking random sketches of the Vandermonde matrix employed in constructing an interpolation model. This randomization enables weakening the general requirement in model-based derivative-free methods that interpolation sets contain a full-dimensional set of affinely independent points in every iteration. Practically, this weakening provides a theoretically justified means of avoiding potentially expensive geometry improvement steps in many model-based derivative-free methods. We demonstrate this practicality by extending the nonlinear least squares solver, $\mathtt{\text{POUNDers}}$ to a variant that employs basis sketching and we observe encouraging results on higher dimensional problems.