Lipschitz Optimisation for Lipschitz Interpolation