Методы одномерного поиска

Поиск минимума вдоль направления P является одномерным поиском относительно параметра a в выражении (1.1.2). Одномерный поиск осуществляется в два этапа.

На первом этапе определяется приближенно область параметра aÎ[a₁, a₂] в которой предполагается находится минимум целевой функции J(a). Строгих методов для этой процедуры нет. Если не вычисляются производные от целевой функции по a, то обычный алгоритм заключается в следующем (см. рис.1.2.1).

Рис.1.2.1

Алгоритм приближенного определения минимума функции

1) Задаются начальным шагом по a - h_a0, который определяют экспериментально. Начальное значение a полагают равным нулю - a=0 и h_a=h_a0.

2) Далее запоминаем текущие значения a₁=a и J₁=J(a₁) и увеличиваем значение a на величину h_a. В новой точке a₂=a₁+h_a вычисляется значение целевой функции J₂=J(a₂).

Если J₂ £ J₁ и h_a³ h_a0, то

а) шаг h_a обычно увеличивают вдвое, т.е. h_a=2×h_a, вводится система пере обозначений вида: a₀=a₁, J₀=J₁, a₁=a₂, J₁=J₂, a=a₁ и снова идем на начало пункта 1) до тех пор пока h_a не превысит начальное значение шага h_a в 2¹⁰ раз. Это означает, что в данном направлении минимум отсутствует. Иначе: б) Если h_a > h_a0, то имеется три точки по a - a₀ ,a₁ ,a₂ , заключающие внутри себя точку минимума целевой функции a_min, и можно в этом случае переходить к методу уточнения местоположения минимума, т.е. к пункту 3), в противном случае начальный шаг делим на четыре - h_a= h_a/4, полагаем a₁=a=0, J₁=J(0) и идем к пункту 2). Деление шага h_a производят до тех пор пока он не станет меньше начального шага h_a0 в 2²⁰ раз. Если он станет меньше, то в данном направлении будем считать минимума нет.

3) Уточняем местоположения минимума целевой функции по a - a_min.

В случае расчета производных от целевой функции по параметру a, алгоритм приближенного определения местоположения минимума целевой функции может быть следующим(см. рис.1.2.2).

Рис.1.2.2

Алгоритм приближенного определения минимума функции с использованием производных

1) Зададимся начальным шагом по a - h_a0, который, например, можно вычислить по формуле:

h_a=½(J_min-J(0))/(2J_a(0))½, (1.2.1)

где J_min - предполагаемое минимально возможное значение целевой функции, J_a(0) - производная от целевой функции по параметру a в начальной точке, где a=0. В общем случае эта производная вычисляется как

(1.2.2)

т.е. как проекция градиента g (X_k) на поисковое направление P_k. Если эта производная будет положительна, то это означает что в данном направлении минимум отсутствует и следует рассчитать новое поисковое направление P_нов. Начальное значение a полагают равным нулю - a=0 и h_a= h_a0.

2) Далее запоминаем текущие значения a₁=a, w₁=J_a(a₁) и J₁=J(a₁) и увеличиваем значение a на величину h_a. В новой точке a₂=a₁+ h_a вычисляется значение целевой функции J₂=J(a₂) и производная w₂=J(a₂). Если w₂<0 и J₂<J₁, то

а) вводится система пере обозначений a₁=a₂, w₁=w₂, a=a₁, J₁=J₂, шаг увеличивают в два раза - h_a=2 h_a и идем в начало пункта 1), иначе

б) переходим к пункту 3) - уточнению местоположения минимума.

3) Вызов процедуры уточнения местоположения минимума целевой функции по a на отрезке a₁ - a₂.

На втором этапе одномерного поиска осуществляется уточнение местоположения минимума целевой функции по параметру a в заданном интервале и с заданной точностью - e.

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