Atomic scale surface structure plays an important role indescribing many properties of materials, especially in the case of nanomaterials. One of the most effective techniques for surface structure determination is low-energy electron diffraction (LEED), which can be used in conjunction with optimization to fit simulated LEED intensities to experimental data. This optimization problem has a number of characteristics that make it challenging: it has many local minima, the optimization variables can be either continuous or categorical, the objective function can be discontinuous, there are no exact analytic derivatives (and no derivatives at all for categorical variables), and function evaluations are expensive. In this study, we show how to apply a particular class of optimization methods known as pattern search methods to address these challenges. These methods donot explicitly use derivatives, and are particularly appropriate when categorical variables are present, an important feature that has not been addressed in previous LEED studies. We have found that pattern search methods can produce excellent results, compared to previously used methods, both in terms of performance and locating optimal results.