1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is the origin if your functional? What is the nature of your variables X? $\endgroup$ – nicoguaro Feb 23 '17 at 16:01
  • $\begingroup$ Well, X is just a N-dimensional real vector, I mean, X = (X_1,...X_N) where X_i are real numbers. What do you mean "origin"? $\endgroup$ – genov4 Feb 23 '17 at 16:07
  • $\begingroup$ Yes, it is a real vector, as you stated, are they coordinates? Is your problem a classical mechanics problem, an electromagnetism problem, quantum mechanics problem? $\endgroup$ – nicoguaro Feb 23 '17 at 16:08
  • $\begingroup$ Yes, they are coordinates. It is not really the case in classical, electromagnetism or quantum mechanics. Just assume that I have a numerical scheme, and I need to solve this optimization problem to find positions for (N/2) particle (N is even of course), (X_1,...X_{N/2}) are x-coordinates and (X_{N/2+1},...,X_N) are y-coordinates. $\endgroup$ – genov4 Feb 23 '17 at 16:15
  • 1
    $\begingroup$ A little comment: in 2017, I think that 2000 is a small number ! A question: could you try expliciting your objective function ? Maybe computing grad F and hess F is doable, we'd like to have a look (maybe with the help of a computer algebra system). $\endgroup$ – BrunoLevy Mar 28 '17 at 20:11
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

It may not be an easy thing to do if you are dealing with particle positions (as you've noted in comments above). Example is a Lennard-Jones atom clustering problem which is very hard to solve for even just 150 particles. Such problems are indirectly combinatorial or continuous-combinatorial. You may look for existing solutions to Lennard-Jones problem, maybe you can find something suitable for your application. Generally-available solvers won't acceptably solve such problems.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.