Piyavsky method

The Piyavsky method is a method for finding the global minimum ( maximum ) of a Lipschitz function given on a compact . It is simple to implement and has fairly simple convergence conditions. Suitable for a wide class of functions, the derivative of which, for example, we can limit.

Content

Idea of the method

Let function $f(x)$ ${\ displaystyle f (x)}$ given on $\left[a,b\right]$ ${\ displaystyle \ left [a, b \ right]}$ satisfies the Lipschitz condition:

$\mid f(x_{2})-f(x_{1})\mid \leq L\|x_{2}-x_{1}\|$ ${\ displaystyle \ mid f (x_ {2}) - f (x_ {1}) \ mid \ leq L \ | x_ {2} -x_ {1} \ |}$ .

From the Lipschitz conditions, a two-sided inequality obviously follows, which limits the expected behavior of the function.

$f_{i}-L\|x-x_{i}\|\leq f(x)\leq f_{i}+L\|x-x_{i}\|$ ${\ displaystyle f_ {i} -L \ | x-x_ {i} \ | \ leq f (x) \ leq f_ {i} + L \ | x-x_ {i} \ |}$ ,

Where $f_{i}$ ${\ displaystyle f_ {i}}$ , the point at which the measurement was taken.

Let a few tests $x_{1},x_{2},...,x_{k}\rightarrow f_{1},f_{2},...,f_{k}$ ${\ displaystyle x_ {1}, x_ {2}, ..., x_ {k} \ rightarrow f_ {1}, f_ {2}, ..., f_ {k}}$ .

Function $f_{k}^{-}(x)=\max _{i={\overline {1,k}}}^{}\left\{f_{i}-L\|x-x_{i}\|\right\}$ ${\ displaystyle f_ {k} ^ {-} (x) = \ max _ {i = {\ overline {1, k}}} ^ {} \ left \ {f_ {i} -L \ | x-x_ { i} \ | \ right \}}$ let's call minorant , and $f_{k}^{+}(x)=\min _{i={\overline {1,k}}}^{}\left\{f_{i}+L\|x-x_{i}\|\right\}$ ${\ displaystyle f_ {k} ^ {+} (x) = \ min _ {i = {\ overline {1, k}}} ^ {} \ left \ {f_ {i} + L \ | x-x_ { i} \ | \ right \}}$ - majorant .

Graphically represent a broken line, so the Piyavsky method is often also called the broken line method. Obviously, they limit the function from two sides: $f_{k}^{-}(x)\leq f(x)\leq f_{k}^{+}(x)$ ${\ displaystyle f_ {k} ^ {-} (x) \ leq f (x) \ leq f_ {k} ^ {+} (x)}$

Denote $f_{k}^{*}=\min _{i={\overline {1,k}}}^{}\left\{f_{i}\right\}$ ${\ displaystyle f_ {k} ^ {*} = \ min _ {i = {\ overline {1, k}}} ^ {} \ left \ {f_ {i} \ right \}}$ . Global minimum function $f(x^{*})$ ${\ displaystyle f (x ^ {*})}$ can be rated: $\min _{x\in \left[a,b\right]}^{}\left\{f_{k}^{-}(x)\right\}\leq f(x^{*})\leq f_{k}^{*}$ ${\ displaystyle \ min _ {x \ in \ left [a, b \ right]} ^ {} \ left \ {f_ {k} ^ {-} (x) \ right \} \ leq f (x ^ {* }) \ leq f_ {k} ^ {*}}$

Making the specified "corridor" less pre-set $\varepsilon$ ${\ displaystyle \ varepsilon}$ , you can find the global minimum of the function. The Piyavsky method at each step produces a new test of the function. $f_{i+1}$ ${\ displaystyle f_ {i + 1}}$ while adjusting the minorant and the current estimate of the global minimum. Tests are conducted at the minimum point of the current minorant.

Algorithm

Set (or estimate) the Lipschitz constant $L>0$ ${\ displaystyle L> 0}$ accuracy $\varepsilon >0$ {\ displaystyle \ varepsilon> 0} and $k_{0}$ ${\ displaystyle k_ {0}}$ - the number of initial tests.
We carry out these tests at any different points on the compact. $K$ ${\ displaystyle K}$ . $x_{1},x_{2},...,x_{k}\rightarrow f_{1},f_{2},...,f_{k}$ ${\ displaystyle x_ {1}, x_ {2}, ..., x_ {k} \ rightarrow f_ {1}, f_ {2}, ..., f_ {k}}$ . $k:=k_{0}$ ${\ displaystyle k: = k_ {0}}$
$f_{k}^{*}=\min _{i={\overline {1,k}}}^{}\left\{f_{i}\right\}$ ${\ displaystyle f_ {k} ^ {*} = \ min _ {i = {\ overline {1, k}}} ^ {} \ left \ {f_ {i} \ right \}}$ . You can simply compare with the value in the previous iteration.
$x_{k+1}=arg\min _{x\in \Pi _{k}}^{}f_{k}^{-}(x)$ ${\ displaystyle x_ {k + 1} = arg \ min _ {x \ in \ Pi _ {k}} ^ {} f_ {k} ^ {-} (x)}$ where $\Pi _{k}=\left\{x\in K:f(x)\leq f_{k}^{*}\right\}$ ${\ displaystyle \ Pi _ {k} = \ left \ {x \ in K: f (x) \ leq f_ {k} ^ {*} \ right \}}$ .
If a $f_{k}^{*}-f_{k}^{-}(x_{k+1})\leq \varepsilon$ ${\ displaystyle f_ {k} ^ {*} - f_ {k} ^ {-} (x_ {k + 1}) \ leq \ varepsilon}$ - stop. Minimum found at $x_{k+1}$ ${\ displaystyle x_ {k + 1}}$ .
Being tested $f_{k+1}=f(x_{k+1})$ ${\ displaystyle f_ {k + 1} = f (x_ {k + 1})}$ . $k:=k+1$ ${\ displaystyle k: = k + 1}$ . Adjusted minorant. Return to step 2.

Convergence theorem

Let be $K$ ${\ displaystyle K}$ - compact. $f(x)$ ${\ displaystyle f (x)}$ - Lipschitz, with constant $L>0$ ${\ displaystyle L> 0}$ , $\varepsilon >0$ ${\ displaystyle \ varepsilon> 0}$ . Then with any method of placing the starting points $x_{1},x_{2},...,x_{k}\in K$ ${\ displaystyle x_ {1}, x_ {2}, ..., x_ {k} \ in K}$ Piyavsky's method will stop in a finite number of steps. $N(f)$ ${\ displaystyle N (f)}$ , and $f_{k}^{*}-f(x^{*})\leq \varepsilon$ ${\ displaystyle f_ {k} ^ {*} - f (x ^ {*}) \ leq \ varepsilon}$ .

Literature

Piyavsky S. A. One algorithm for finding the absolute extremum of functions // Journal of Computational Mathematics and Mathematical Physics, V. 12, No. 4 (1972), pp. 885—896.
V. I. Norkin. On the Piyavsky Method for Solving the General Problem of Global Optimization, Journal of Computational Mathematics and Mathematical Physics, vol. 32, No. 7 (1992), pp. 992-1006.