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

Толкование

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

Идея метода

Пусть функция $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}$ , корректируя при этом миноранту и текущую оценку глобального минимума. Испытания проводятся в точке минимума текущей миноранты.

Алгоритм

Задаем (или оцениваем) константу Липшица $L > 0$ , точность $\varepsilon > 0$ , и $k_0$ - количество начальных испытаний.

Проводим эти испытания в любых различных точках на компакте $K$ . $x_1, x_2, ..., x_k \rightarrow f_1, f_2, ..., f_k$ . $k:=k_0$

$f_k^* = \min^{}_{i=\overline {1,k}} \left \{ f_i \right \}$ . Можно просто сравнивать со значением на предыдущей итерации.

$x_{k+1} = arg \min^{}_{x \in \Pi_k} f_k^-(x)$ , где $\Pi_k=\left \{ x \in K : f(x)\le f_k^* \right \}$ .

Если $f_k^* - f_k^-(x_{k+1}) \le \varepsilon$ - остановка. Минимум найден в точке $x_{k+1}$ .

Проводится испытание $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$ .

Связать^?

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

Категория:
Алгоритмы оптимизации

Игры ⚽ Нужна курсовая?

Полезное

Пометить текст и поделиться
Искать во всех словарях
Искать в переводах
Искать в Интернете

Поделиться ссылкой на выделенное