Using a surrogate model for the solution space of an optimization problem

I have an optimization problem: Given a complex $$n\times n$$ covariance matrix $$C$$ one must find a complex $$n$$-vector $$v_C^\ast$$ which (approximately) minimizes an objective $$f_C(v)$$ over all space. $$n$$ is around 5 or so.

The ultimate goal is to design a procedure which quickly translates covariance matrices $$C$$ into a near-optimal vector.

$$C$$ and $$f_C$$ are known "at runtime" and $$f_C$$ is readily computable, but the optimization problem is hard. $$f_C$$ has many close-to-optimal local maxima and discontinuities. The most efficient technique known to directly find $$v_C^\ast$$ is by random trials: choose components randomly uniform over a box at the origin. This is slow and naive, but performs consistently well.

Because we only need an approximate solution, I am hoping that learning techniques can help. My idea is to spend a long time building a large dictionary of known-good pairs $$(C,v_C^\ast)$$, then training a model on the dictionary. What learning techniques might be suited for this purpose?

My first idea is to use random forest regression, except instead of averaging from the committee of trees, just choose the best of them instead. Does this have a chance of working?