up


Geometry Optimization: Ver. 1.0

Taisuke Ozaki, RCIS, JAIST

Newton method

The total energy $E$ of a system can be expanded by the Taylor series with respect to atomic coordinates $\{x_i\}$ around $E_0$ with $\{x_i^{(0)}\}$ as follows:
$\displaystyle E$ $\textstyle =$ $\displaystyle E_{0}
+ \sum_{i}^{3N}
\left(
\frac{\partial E}{\partial x_i}
\rig...
... \partial x_j}
\right)_0 (x_i - x_i^{(0)})(x_j - x_j^{(0)})
+ \cdots,\quad\quad$ (1)

where the derivatives $()_0$ mean the partial derivatives at $\{x_i^{(0)}\}$, and $N$ is the number of atoms. By differentiating Eq. (1) with respect to $x_k$, to the second order we have
$\displaystyle \frac{\partial E}{\partial x_k}$ $\textstyle =$ $\displaystyle \left(
\frac{\partial E}{\partial x_k}
\right)_0
+
\sum_{i}^{3N}
\left(
\frac{\partial^2 E}{\partial x_k \partial x_i}
\right)_0 (x_i - x_i^{(0)}).$ (2)

In case the coordinates $\{x_i\}$ give a local minimum, assuming $\frac{\partial E}{\partial x_k}=0$, we have the following matrix equation:
    $\displaystyle \left(
\begin{array}{ccc}
(\frac{\partial^2 E}{\partial x_1 \part...
...
\left(
\frac{\partial E}{\partial x_2}
\right)_0\\
\cdots
\end{array}\right).$ (3)

The short notation is
    $\displaystyle H \Delta {\bf x} = -{\bf g},$ (4)

where the matrix consisting of the second derivatives in the left-hand side is called Hessian $H$. Using Eq. (4), $\{x_i\}$ can be updated by
    $\displaystyle {\bf x}^{(n+1)} = {\bf x}^{(n)} - (H^{(n)})^{-1}{\bf g}^{(n)}.$ (5)

This is the well known Newton method.

RMM-DIIS

In the OpenMX, ${\bf x}^{(n)}$ and ${\bf g}^{(n)}$ in Eq. (5) are replaced by ${\bf\bar{x}}^{(n)}$ and ${\bf\bar{g}^{(n)}}$ given by the residual minimization method in the direct inversion of iterative subspace (RMM-DIIS) [1,2] as follows:
    $\displaystyle {\bf x}^{(n+1)} = {\bf\bar{x}}^{(n)}
-\alpha~(H^{(n)})^{-1}{\bf\bar{g}}^{(n)},$ (6)

where $\alpha$ is a tuning parameter for acceleration of the convergence, which can be small (large) for a large (small) ${\bf\bar{g}}^{(n)}$. ${\bf\bar{g}}$ in the RMM-DIIS can be found by a linear combination of previous upto p-th gradients ${\bf g}$ as
    $\displaystyle {\bf\bar{g}}^{(n)} = \sum_{m=n-(p-1)}^{n} a_{m}{\bf g}^{(m)},$ (7)

where $a_{m}$ is found by minimizing $\langle {\bf\bar{g}}^{(n)} \vert {\bf\bar{g}}^{(n)} \rangle$ with a constraint $\sum_{m=n-(p-1)}^{n} a_{m}=1$. According to Lagrange's multiplier method, $F$ is defined by
$\displaystyle F$ $\textstyle =$ $\displaystyle \langle {\bf\bar{g}}^{(n)} \vert {\bf\bar{g}}^{(n)} \rangle
-\lambda (1-\sum_{m}^{n} a_{m}),$  
  $\textstyle =$ $\displaystyle \sum_{m,m'}
a_{m}a_{m'}
\langle {\bf g}^{(m)} \vert {\bf g}^{(m')} \rangle
-\lambda (1-\sum_{m}^{n} a_{m}).$ (8)

Considering $\frac{\partial F}{\partial a_k}=0$ and $\frac{\partial F}{\partial \lambda}=0$, an optimum set of $\{a\}$ can be found by solving the following linear equation:
    $\displaystyle \left(
\begin{array}{cccc}
\langle {\bf g}^{(n-(p-1))} \vert {\bf...
...\right)
=
\left(
\begin{array}{c}
0\\
0\\
\cdot\\
1
\end{array}\right).\quad$ (9)

An optimum choice of ${\bf\bar{x}}^{(n)}$ may be obtained by the set of coefficients $\{a\}$ as
    $\displaystyle {\bf\bar{x}}^{(n)} = \sum_{m=n-(p-1)}^{n} a_{m}{\bf x}^{(m)}.$ (10)

If the Hessian $H$ is approximated by the unity $I$, Eq. (6) becomes
    $\displaystyle {\bf x}^{(n+1)} = {\bf\bar{x}}^{(n)} - \alpha~{\bf\bar{g}}^{(n)}.$ (11)

This scheme in the Cartesian coordinate has been implemented as 'DIIS' in OpenMX.

Broyden-Fletcher-Goldfarb-Shanno (BFGS) method

Define
$\displaystyle \Delta {\bf g}^{(n)}$ $\textstyle =$ $\displaystyle {\bf g}^{(n)} - {\bf g}^{(n-1)},$ (12)
$\displaystyle \Delta {\bf x}^{(n)}$ $\textstyle =$ $\displaystyle {\bf x}^{(n)} - {\bf x}^{(n-1)}.$ (13)

Then, the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method [3] gives the following rank-2 update formula for $(H^{(n)})^{-1}$:
$\displaystyle (H^{(n)})^{-1}$ $\textstyle =$ $\displaystyle (H^{(n-1)})^{-1}
+ \frac{\langle \Delta {\bf x}^{(n)}
\vert \Delt...
...right)^2}
\vert \Delta {\bf x}^{(n)} \rangle
\langle \Delta {\bf x}^{(n)} \vert$  
    $\displaystyle -
\frac{
(H^{(n-1)})^{-1}\vert \Delta {\bf g}^{(n)} \rangle
\lang...
...-1)})^{-1}
}
{\langle \Delta {\bf x}^{(n)}
\vert \Delta {\bf g}^{(n)} \rangle},$ (14)

where $(H^{(0)})^{-1}=I$. An optimization scheme using Eq. (6) and the BFGS update formula for the inverse of an approximate Hessian matrix in the Cartesian coordinate has been implemented as 'BFGS' in OpenMX.

Rational function (RF) method

The BFGS update by Eq. (14) without any care gives an ill-conditioned approximate inverse of Hessian having negative eigenvalues in many cases. This leads to the optimization to saddle points rather than the optimization to a minimum. The rational function (RF) method [4] can avoid the situation in principle. Instead of Eq. (1), we may consider the following expression:
$\displaystyle E$ $\textstyle =$ $\displaystyle E_{0}
+ \sum_{i}^{3N}
\left(
\frac{\partial E}{\partial x_i}
\rig...
...- x_j^{(0)})
+ \frac{1}{2}\lambda \sum_{i}^{3N}
(x_i - x_i^{(0)})^2.
\quad\quad$ (15)

Then, the equation corresponding to Eq. (4) becomes
    $\displaystyle (H^{(n)}+\lambda I) \Delta {\bf x}^{(n)} = -{\bf g}^{(n)}.$ (16)

Therefore, a large $\lambda$ assures that $(H^{(n)}+\lambda I)$ is positive definite. If $\lambda^{(n)}(=-\lambda)$ is given by
    $\displaystyle \lambda^{(n)} =
\langle {\bf g}^{(n)} \vert {\bf s}^{(n)} \rangle.$ (17)

With Eq. (17), Eq. (16) may be equivalent to
    $\displaystyle \left(
\begin{array}{cc}
H^{(n)} & {\bf g}^{(n)}\\
({\bf g}^{(n)...
...bda^{(n)}
\left(
\begin{array}{c}
\Delta {\bf x}^{(n)}\\
1
\end{array}\right),$ (18)

where the size of the matrix in the left-hand side is $(3N+1)\times (3N+1)$, and called the augmented Hessian. The lowest eigenvalue of the eigenvalue problem defined by Eq. (18) may give an optimum choice for $\lambda$, and the corresponding eigenvector, the last component is scaled to 1, gives an optimization step $\Delta {\bf x}^{(n)}$. In Eq. (18), the approximate Hessian can be estimated by the following BFGS formula:
$\displaystyle H^{(n)}$ $\textstyle =$ $\displaystyle H^{(n-1)} +
\frac{\vert \Delta {\bf g}^{(n)} \rangle
\langle \Del...
...angle \Delta {\bf x}^{(n)}
\vert H^{(n-1)} \vert \Delta {\bf x}^{(n)} \rangle},$ (19)

where $H^{(0)}=I$. An optimization scheme using Eq. (18) and the BFGS update formula Eq. (19) in the Cartesian coordinate has been implemented as 'RF' in OpenMX.

Eigenvector following (EF) method

By diagonalizing the approximate Hessian given by Eq. (19), the ill-conditioned situation can be largely reduced [5]. The approximate Hessian is diagonalized as
    $\displaystyle E^{(n)} = (V^{(n)})^{T} H^{(n)} V^{(n)},$ (20)

where $E^{(n)}$ is a diagonal matrix of which diagonal parts are eigenvalues of $H^{(n)}$. If the eigenvalue of the approximate Hessian is smaller than a threshold (0.02 a.u. in OpenMX3.3), the eigenvalue is set to the threshold. The modification of eigenvalues gives a corrected matrix $E'^{(n)}$ instead of $E^{(n)}$. Then, we have the inverse of a corrected Hessian matrix $H'^{(n)}$ being a positive definite as
    $\displaystyle (H'^{(n)})^{-1} = V^{(n)} (E'^{(n)})^{-1} (V^{(n)})^{T}.$ (21)

A optimization scheme using the inverse Eq. (21) in Eq. (6) in the Cartesian coordinate has been implemented as 'EF' in OpenMX. In addition, there are two important prescriptions for the stable optimization: (1) If $\langle \Delta {\bf x}^{(n)}\vert \Delta {\bf g}^{(n)} \rangle$ is positive in the update of Hessian by Eq. (19), it is assured that the updated Hessian is positive definite. Therefore, if $\langle \Delta {\bf x}^{(n)}\vert \Delta {\bf g}^{(n)} \rangle$ is negative, the update should not be performed. (2) The maximum step should be always monitored, so that an erratic movement of atomic position can be avoided.

Bibliography

1
P. Csaszar and P. Pulay, J. Mol. Struc. 114, 31 (1984).

2
F. Eckert, P. Pulay, and H.-J. Werner, J. Comp. Chem. 18, 1473 (1997).

3
C. G. Broyden, J. Inst. Math. Appl. 6, 76 (1970); R. Fletcher, Comput. J. 13, 317 (1970); D. Goldrarb, Math. Comp. 24, 23 (1970); D. F. Shanno, Math. Comp. 24, 647 (1970).

4
A. Banerjee et al., J. Phys. Chem. 89, 52 (1986).

5
J. Baker, J. Comput. Chem. 7, 385 (1986).

up
2007-08-16