5.19. Методы прямого поиска

Термин прямой поиск» введен Хуком и Дживсом [109]. Он относится к методам (подобным методу Хука и Дживса) поиска минимума без явного вычисления производных, аналитического или численного. Сама идея методов прямого поиска весьма привлекательна, и в целом ряде случаев они работают достаточно хорошо (см., например, обзор Бокса [391). Наш собственный опыт их применения, однако, был неудачным; градиентные методы, даже с использованием конечно-разностных аппроксимаций, работали лучше, чем методы прямого поиска при решении различных, кроме самых тривиальных, задач оценивания параметров и по надежности, и по скорости сходимости,

В обзоре Бокса [391 в качестве наилучших признаны методы, разработанные Пауэллом [158], [159]. Первый из них позволяет минимизировать функцию произвольного вида, он был улучшен Занвиллом [194]. Второй метод Пауэлла [159] разработан специально для минимизации суммы квадратов, но может быть легко адаптирован к другим задачам, которые допускают аппроксимацию Гаусса. Этот алгоритм родствен методу Гаусса, причем конечные разности берутся по направлениям поиска (а не вдоль направлений координат, как было бы в случае обычного конечно-разностного варианта метода Гаусса). Слабость этого метода вытекает из того факта, что разности берутся лишь в одном направлении на каждой итерации; таким образом, оценки производных, рассчитываемые в методе по всем другим направлениям, оказываются устаревшими. Этот эффект усиливается с ростом размерности вектора параметров.

Другие методы, нашедшие широкое применение для решения задач - это методы Хука и Дживса [109], Розенброка [169] (см. также Розенброк и Стори [170]), Буцци Феррариса [43], Брента [41] и симплекс-метод Нелдера и Мида [148]. Последний метод был адаптирован Спендли [181] специально для решения задач методом наименьших квадратов. Обзор методов прямого поиска дается в работе Флетчера [79].