Direct methods

The three most widely used direct search methods are the Hooke and Jeeves pattern search method [110], the Nelder and Mead Simplex method [199], and Powell's conjugate gradient method [210]. In the sequel we discuss in detail only the most efficient and accurate one: the Nelder-Mead Simplex method (see Onwubiko [204] for a comparison).

The Nelder-Mead Simplex method is based on the "Sequential Simplex" method formulated by Spendley, Hext, and Himsworth in 1962 [278]. To understand the Nelder-Mead method, we need to briefly consider the sequential simplex method.

A simplex in IRn is a set of n +1 points (x0, x1, ■ ■ ■ ,xn) which form a polyhedron. In the case of IR2 a simplex is simply a (equilateral) triangle, while in three dimensions it becomes a tetrahedron. At each iteration, to minimize the user-specified objective function, the function values are determined at each of the n +1 vertices. After that, the vertex with the highest function value is mirrored (reflected) in the centroid of the other n vertices as illustrated in Fig. 5.1, with the result that a new simplex is created. The objective function is then evaluated at the new vertex, and the process is repeated. Observe that the search direction points away from the vertex having the largest function value.

During the iterations after the first one it might be that the newest vertex still has the largest function value in the new simplex, and reflecting this vertex would cause oscillation. To prevent this, the largest function value other than that at the newest vertex is subsequently used to decide which vertex to reflect. As the optimum is approached, the last vertex will straddle the optimum point or be within a distance of the order of its own size from the optimum. In the latter case, the procedure cannot get closer to the optimum without reducing the simplex size. The simplex size is reduced ("contracted") by replacing the other vertices by new ones half way the last vertex. When the resulting simplex size is smaller than a prescribed tolerance, the iteration is stopped. Thus the optimum parameter vector is determined to within a tolerance influenced by the size of the simplex.

The typical progress of the iteration is illustrated in Fig. 5.2 using a function of two parameters [64]. Vertices 1,2 and 3 form the initial simplex, and increasing

Figure 5.1: Reflection to a new point in the Simplex method. Vertices xo (with largest function value), x\, and X2 form the initial simplex. The next point (vertex) is X4.

numbers indicate the new vertices added to each iteration. Note that vertex 7 has the largest function value for the simplex (4,6,7) but is not reflected immediately since it is the newest vertex in that simplex. When simplex (6,9,10) is reached, the procedure cannot get closer to the optimum without reducing the simplex size to (6,11,12). The iteration continues again from this simplex until the simplex is smaller than a prescribed tolerance. The interested reader is referred to Buchanan et al. [35] and Walters et al. [304] for detailed information (including applications) about the Simplex search method.

Figure 5.2: Illustration of the iteration progress of the Simplex method in two parameters (n = 2). Vertices (1,2,3) form the initial simplex. Succeeding new vertices are numbered starting with 4 and continuing to 10 at which a cycle starts to repeat. Consequently the simplex is contracted to the new simplex (6,11,12). After that the procedure is continued.

Figure 5.2: Illustration of the iteration progress of the Simplex method in two parameters (n = 2). Vertices (1,2,3) form the initial simplex. Succeeding new vertices are numbered starting with 4 and continuing to 10 at which a cycle starts to repeat. Consequently the simplex is contracted to the new simplex (6,11,12). After that the procedure is continued.

The problem with the method thus far is that the use of regular simplices slows down the rate of acceleration of the search. It would be more efficient to allow the simplex to adapt to the local contours of the objective function [181]. Because of this, Nelder and Mead introduced the use of nonregular simplices. However, it is known that the Nelder-Mead method frequently fails to converge to a local minimum. Furthermore, this method is slow and can be applied only to problems in which n is small [194]. In spite of this, it is enormously popular in practice. The main reasons are twofold. First, it typically produces significant improvement in the first few iterations. Second, the Nelder-Mead method uses a small number of function evaluations per iteration. The interested reader is referred to Lagarias et al. [148] were convergence properties of this method are discussed.

Renewable Energy 101

Renewable Energy 101

Renewable energy is energy that is generated from sunlight, rain, tides, geothermal heat and wind. These sources are naturally and constantly replenished, which is why they are deemed as renewable. The usage of renewable energy sources is very important when considering the sustainability of the existing energy usage of the world. While there is currently an abundance of non-renewable energy sources, such as nuclear fuels, these energy sources are depleting. In addition to being a non-renewable supply, the non-renewable energy sources release emissions into the air, which has an adverse effect on the environment.

Get My Free Ebook


Post a comment