1 Introduction

1.3 Optimization

Like quadrature optimization is a very important problem area in science.

Assume that we want to determine the maximum f* = max of the function f(x) in the interval (0,1.5), see below. (The problem of determining the minimum f_* = min f is equivalent to f* = max (-f).)

              2  |------------|
                 |  _        /|
              y  | / \      / | y = f(x)
                 |/   \    /  |
                 |     \__/   |
                 |            |
              0  |____________|
                 0       x    1.5
 

There is no closed form solution to this problem so it must normally be solved numerically. For general f(x) there is even no method that can guarantee an estimate within prescribed accuracy of f*. This problem is therefore well suited to the use of probablilistic algorithms.

A very simple probabilistic algorithm to estimate f* is the following:

     RANDOM SAMPLING:
                fmax:='a very small number'
                for i:=1 step 1 until N do
                     sample a r.n. x in (a,b)
                     if f(x) > fmax then fmax:=f(x)

In our problem above a=1, b=1.5. When the algorithm finishes, fmax holds an estimate of f*. Obviously the estimate improves with increasing N.

The problem stated above is the global optimization problem. In such a problem the function may have many maxima and an estimate of the largest of those is asked for. In local optimization the area of interest (a,b) just contains a single maximum that is to be determined.

Global optimization methods contains some techniques which prevents them from converging just on the first local minimum found. Normally they contain both a global and a local part.

There exist a large number of stochastic methods for both local and global optimization. We will cover some of them in this course. The method Random Sampling is a global optimization method with no local part.

As for quadrature, in the example above, the argument of the function is in Rⁿ, where n=1. However, the method is easy to extend to arbitrary n.