Many properties of nanostructures depend on the atomic configuration at the surface. One common technique used for determining this surface structure is based on the low energy electron diffraction (LEED) method, which uses a high-fidelity physics model to compare experimental results with spectra computed via a computer simulation. While this approach is highly effective, the computational cost of the simulations can be prohibitive for large systems. In this work, we propose the use of a direct search method in conjunction with an additive surrogate. This surrogate is constructed from a combination of a simplified physics model and an interpolation that is based on the differences between the simplified physics model and the full fidelity model.