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

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

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

Идея метода

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

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

.

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

,

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

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

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

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

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

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

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

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

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

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

Литература

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