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

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

Идея метода

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

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

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

$f_i-L \| x-x_i \| \le f(x) \le 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) \le f(x) \le 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 \} \le f(x^*) \le 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)\le f_k^* \right \}$.
5. Если $f_k^* - f_k^-(x_{k+1}) \le \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^*) \le \varepsilon$.

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.