Метод прямого поиска (метод Хука-Дживса)

Суть этого метода состоит в следующем. Задаются некоторой начальной точкой х[0]. Изменяя компоненты вектора х[0], обследуют окрестность данной точки, в результате чего находят направление, в котором происходит уменьшение минимизируемой функции f(x). В выбранном направлении осуществляют спуск до тех пор, пока значение функции уменьшается. После того как в данном направлении не удается найти точку с меньшим значением функции, уменьшают величину шага спуска. Если последовательные дробления шага не приводят к уменьшению функции, от выбранного направления спуска отказываются и осуществляют новое обследование окрестности и т. д.

Алгоритм метода прямого поиска состоит в следующем.

1. Задаются значениями координат х_i[0] , i = 1, ..., п , начальной точки х[0], вектором изменения координат D х в процессе обследования окрестности, наименьшим допустимым значением е компонентов D х.

2. Полагают, что х[0] является базисной точкой х^б, и вычисляют значение f(x^б).

3. Циклически изменяют каждую координату х^б_i, i = 1, ..., п , базисной точки х^б на величину Dх_i, i = 1, ..., п , т. е. х_i[k] = х^б + D х; х_i[k]= х^б_i - ?х_i. При этом вычисляют значения f(x[k]) и сравнивают их со значением f(x^б). Если f(x[k]) < f(x^б), то соответствующая координата х_i, i = 1, ..., п , приобретает новое значение, вычисленное по одному из приведенных выражений. В противном случае значение этой координаты остается неизменным. Если после изменения последней п-йкоординаты f(x[k]) < f(x^б), то переходят к п, 4. В противном случае ‑ к п. 7.

4. Полагают, что х[k] является новой базисной точкой х^б , и вычисляют значение f(x^б).

5. Осуществляют спуск из точки х[k] > х_i[k+1] = 2х_i[k] ‑ x^б, i = 1, ..., n , где x^б - координаты предыдущей базисной точки. Вычисляют значение f(x[k+1]).

6. Как и в п. 3, циклически изменяют каждую координату точки х[k+1], осуществляя сравнение соответствующих значений функции f(х) со значением f (х[k+1]), полученным в п. 5. После изменения последней координаты сравнивают соответствующее значение функции f(x[k]) со значением f(x^б), полученным в п. 4. Если f(x[k]) < f(x^б), то переходят к п. 4, в противном случае ‑ к п. 3. При этом в качестве базисной используют последнюю из полученных базисных точек.

7. Сравнивают значения D х и е. Если D х < е, то вычисления прекращаются. В противном случае уменьшают значения D х и переходят к п. 3.

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

Недостаток метода прямого поиска состоит в том, что в случае сильно вытянутых, изогнутых или обладающих острыми углами линий уровня целевой функции он может оказаться неспособным обеспечить продвижение к точке минимума. Действительно, в случаях, изображенных на Рис. 7.4, а и б, каким бы малым ни брать шаг в направлении х₁ или x₂ из точки х’ нельзя получить уменьшения значения целевой функции.

Рис. 7.4 ‑ Прямой поиск: невозможность продвижения к минимуму:

а – С₁ > C₂ > C₃; б ‑ С₁ > C₂

Напомним, что поверхностью уровня (на плоскости ‑ линией уровня) является поверхность, получаемая приравниванием выражения функции f(х) некоторой постоянной величине С, т. е. f(х) = С . Во всех точках этой поверхности функция имеет одно и то же значение С. Давая величине С различные значения С₁, ..., С_n, получают ряд поверхностей, геометрически иллюстрирующих характер функции.