1.6. Методы нулевого порядка (методы прямого поиска)

1.6.1. Методы аппроксимации

В их основе лежит аппроксимация градиента и матрицы вторых производных с помощью конечных разностей.

Пусть e_j - орт j-й оси.

f (x + e_j)  f(x) + (f/x)_j + O(²)

f/x_j  ( f(x + e_j) - f(x) )/   ( f(x + e_j) - f(x - e_j) )/ (2)

Здесь под градиентом понимается конечная разность. Если  слишком мала, то слишком велики погрешности при вычислении производных. Если  велика, то из-за O(²) погрешности тоже велики. Таким образом, проблема этих методов - выбор .

2. Метод покоординатного спуска

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

Алгоритм:

1. j :=1

2. min f(x^’-e_j)=f(x^’’), x^’’:= x’- *e_j

3. j:=j+1, x^’= x^’’

4. if j  n then goto 2)

5. if not (условие окончания цикла) then goto 1

Достоинство:

Требуется min функции вдоль только одной прямой.

1.6.3. Метод симплексов (Нелдера-Мида)

Алгоритм:

1.Фиксируем x_o…x_n ( n+1- точка)

Если n =2 , то выбираем равнобедренный треугольник.

2

.

т.е. вычисляем отражённую точку.

Если f(x_j^’) < f(x_j), то x_j := x_j^’; k:=0, иначе k:=k+1

где k- количество идущих подряд неудачных отражений

3. Если k<n, то (если j<n, то j:=j+1 , иначе j:=0) goto 2.

4.Иначе сжатие: x_l = argmin f(x_j), 0 j  n - ищем вершину, в которой функция минимальна (то есть наименьшее значение из всех существующих вершин.

5. Cжатие: x_j = x_l + ( x_j - x_l), j (сжатие в  раз).

6. Если ||x₀ – x₁||, то j:=0, goto 2.

7. Печать x_l.

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

Существует много модификации метода.

1.6.4. Метод Пауэлла (сопряженных направлений)

Идея: Для двух точек x₀,x₁ делается шаг в произвольном направлении p_0. Получаем точки x₂,x_3. Следующий шаг делаем в направлении p₁. Находится x*.

p₁= x₃-x₂ x₂ x₃p₁

x*

p₀ p₁

x₀ x₁

Утверждается, что (Ap₁,p_o)=0.

Поэтому для квадратичной функции метод сойдется за n-шагов. Это один из лучших методов прямого поиска.

1.7. Методы прямого поиска в задачах одномерной минимизации.

Схема метода: x_k+1 = x_k + t_kS_k , где S_k -направление.

Необходимо определить t_k.. Для этого надо найти минимум функции одной переменной (t) = f(x_k + tS_k). Будем искать точку локального минимума, поэтому ограничимся унимодальными функциями, т.е. имеющими один минимум. Больше ничего о функции неизвестно. Только можно вычислить (измерить) значения функции в точках.

1.7.1. Метод квадратичной интерполяции.

Пусть функция задана на прямой, даны при этом точки a<b<c, и , точка минимума в [a, c]

Через эти точки проведем параболу:

Положим:

, т.е. имеем 3 уравнения и 3 неизвестных g₀, g₁, g₂.

Находим g₀, g₁, g₂

Рассмотрим два случая:

1. 

2. 

Так поступаем до тех пор, пока точка не окажется в достаточно малой окрестности одной из трех точекa, b, c. После чего такую точку считаем точкой минимума.

Метод можно обобщить на случай кубических и т.д. функций, но потребуется вычислять большее количество точек.