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

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

Идея метода

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

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

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

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

где $f_{i}$, точка, в которой произведено измерение.

Пусть проведено несколько испытаний $x_{1},x_{2},...,x_{k}\rightarrow f_{1},f_{2},...,f_{k}$.

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

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

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

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

Алгоритм

1. Задаем (или оцениваем) константу Липшица $L>0$, точность $\varepsilon >0$, и $k_{0}$ - количество начальных испытаний.
2. Проводим эти испытания в любых различных точках на компакте $K$. $x_{1},x_{2},...,x_{k}\rightarrow f_{1},f_{2},...,f_{k}$. $k:=k_{0}$
3. $f_{k}^{*}=\min _{i={\overline {1,k}}}^{}\left\{f_{i}\right\}$. Можно просто сравнивать со значением на предыдущей итерации.
4. $x_{k+1}=arg\min _{x\in \Pi _{k}}^{}f_{k}^{-}(x)$, где $\Pi _{k}=\left\{x\in K:f(x)\leq f_{k}^{*}\right\}$.
5. Если $f_{k}^{*}-f_{k}^{-}(x_{k+1})\leq \varepsilon$ - остановка. Минимум найден в точке $x_{k+1}$.
6. Проводится испытание $f_{k+1}=f(x_{k+1})$. $k:=k+1$. Корректируется миноранта. Возврат на шаг 2.

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

Пусть $K$ - компакт. $f(x)$ - липшицева, с константой $L>0$, $\varepsilon >0$. Тогда при любом способе размещения начальных точек $x_{1},x_{2},...,x_{k}\in K$, метод Пиявского остановится через конечное число шагов $N(f)$, причем $f_{k}^{*}-f(x^{*})\leq \varepsilon$.

Литература

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