Методы с использованием производных

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

М е т о д с е к у щ и х

Этот метод ориентирован на нахождение корня уравнения J_a(a)=0 в интервале aÎ[a₁, a₂], на концах которого w₁=J_a(a₁)<0 и w₂=J_a(a₂)>0. В этом методе используется линейная аппроксимация производной J_a и алгоритм поиска следующий.

{{{ Начало алгоритма.

1) Запоминается крайняя точка a_z=a₁.

2) Из подобия треугольников (см. рис.1.2.5) определяем следующее приближение стационарной точки по формуле:

(1.2.9)

В этой точке рассчитывается значение производной w₃=J_a(a₃).

3) Если w₃>0, то эта точка берется в качестве новой правой точки: a₂=a₃, w₂=w₃, иначе - в качестве левой: a₁=a₃, w₁=w₃.

4) Если |a_z-a₃|<e, то поиск минимума окончен, иначе запоминается новое значение a_z=a₃ и переходим к пункту 2).

}}} Конец алгоритма.

Рис.1.2.5

Алгоритм метода секущих

М е т о д к у б и ч е с к о й а п п р о к с и м а ц и и

Целевая функция в этом методе аппроксимируется полиномом третьей степени. Логическая структура метода аналогична схеме метода квадратичной аппроксимации. Однако в данном методе для аппроксимации используются только две опорные точки a₁ и a₂ и значения функций и производных в этих точках: J₁=J(a₁), J₂=J(a₂), w₁=J_a(a₁), w₂=J_a(a₂). Аппроксимирующий полином можно искать в виде:

Y(a)=a₀+a₁×(a-a₁)+a₂×(a-a₁)×(a-a₂)+a₃×(a-a₁)²×(a-a₂). (1.2.10)

Коэффициенты a_0-3 определяются путем решения следующей системы

линейных уравнений:

(1.2.11)

Приравняв к нулю производную от полинома (1.2.10) получим квадратное уравнение относительно a, решение которого определяет минимальную точку кубического полинома и для случая w₁<0 имеет вид (см. [8]):

a_min=(a₂-a₁)×(1-(w₂+b-a)/c), (1.2.12)

где a=3×(J₁-J₂)/(a₂-a₁)+w₁+w₂,

b=(a²-w₁×w₂)^1/2,

c=w₂-w₁+2×b.

Алгоритм данного метода может выглядеть следующим образом.

{{{ Начало алгоритма.

1) Запоминаем граничное значение переменной a_z=a₁.

2) По формулам (1.2.12) определяем a_min и рассчитываем в этой точке J_min=J(a_min) и w_min=J_a(a_min).

3) Если J_min<J₁ и w_min<0, то производим следующую замену: a₁=a_min, J₁=J_min, w₁=w_min, иначе: a₂=a_min, J₂=J_min, w₂=w_min.

4) Если |w_min|<e или |a_min-a_z|<e, то поиск заканчивается, иначе полагаем a_z=a_min и переходим к пункту 2).

}}} Конец алгоритма.

Дата добавления: 2015-11-14