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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Идея метода[править | править код]

Пусть функция , заданная на , удовлетворяет условию Липшица:

.

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

,

где , точка, в которой произведено измерение.

Пусть проведено несколько испытаний .

Функцию назовем минорантой, а  — мажорантой.

Графически миноранта и мажоранта представляют собой ломаные, поэтому метод Пиявского часто также называют методом ломаных. Очевидно, что они ограничивают функцию с двух сторон:

Обозначим . Глобальный минимум функции может быть оценен:

Сделав указанный «коридор» меньше наперед заданного , можно отыскать глобальный минимум функции. Метод Пиявского на каждом шаге производит новое испытание функции , корректируя при этом миноранту и текущую оценку глобального минимума. Испытания проводятся в точке минимума текущей миноранты.

Алгоритм[править | править код]

  1. Задаем (или оцениваем) константу Липшица , точность , и  — количество начальных испытаний.
  2. Проводим эти испытания в любых различных точках на компакте . .
  3. . Можно просто сравнивать со значением на предыдущей итерации.
  4. , где .
  5. Если  — остановка. Минимум найден в точке .
  6. Проводится испытание . . Корректируется миноранта. Возврат на шаг 2.

Теорема сходимости[править | править код]

Пусть  — компакт.  — липшицева, с константой , . Тогда при любом способе размещения начальных точек , метод Пиявского остановится через конечное число шагов , причем .

Литература[править | править код]

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