Heavy sphere, method of the

A method for solving a minimization problem for a differentiable function on a Euclidean space $ E ^ {n} $. The method is based on considering the system of differential equations

$$ \tag{1 } \frac{d ^ {2} x }{d t ^ {2} } + a \frac{dx}{dt} + \frac{f ^ { \prime } ( x) }{1 + | f ^ { \prime } ( x) | ^ {2} } = 0 ,\ t \geq 0 , $$

which describes the movement of a material point over the surface $ y = f ( x) $ in an attracting field directed in the negative direction of the $ y $- axis under the condition that the point may not leave the surface and that the attraction is proportional to the velocity; $ | f ^ { \prime } ( x) | $ is de gradient of $ f ( x) $ at a point $ x $ and $ a \geq 0 $ is the attraction coefficient. Taking into account that $ | f ^ { \prime } ( x) | ^ {2} $ is small in a neighbourhood of a stationary point, (1) is often replaced by the system

$$ \tag{2 } \frac{d ^ {2} x }{d t ^ {2} } + a \frac{dx}{dt} + f ^ { \prime } ( x) = 0 ,\ \ t \geq 0 . $$

Subject to certain assumptions on $ f ( x) $ and under the initial conditions

$$ x ( 0) = x _ {0} ,\ \ \frac{d x ( 0) }{d t } = x _ {1} $$

it can be shown that the corresponding solution $ x ( t) $ of (1) or (2), as $ t \rightarrow \infty $, converges to some stationary point $ x _ {*} $ of $ f ( x) $. If $ f ( x) $ is a convex function, then $ x _ {*} $ is a minimum point of it. Thus, the method of the heavy sphere is a particular case of the adjustment method. For the numerical solution of (1), or (2), one may, use, e.g., difference methods. In dependence on the choice of this difference method, discrete analogues of the method of the heavy sphere are obtained, including those for functions depending strongly on a few variables, the conjugate-gradient method, etc. (cf. Minimization methods for functions depending strongly on a few variables; Conjugate gradients, method of). The choice of the step of the difference method and of the quantity $ a $ strongly influences the rate of convergence of the method of the heavy sphere. Instead of (1), (2) other first- or second-order systems may be used (cf. [1]). In the problem of minimizing a function $ f ( x) $ under the restrictions

$$ g _ {i} ( x) \leq 0 ,\ \ i = 1 \dots m ; \ \ g _ {i} ( x) = 0 ,\ \ i = m + 1 \dots s , $$

the method of the heavy sphere is applied in combination with the method of penalty functions, Lagrange functions, etc. (cf. [2], [3], Penalty functions, method of; Lagrange function).

References

[1]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[2]	F.P. Vasil'ev, "Numerical methods for solving extremum problems" , Moscow (1980) (In Russian)
[3]	Yu.G. Evtushenko, "Numerical optimization techniques" , Optim. Software (1985) (Translated from Russian)