Q:

Numerical optimization algorithm with approximated derivatives

Suppose I have a energy functional E depending on X, where X is a N-dimensional real value vector and N could be very large (~=2000). I assume that there exists (at least) a (local) minimizer for E. There are several problems I am dealing with now:

Firstly, the functional E is extremely 'complicated', it is nearly impossible to compute its exact gradient and its Hessian as well. So the 'input' data are always approximated. (approximated Gradient by finite difference formula, approximate Hessian, ...) 
Secondly, N is very large: N ~= 2000. So I guess this can be called a Large Scaled Problem.
Thirdly, in my code, I need to repeat this optimization problem many times (approx. 100 iterations), so a fast and efficient optimization solver is very necessary.

Is there any good algorithm that can satisfies all the requirement above?

A:

Consider simulated annealing  or similar algorithms.
Very briefly, such algorithms perform a random walk in your $N$-dimensional space, but whether a new step is taken depends on the energy lost¹ by this step:

If the step decreases $E$, it is made.
If the step increases $E$, the step is made with a probability depending on the energy lost by this step. This probability is decreased over time (that’s the annealing).

The advantages are:

You do not need to compute the derivatives at all (unless you opt for a mixed technique).
You can also find global minima.

The downsides are:

You need to evaluate $E$ a lot. 
It’s a Monte Carlo algorithm, so it may not always find the answer you desire (in particular if you have to cut down on the computation).

Whether this is actually the best solution for you is obviously something only you can decide as it depends on a lot of factors.

¹ or gained, depending on your perspective and signs

