Математические методы принятия решений. Бодров В.И - 32 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

u
2
u
2
u
1
u
0
u
1
•
Рис. 3.10 Характер движения к оптимуму в методе градиента
4 Делается шаг в направлении антиградиента при поиске минимума, в результате чего попадают в
точку u
1
.
5 Процесс поиска продолжается, повторяя все этапы с п. 2, т.е. вычисляется
(
)
1
4
1
2
1
11
...,,, uuuQ
, опре-
деляется направление градиента в точке u
1
, делается шаг и т.д.
Важной задачей в этом методе является выбор шага. Если размер шага слишком мал, то движение к
оптимуму будет долгим из-за необходимости расчета целевой функции и ее частных производных в
очень многих точках. Если же шаг будет выбран слишком большим, то в районе оптимума может воз-
никнуть "рыскание", которое либо затухает слишком медленно, либо совсем не затухает. На практике
сначала шаг выбирается произвольно. Если окажется, что направление градиента в точке u
1
существен-
но отличается от направления в точке u
2
, то шаг уменьшают, если отличие векторов по направлению
мало, то шаг увеличивают. Изменение направления градиента можно определять по углу поворота гра-
диента рассчитываемого на каждом шаге по соответствующим выражениям.
Итерационный процесс поиска обычно прекращается, если вы-
полняются неравенства
()
(
)
(
)
,/,
111
δ≤−ε≤−
−−− kkkkk
uQuQuQuu
(
)
γ≤∂∂ uuQ
k
/
, где ε, δ, γ – заданные числа.
Недостатком градиентного метода является то, что при его использовании можно обнаружить толь-
ко локальный минимум целевой функции. Для нахождения других локальных минимумов поиск необ-
ходимо производить из других начальных точек.
3.4.3 Метод наискорейшего спуска
При применении метода градиента на каждом шаге вычисляются значения всех частных производ-
ных оптимизируемой функции Q по всем независимым переменным U, что при большом числе этих
переменных приводит к весьма большому времени поиска оптимума. Сократить время поиска позво-
ляет метод наискорейшего спуска, блок-схема которого отображена на рис. 3.4, где ε – точность вы-
числения,
H – величина шага, n – размерность вектора u, Q – алгоритм вычисления целевой функции Q (u), L –
количество шагов по конкретному направлению градиента функции Q.
Таким образом, в начальной точке u
0
определяется градиент целевой функции
i
u
Q
∂
∂
и, следовательно, на-
правление ее наибыстрейшего убывания; далее делается шаг спуска в этом направлении. Если значение це-
левой функции уменьшились, то делается следующий шаг в этом же самом направлении. Процедура повто-

Страницы