Golden search

One method to finding the minimum of a function is to search over all possible values of x and find the minimum based on the corresponding values of Y. These algorithms include region elimination methods, such as the Golden Search algorithm or point-estimation methods, such as Powell s method, neither of which require calculation of the derivatives. However, these types of methods often assume unimodality, and in some cases, continuity of the function. The reader is referred to Reklaitis Ravindran, and Ragsdell (1983) or Rao (1996) for details. 

In root-finding, Bolzano s method is combined with other efficient methods because of its robustness. Unfortunately, in the case of one-dimensional optimization, neither the robust methods, golden search nor Fibonacci, can be satisfactorily combined with efficient methods. 

The golden section can be seen as a criterion to check the efficiency of an efficient method if the efficient method does not reduce the interval of uncertainty any better than the golden search, the new point is inserted using a different method. 

The golden section search is the optimization analog of a binary search. It is used for functions of a single variable, F a). It is faster than a random search, but the difference in computing time will be trivial unless the objective function is extremely hard to evaluate. 

The nature of the relationships and constraints in most design problems is such that the use of analytical methods is not feasible. In these circumstances search methods, that require only that the objective function can be computed from arbitrary values of the independent variables, are used. For single variable problems, where the objective function is unimodal, the simplest approach is to calculate the value of the objective function at uniformly spaced values of the variable until a maximum (or minimum) value is obtained. Though this method is not the most efficient, it will not require excessive computing time for simple problems. Several more efficient search techniques have been developed, such as the method of the golden section see Boas (1963b) and Edgar and Himmelblau (2001). 

The optimum seeking methods which have been found to be particularly useful are the modified Fibonacci search (search by golden section) for one-dimensional searches and the Hooke-Jeeves search for multi-dimensional searches. Beveridge and Schechter (8) give a complete description of these searches. 

Retaining the latest estimates for x and X2, the slope of the line follows more closely the form of the function than in the false position method. The order of convergence can be shown to be 1.61B, the "golden ratio", which we will encounter in Section 2.2.1. The root, however, is not necessarily bracketed, and the next estimate x3 may be far away if the function value ffx ) is close to f(x2>. Therefore we may run into trouble when starting the search in a region where the function is not monotonic. 

Fig. 2.7. Notations used in golden-section search derivation...

The golden section search guarantees that each new function evaluation will reduce the uncertainty interval to a length of >. times the previous interval. This is comparable to, but not as good as interval halving in the bisection method of solving a nonlinear equation. You can easily calculate that to attain an error tolerance EP we need... 

Example 2.2.1 Optimal drug dosing by golden section search... 

Although the golden section search works quite well, it is obviously not the best available for a given number of function evaluations. For example, with only two evaluations allowed it is better to choose the internal points close to the midpoint of the initial interval, as we already discussed. The idea can... 

Parabolic interpolation is more effective than golden section search for this problem, because the function is of parabolic character in the vicinity of the minimum. To show a counterexample we slightly change the approximate objective function (2.19) and define by... 

Search the Web for the term golden rule and you ll quickly find many more. Although the wordings are different, the meanings are virtually the same. Note, however, there are two different types of golden rule (Hazlitt, 1964). 

The only parameter that has been fixed in the above three sequential stages is the HRAT. We can subsequently update the H RAT by performing a one-dimensional search using the golden section search method, which is shown as the outside loop in Figure 8.20. 

Remark 1 Steps (i) and (ii) are applied to the overall HEN without decomposing it into subnetworks. It is assumed, however, that we have a fixed HRAT for which we calculated the minimum utility cost. The HRAT can be optimized by using the golden section search in the same way that we described it in Figure 8.20. 

Indirect methods solve the necessary conditions for an optimum (looking at the shape of the function) directly via iteration. Region elimination techniques such as Fibonacci and Golden Section searches use function evaluations only to delete a portion of the independent variable range at each iteration. Interpolation techniques use polynomial fitting (quadratic or cubic oftentimes) to predict the location of the optimum. 

---