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?

Improve this question
$\endgroup$
5
  • $\begingroup$ What is the origin if your functional? What is the nature of your variables X? $\endgroup$
    – nicoguaro ♦
    Commented Feb 23, 2017 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
    Commented Feb 23, 2017 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 ♦
    Commented Feb 23, 2017 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
    Commented Feb 23, 2017 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
    Commented Mar 28, 2017 at 20:11

2 Answers 2

Reset to default
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

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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