WikiSort.ru - Программирование

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

Идея метода

Пусть функция ${\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.