Метод перебора. Одномерный метод Монте-Карло

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

Рассматривается следующая одномерная задача условной глобальной оптимизации): найти минимум, вообще говоря, многоэкстремальной функции

(

), определенной в замкнутой области допустимых значений

(1)

Метод перебора

Схема метода перебора (см. рис. 1):

Рис. 1. К схеме метода перебора.

Покрываем интервал некоторой сеткой с узлами , [1,].

Производим испытание в точке , т.е. вычисляем значения функции в этой точке.
Полагаем .
Производим испытание в точке - вычисляем значение () функции () в этой точке.
Если , то выполняем присваивания , .
Если , то выполняем присваивание 1 и переходим на п.4). Иначе - заканчиваем вычисления.

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

При выборе количества узлов сетки

[1,

] можно исходить из требуемой точности решения

– максимальный шаг сетки принять равным этой величине.

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

Одномерный метод Монте-Карло

Схема одномерного метода Монте-Карло:

Генерируем с помощью какого-либо программного генератора случайных чисел, равномерно распределенных в интервале [,], случайное число .
Производим испытание в точке - вычисляем значения функции () в этой точке.
Полагаем 2.
Аналогично п. 1) генерируем случайное число [,] .
Производим испытание в точке - вычисляем значение () функции () в этой точке.
Если , то выполняем присваивания , .
Если , то выполняем присваивание 1 и переходим на п. 4). Иначе - заканчиваем вычисления. Здесь – количество испытаний.
Принимаем в качестве приближенного значения точки глобального минимума функции () на интервале [,] или каким-либо из рассмотренных одномерных методов локальной оптимизации организуем в окрестности точки поиск локального минимума этой функции

При достаточно большом

метода гарантирует нахождение глобального минимума с высокой вероятностью.