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

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

Идея метода

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

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

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

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

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

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

Функцию ${\displaystyle f_{k}^{-}(x)=\max _{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\}}$ - мажорантой.

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

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

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

Алгоритм

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

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

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

Литература

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

Эта страница в последний раз была отредактирована 31 января 2018 в 21:47.