Optimization in More than One Dimension

We now return to the problem mentioned above of minimizing the total energy of a set of atoms in a supercell, E(x), by varying the positions of the atoms within the supercell. This example will highlight some of the complications that appear when we try and solve multivariable optimization problems that are not present for the one-dimensional situations we have already discussed. If we define g,(x) = dE(x)/dxi, then minimizing E(x) is equivalent to finding a set of positions for which g (x) = 0 simultaneously for i 1. 3N. 

There is no natural way to generalize the one-dimensional bisection method to solve this multidimensional problem. But it is possible to generalize Newton s method to this situation. The one-dimensional Newton method was derived using a Taylor expansion, and the multidimensional problem can be approached in the same way. The result involves a 3/V x 3/V matrix of derivatives, J, with elements 7y = dg, /dxj. Note that the elements of this matrix are the second partial derivatives of the function we are really interested in, E(x). Newton s method defines a series of iterates by 

This looks fairly similar to the result we derived for the one-dimensional case, but in practice is takes a lot more effort to apply. Consider a situation where we 

At this point it may seem as though we can conclude our discussion of optimization methods since we have defined an approach (Newton s method) that will rapidly converge to optimal solutions of multidimensional problems. Unfortunately, Newton s method simply cannot be applied to the DFT problem we set ourselves at the beginning of this section To apply Newton s method to minimize the total energy of a set of atoms in a supercell, E(x), requires calculating the matrix of second derivatives of the form SP E/dxi dxj. Unfortunately, it is very difficult to directly evaluate second derivatives of energy within plane-wave DFT, and most codes do not attempt to perform these calculations. The problem here is not just that Newton s method is numerically inefficient—it just is not practically feasible to evaluate the functions we need to use this method. As a result, we have to look for other approaches to minimize E(x). We will briefly discuss the two numerical methods that are most commonly used for this problem quasi-Newton and 

We have referred to quasi-Newton methods rather than the quasi-Newton method because there are multiple definitions that can be used for the function F in this expression. The details of the function F are not central to our discussion, but you should note that this updating procedure now uses information from the current and the previous iterations of the method. This is different from all the methods we have introduced above, which only used information from the current iteration to generate a new iterate. If you think about this a little you will realize that the equations listed above only tell us how to proceed once several iterations of the method have already been made. Describing how to overcome this complication is beyond our scope here, but it does mean than when using a quasi-Newton method, the convergence of the method to a solution should really only be examined after performing a minimum of four or five iterations. 

---