5 Local and Global Optimization

Unirandi

Unirandi is a uniform-random-direction-linear-search local minimization algorithm proposed by Timo Järvi in his Ph.D. Thesis (1973). A simplified version of the algorithm can be described as follows:

            Unirandi(x0, h0, hm, x, fx)                        
                   x := x0; starting point (x1,x2,...,xn)
                   h := h0; initial steplength
                   hm minimum steplength
                   fx:= f(x)

    find_better:  for k:=1,2 do (2 + 2 failures means: halve steplength)
                        new_direction d
                        new_trial t, ft := f(t)
                        if better then go to linear
                        opposite_direction d := -d
                        new_trial t, ft := f(t)
                        if better then go to linear

                  halve_steplength h:= h/2
                  if h < hm then return else go to find_better

         linear:   while better do
                        record_point x:= t, fx := ft
                        double_steplength h:= 2h
                        new_trial t, ft := f(t)

                    halve_steplength h:=h/2
                    go to find_better

If we assume that the minimum of f(x) is sought in the box [a₁,b₁] x [a₂,b₂] x ... x [a_n,b_n] starting from the point x₀ with the initial steplength h₀, that the dimension of the x-space is n, rn_i is a normally distributed random number (0,1), then the ith coordinate d_i of new_direction (giving unit length of d) is

               di := rni/sqrt(rn12+ ... + rnn2)

opposite_direction is obtained by changing the signs of the d_is and new-trial is obtained by

                    ti := xi + h*di
                    ft := f(t)  

better could be the boolean

                ti in [ai,bi] and ft < fx