CLUSTER: Derivative-free optimization of smooth functions with parameter-change costs

We introduce the CLUSTER algorithm ($\mathbf{\text{c}}$oordinate-$\mathbf{\text{l}}$evel $\mathbf{\text{u}}$pdate $\mathbf{\text{s}}$trategy for $\mathbf{\text{t}}$rust-region step $\mathbf{\text{e}}$valuation $\mathbf{\text{r}}$efinement) for local derivative-free optimization problems where there is a cost to changing each parameter (or clusters of parameters). For example, this type of cost model is appropriate for optimizing robot-controlled laboratory experiments, in which a robot may incur a separate motion for each parameter cluster to be adjusted. We build off of a class of quadratic-interpolation optimization algorithms by Powell and Conn that are known to perform well for twice-differentiable objectives (e.g. low-noise experiments), and show that the CLUSTER variants improve performance on a variety of test problems (including an optics laboratory experiment) by around 50$\mathrm{\%}$, and greatly outperform common competing algorithms for laboratory optimization (Bayesian optimization and Nelder–Mead). We also adapt the convergence proof of the Conn algorithm to obtain a similar convergence guarantee for CLUSTER-Conn.