Global Optimisation

From FraudWiki

It is possible to find the global minimum by finding and removing the local minima. Each local minima is removed by deforming the gradient field as described by Chao[1]. The following illustrates this idea in one dimension but the method guarantees to find the global minimum within any bounded region.

So if we consider the energy function:

$E = 2 w 6 - 15 w 4 + 24 w 2$ which has extrema at w = +2, +1, 0, -1, -2

Starting from w = 3, we follow the direction of the negative gradient until the first minimum is reached at w = 2. Then we deform the gradient field to remove this extremum from the energy field by `dividing it out' and proceed down the gradient of the deformed field until we reach the next extremum, a maximum, at +1. This process may be repeated until all the extrema have been eliminated. This procedure is illustrated below:

Energy		Gradient	Extrema removed
$E_0 = \textstyle{2}w^6-15w^4+24w^2$	so	$\frac{dE_0 }{dw} = 12w\left( {w^2-1} \right)\left( {w^2-4} \right)$
$E_1 =\textstyle{{12} \over 5}w^5+6w^4-4w^3-12w^2$	and so	$\frac{dE_1 }{dw}={\frac{dE_0 }{dw}} / {\left( {w-2} \right)} = 12w\left( {w^2-1} \right)\left( {w+2} \right)$	min at w = 2
$E_2 =\textstyle{3}w^4+12w^3+12w^2$	and so	$\frac{dE_2 }{dw}={\frac{dE_1 }{dw}} / {\left( {w-1} \right)} = 12w\left( {w+1} \right)\left( {w+2} \right)$	max at w = 1
$E_3 =\textstyle{4}w^3+18w^2+24w$	and so	$\frac{dE_3 }{dw}={\frac{dE_2 }{dw}} / {\left( {w} \right)} = 12\left( {w+1} \right)\left( {w+2} \right)$	min at w = 0
$E_4 =\textstyle{6}w^2+24w$	and so	$\frac{dE_4 }{dw}={\frac{dE_3 }{dw}} / {\left( {w+1} \right)} = 12\left( {w+2} \right)$	max at w = -1
$E_5 =\textstyle{12}w$	and so	$\frac{dE_5 }{dw}={\frac{dE_4 }{dw}} / {\left( {w+2} \right)} = 12$	min at w = -2