Метод Пиявского

Метод Пиявского - метод нахождения глобального минимума (максимума) липшицевой функции, заданной на компакте. Прост в реализации и имеет достаточно простые условия сходимости. Подходит для широкого класса функций, производную которых, например, мы можем ограничить.

Идея метода

Пусть функция $f(x)$, заданная на $[a,b]$, удовлетворяет условию Липшица:

$\mid f(x_2)-f(x_1)\mid \le L\Vert x_2-x_1\Vert$.

Из условий Липшица очевидным образом вытекает двухстороннее неравенство, которое ограничивает ожидаемое поведение функции.

$f_i-L\Vert x-x_i\Vert \le f(x)\le f_i+L\Vert x-x_i\Vert$,

где $f_i$, точка, в которой произведено измерение.

Пусть проведено несколько испытаний $x_1,x_2,\mathrm{...},x_k\to f_1,f_2,\mathrm{...},f_k$.

Функцию $f_k^{-}(x)={\max }_{i=\overline{1,k}}^{}\{f_i-L\Vert x-x_i\Vert \}$ назовем минорантой, а $f_k^{+}(x)={\min }_{i=\overline{1,k}}^{}\{f_i+L\Vert x-x_i\Vert \}$ - мажорантой.

Графически представляют собой ломаные, поэтому метод Пиявского часто так же называют методом ломаных. Очевидно, что они ограничивают функцию с двух сторон: $f_k^{-}(x)\le f(x)\le f_k^{+}(x)$

Обозначим $f_k^{\ast }={\min }_{i=\overline{1,k}}^{}\left\{f_i\right\}$. Глобальный минимум функции $f(x^{\ast })$ может быть оценен: ${\min }_{x\in [a,b]}^{}\{f_k^{-}(x)\}\le f(x^{\ast })\le f_k^{\ast }$

Сделав указанный "коридор" меньше наперед заданного $\epsilon$, можно отыскать глобальный минимум функции. Метод Пиявского на каждом шаге производит новое испытание функции $f_{i+1}$, корректируя при этом миноранту и текущую оценку глобального минимума. Испытания проводятся в точке минимума текущей миноранты.

Алгоритм

1. Задаем (или оцениваем) константу Липшица $L>0$, точность $\epsilon >0$, и $k_0$ - количество начальных испытаний.
2. Проводим эти испытания в любых различных точках на компакте $K$. $x_1,x_2,\mathrm{...},x_k\to f_1,f_2,\mathrm{...},f_k$. $k:=k_0$
3. $f_k^{\ast }={\min }_{i=\overline{1,k}}^{}\left\{f_i\right\}$. Можно просто сравнивать со значением на предыдущей итерации.
4. $x_{k+1}=arg{\min }_{x\in {\Pi }_k}^{}{f}_k^{-}(x)$, где ${\Pi }_k=\{x\in K:f(x)\le f_k^{\ast }\}$.
5. Если $f_k^{\ast }-f_k^{-}(x_{k+1})\le \epsilon$ - остановка. Минимум найден в точке $x_{k+1}$.
6. Проводится испытание $f_{k+1}=f(x_{k+1})$. $k:=k+1$. Корректируется миноранта. Возврат на шаг 2.

Теорема сходимости

Пусть $K$ - компакт. $f(x)$ - липшицева, с константой $L>0$, $\epsilon >0$. Тогда при любом способе размещения начальных точек $x_1,x_2,\mathrm{...},x_k\in K$, метод Пиявского остановится через конечное число шагов $N(f)$, причем $f_k^{\ast }-f(x^{\ast })\le \epsilon$.

Литература

• Пиявский С. А. Один алгоритм отыскания абсолютного экстремума функций // Журнал вычислительной математики и математической физики, т.12, № 4 (1972), стр. 885—896.
• Норкин В. И. О методе Пиявского для решения общей задачи глобальной оптимизации // Журнал вычислительной математики и математической физики, т.32, № 7 (1992), стр. 992—1006.