Parameter estimation: reduce time
If an exhaustive nonlinear scan is too expensive and a linear scan doesn't yield the best results then I suggest you try a stochastic nonlinear search i.e. a random search for hyperparameter optimization.  

Scikit learn has a user friendly description in its user guide.

Here is a paper on random search for hyperparameter optimization.