9. The Objective Function
Society for Industrial and Applied Mathematics eBooks · 2002
Recall that we are generally interested in very large problems. Our point of view is to do as well as possible with a given amount of computer time. How much computer time one should allocate is ultimately an economic problem that yields easily to a cost-benefit analysis: We need to compare the value of a unit of improvement in the energy with the cost of the expected increase in computational time. As long as it pays more than it costs, we should allocate more time. How to spend a given amount of time to do “as well as possible” is less clear cut than one might expect. Recalling that the algorithm is stochastic, we realize that our choices of the algorithm and its parameters will determine a distribution of possible values for the best energy found by the algorithm. We might thus conclude that “as well as possible” means that we should minimize the expected value of this best energy. As argued in Chapter 8, where this objective is 〈Evbsf〉, beyond a certain level of dedicated computer time, trying to find the best expected value of Evbsf leads naturally to ensembles. This is not, however, the only approach. In fact, for problems in which the objective function is not known with perfect precision, there is a better alternative. This is discussed in the next two sections. Even when the objective is perfectly known, however, there is another approach that modifies (or deforms) the objective as a device for speeding up the convergence of the algorithm. This approach is the topic of the last two sections of this chapter. 9.1 Imperfectly Known Objective Many important optimization problems come with imperfect information regarding the real objective being minimized. In such problems the values of the objective are accurate only to a certain tolerance. Many of the improvements and conjectures described in Part III distinguish between problems with such noisy objectives and problems in which the objective is known with perfect accuracy. Almost all real problems have some sort of noise in the objective function. We will discuss three sources of such noise.