Ensuring safety in optimization is challenging if the underlying functional forms of either the constraints or the objective function are unknown. The challenge can be addressed by using Gaussian processes to provide confidence intervals used to find solutions that can be considered safe. To iteratively find a trade-off between finding the solution and ensuring safety, the SafeOpt algorithm builds on algorithms using only the upper bounds (UCB-type algorithms) by performing an exhaustive search on the entire search space to find a safe iterate. That approach can quickly become computationally expensive. We reformulate the exhaustive search as a series of optimization problems to find the next recommended points. We show that the proposed reformulation allows using a wide range of available optimization solvers, such as derivative-free methods. We show that by exploiting the properties of the solver, we enable the introduction of new stopping criteria into safe learning methods and increase flexibility in trading off solver accuracy and computational time. The results from a non-convex optimization problem and an application for controller tuning confirm the flexibility and the performance of the proposed reformulation.