2.4Прямой многомерный поиск

Рассмотрим функцию двух переменных. Линии постоянного уровня показаны на рис. 2.7 (линией уровня называется кривая соединяющая точки с равными значениями функции), а минимум лежит в точке х₁*,х₂*.

Рис. 2.7 Покоординатный спуск

Простейшим методом поиска является метод покоорди­натного спуска. Из точки A мы производим поиск минимума вдоль направления оси х₁ и, таким образом, переходим в точку B, в которой касательная к линии уровня параллельна оси х₁. Затем, произведя поиск из точки B в направлении оси х₂, получаем точку C, произведя по­иск вдоль оси х1, получаем точку D и т.д. Таким образом, мы приходим к оптимальной точке. Очевидным образом эту идею можно распространить на функцию n переменных. На практике этот метод оказывается слишком медленным, а в сложных случаях имеет «тупиковую» сходимость (останавливается далеко от точки минимума в связи с фиксацией направлений спуска только по координатным осям). Поэтому были разработаны более сложные методы, использующие больше информации на основании уже полученных значений функции.

Метод Хука - Дживса. Поиск состоит из последовательности шагов вокруг базисной точки, за которой в случае успеха следует поиск по образцу (рис. 2.8).

Описание процедуры поиска:

1. Выбрать начальную точку b₁ и шаг длиной h.

2. Вычислить f(X) в базисной точке b₁ с целью получения сведений о локальном пове­дении функции f(X), которые будут использоваться для нахождения подходящего направле­ния поиска по образцу:

1. 

   Рис. 2.33 Поиск по образцу

   Вычисляется значение функции f(X) в базисной точке b₁.

2. Каждая переменная по очереди изменяется прибавлением шага h. Таким образом, вычисляется значение функции , где - единичный вектор в направлении оси . Если это приводит к уменьшению значения функции, то заменяется на . В противном случае вычисляется значение функции , и если ее значение уменьши­лось, то заменяется значением . Если ни один из проделанных шагов не приво­дит к уменьшению значения функции, то точка остается неизменной и рассматриваются изменения в направлении оси х_j+1, то есть находится значение функции и т.д. Когда будут рассмотрены все n переменных, мы будим иметь новую базисную точку.

1. Если b₂=b₁, то есть уменьшение функции не было достигнуто, то исследование про­должается вокруг той же базисной точки, но с уменьшенной длиной шага. На практике удов­летворительным является уменьшение шага в десять раз от начальной длины.

2. Если b₂b₁, то производится поиск по образцу.

3. При поиске по образцу используется информация, полученная в процессе исследо­вания, и минимизация функции завершается поиском в направлении заданном образцом. Эта процедура производится следующим образом:

1. Разумно двигаться из базисной точки b₂ в направлении b₂b₁, поскольку поиск в этом направлении уже привел к уменьшению функции.

2. Затем исследование следует продолжить вокруг данной точки.

3. Если наименьшее значение на шаге C.2 меньше значения в базисной точке b₂ (в общем случае b_j+1), то получим новую базисную точку b₃ (b_j+2), после чего следует повторить шаг C.1. В противном случае - не производить поиск по образцу из точки b₂ (b_j+1), а про­должить исследование в точке b₂ (b_j+1).

3. Завершить этот процесс, когда длина шага будет уменьшена до требуемого значе­ния, определяемого точностью расчетов.