Случайный поиск. 
Методы поиска минимума функции многих переменных

Методы спуска неполноценны на неупорядоченном рельефе. Если локальных экстремумов много, то спуск из одного нулевого приближения может сойтись только к одному из локальных минимумов, не обязательно абсолютному. Тогда для исследования задачи применяют случайный поиск.

Предполагают, что интересующий нас минимум (или все минимумы) лежит в некоторой замкнутой области; линейным преобразованием координат помещают ее внутрь единичного n-мерного куба. Выбирают в этом кубе Nслучайных точек; если о расположении экстремумов заранее ничего неизвестно, то наилучшие результаты дают ЛП — последовательности точек.

Даже при миллионе пробных точек вероятность того, что хотя бы одна точка попадает в небольшую окрестность локального минимума, ничтожна мала. В самом деле, пусть диаметр котловины около минимума составляет 10% от пределов изменения каждой координаты. Тогда объем этой котловины составляет 0,1ⁿ часть объема n-мерного куба. Уже при n 6 ни одна точка в котловину не попадает.

Поэтому берут небольшое число точек N (5 — 20) nи каждую точку рассматривают как нулевое приближение. Из каждой точки совершают спуск, быстро попадая в ближайший овраг или котловину; когда шаги спуска сильно укорачиваются, его прекращают, не добиваясь высокой точности. Этого уже достаточно, чтобы судить о величине функции в ближайшем локальном минимуме с удовлетворительной точностью.

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

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

Пусть, например, координаты — это размеры деталей механической конструкции, а минимизируемая функция есть мера качества конструкции. Если нашли минимум точно, то находимся в самом центре котловины около минимума. В этом случае вариации координат влияют на функцию слабее, чем в точках, расположенных ближе к краям котловины. А безопасные вариации координат имеют в данном примере смысл допусков на точность обработки деталей. Значит, при аккуратном вычислении координат минимума можем разрешить большие допуски, т. е. удешевить обработку деталей.

Метод случайного поиска зачастую позволяет найти все локальные минимумы функции от — 10−20 переменных со сложным рельефом. Он полезен и при исследовании функции с единственным минимумом; в этом случае можно обойтись заметно меньшим числом случайных точек. Недостаток метода в том, что надо заранее задать область, в которой выбираются случайные точки. Если зададим слишком широкую область, то ее труднее детально исследовать, а если выберем слишком узкую область, то многие локальные минимумы могут оказаться вне ее. Правда, положение несколько облегчается тем, что при спусках траектории могут выйти за пределы заданной области и сойтись к лежащим вне этой области минимумам[2].