Namespaces
Variants
Actions

Difference between revisions of "Heavy sphere, method of the"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
A method for solving a minimization problem for a differentiable function on a Euclidean space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h0467801.png" />. The method is based on considering the system of differential equations
+
<!--
 +
h0467801.png
 +
$#A+1 = 21 n = 0
 +
$#C+1 = 21 : ~/encyclopedia/old_files/data/H046/H.0406780 Heavy sphere, method of the
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h0467802.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
which describes the movement of a material point over the surface <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h0467803.png" /> in an attracting field directed in the negative direction of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h0467804.png" />-axis under the condition that the point may not leave the surface and that the attraction is proportional to the velocity; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h0467805.png" /> is de gradient of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h0467806.png" /> at a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h0467807.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h0467808.png" /> is the attraction coefficient. Taking into account that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h0467809.png" /> is small in a neighbourhood of a stationary point, (1) is often replaced by the system
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h04678010.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{1 }
  
Subject to certain assumptions on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h04678011.png" /> and under the initial conditions
+
\frac{d  ^ {2} x }{d t  ^ {2} }
 +
+
 +
a
 +
\frac{dx}{dt}
 +
+
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h04678012.png" /></td> </tr></table>
+
\frac{f ^ { \prime } ( x) }{1 + | f ^ { \prime } ( x) |  ^ {2} }
  
it can be shown that the corresponding solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h04678013.png" /> of (1) or (2), as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h04678014.png" />, converges to some stationary point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h04678015.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h04678016.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h04678017.png" /> is a convex function, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h04678018.png" /> is a minimum point of it. Thus, the method of the heavy sphere is a particular case of the [[Adjustment method|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|Minimization methods for functions depending strongly on a few variables]]; [[Conjugate gradients, method of|Conjugate gradients, method of]]). The choice of the step of the difference method and of the quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h04678019.png" /> 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. [[#References|[1]]]). In the problem of minimizing a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h04678020.png" /> under the restrictions
+
= 0 ,\  t \geq  0 ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046780/h04678021.png" /></td> </tr></table>
+
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|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|Minimization methods for functions depending strongly on a few variables]]; [[Conjugate gradients, method of|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. [[#References|[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. [[#References|[2]]], [[#References|[3]]], [[Penalty functions, method of|Penalty functions, method of]]; [[Lagrange function|Lagrange function]]).
 
the method of the heavy sphere is applied in combination with the method of penalty functions, Lagrange functions, etc. (cf. [[#References|[2]]], [[#References|[3]]], [[Penalty functions, method of|Penalty functions, method of]]; [[Lagrange function|Lagrange function]]).

Latest revision as of 22:10, 5 June 2020


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)
How to Cite This Entry:
Heavy sphere, method of the. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Heavy_sphere,_method_of_the&oldid=47200
This article was adapted from an original article by F.P. Vasil'ev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article