I am modeling the structure of a crystal and need to find what the "lowest energy structure" is. There are three free parameters (let's say, $a$, $b$, and $c$) to change, and the search space, $E(a,b,c)$ is convex. What is the best way to set this up so I vary $a$, $b$, and $c$ to find the combination that yields the minimum of $E(a,b,c)$ without running extraneous calculations?

What I am currently doing is picking a relatively wide range of $a$, $b$, and $c$ values and computing $E$ for each combination. Then I fit a paraboloid to series of 3D plots of $E$ vs. $a$ vs. $b$ at fixed $c$ value and find where the global minimum is located. This was fine when my calculations were quick, but I need to be more efficient now with how to improve how I am searching the parameter space. One can think of something simple like making a range of $a$, $b$, and $c$, and keep expanding this range until $E$ increases when changing in all 3 dimensions from a given point, for instance.

Any suggestions of an adaptive search algorithm for a problem like this?

  • $\begingroup$ There's not quite enough information to recommend an algorithm yet. Can you compute (or efficiently approximate) the gradient and/or Hessian of $E$? Are there constraints on $a,b,c$? Is $E$ expensive compute for a given $a,b,c$? $\endgroup$ – Tyler Olsen Sep 24 '17 at 4:11
  • $\begingroup$ I will try to provide more information. Generally, yes, $E$ is expensive to compute, which is why I wish to not run extraneous calculations. Experimental values of $a$, $b$, and $c$ are known, so the theoretical values I compute are usually near these values. As such, I can do a brute force approach and sample around this space but would like to do so moderately efficiently. The constraints are that the parameters are positive. They are generally within +/- 10% of reference values I have. I can get the gradient of $E$. Hessian is expensive. I'm using Python as well by the way. $\endgroup$ – Argon Sep 24 '17 at 4:18
  • 1
    $\begingroup$ One technique that might work (if you observe that you do not ever run into the constraints on $a,b,c$) is a quasi-Newton method for unconstrained optimization problems called BFGS. It requires a gradient computation at each time step, and it maintains an approximation of the Hessian and uses this information to do a Newton-like step, so it tends to converge more quickly than a simple gradient descent method for well-behaved functions. Check out the wiki and contained references for implementation details. en.wikipedia.org/wiki/… $\endgroup$ – Tyler Olsen Sep 24 '17 at 4:27
  • 1
    $\begingroup$ I will mention that it is unsuitable for the case where you have to strictly enforce the positivity constraints on your parameters. In this case, you should check out other constrained optimization algorithms. I'll throw out the name "accelerated projected gradient descent" for you to google if you run into this. $\endgroup$ – Tyler Olsen Sep 24 '17 at 4:35
  • 1
    $\begingroup$ for box constraints on your variables (e.g., positivity), look into L-BFGS-B (limited memory BFGS with bound constraints). Scipy implements this method, see this link. $\endgroup$ – GoHokies Sep 24 '17 at 8:00

Your Answer

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

Browse other questions tagged or ask your own question.