## General algorithm for locating minima and optimization Although I don't really want to talk much about this topic, since [[Potential energy surface#^d5abce|the minimal locating]] is almost something entirely independent with material science. We here just want to get a general and efficient algorithm to find the minimum/maximum and [[Locating transit state|settle points (discuss later)]] of the given field. >[!Notice] >Although it seems like a 2D picture, but it **does not have grids**, so slightly different. It is described **analytically** from constraints, so it's pretty annoying. ### Without gradient - Possibly evaluate V on a grid of points. - Simplex method. - Or [parallel tempering](https://en.wikipedia.org/wiki/Parallel_tempering), [simulated annealing](https://en.wikipedia.org/wiki/Simulated_annealing), etc. (These are actually large scale global sampling method) ### With gradient #### Steepest descent method Go along biggest gradient (i.e., the steepest descent) direction - choose $x_0$ - Consider $X_{n+1} = X_n -\gamma_n \nabla F(x_n)x\geq0$ - $\gamma$ may get changed Problem: May have the zigzag shape. Slow the simulation. #### Congregate gradient method Similar to the previous one, but $x_{n+1}$ step only search the conjugate directions. This ensures no reputation such of minimum and converge in at most n step. (for $n \times n$ matrix) #### Quasi-Newton method Newton-Raphson method reach minimum by iterating $x_{n+1}=x_n-\alpha(H_n^{-1}g_n)$ $H_n$ is Hessian and $g_n$ is gradient of $f$. >[!Note] >Here $H_n^{-1}$ control/adjust the step size, while $g_n$ determines the direction. For a complex system, $H_n^{-1}$ can be difficult to compute. (Or say, computational intensive) So use quasi-update to update $H_n$ at each step, Instead of recomputing, based on BFGS. BFGS provides a way to iterate $H_{n+1}$ from $H_n$, based only on $g_n$. >[!Info] >More on [BFGS](https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm) and [optimization algorithm](https://ocw.mit.edu/courses/18-335j-introduction-to-numerical-methods-spring-2019/pages/week-11/). >