Методы безусловной многомерной оптимизации. Шипилов С.А. - 10 стр.

UptoLike

ВУЗ: 

НФИ КемГУ | Новокузнецк

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

Рубрика: 

10
4.3. Градиентные методы
Суть всех градиентных методов заключается в использовании вектора
градиента для определения направления движения к оптимуму. Вектор гради-
ента
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∂
∂
∂
∂
∂
∂
=∇
n
x
f
x
f
x
f
f ,,,)(
21
Kx обладает несколькими свойствами, кото-
рые и обуславливают его эффективное применение при поиске экстремальных
значений функции многих переменных. Выделим некоторые из них.
•
Вектор градиента всегда направлен в сторону наиболее быстрого возрас-
тания функции в данной точке. Поэтому очевидно, что при поиске ми-
нимальных значений функции необходимо двигаться в противополож-
ную сторону. Такое направление движения называют антиградиентом
(-∇f(x) ) или отрицательным градиентом и оно характеризует направле-
ние наиболее быстрого убывания функции.
•
Градиент всегда ортогонален линии равного уровня, проходящей через
данную точку x
(k)
.
•
Согласно необходимому условию существования экстремума функции
многих переменных в точке экстремума градиент функции обращается в
ноль. Это свойство часто используется для проверки условия окончания
поиска в градиентных методах, т.е.
ε
≤∇ )(
)(k
f x .
Общий алгоритм всех градиентных методов заключается в построении из
некоторой начальной точки x
(0)
последовательности приближений (рассматри-
ваем задачу минимизации):
x
(k+1)
= x
(k)
-λ
(k)
S
(k)
(k=0, 1, …),
где S
(k)
- единичный вектор в направлении градиента целевой функции f(x)
в точке x
(k)
:
2
2
2
2
1
)(
)(
)(
)(
)(
)(
)(
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∂
∂
++
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∂
∂
+
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∂
∂
∇
=
∇
∇
=
n
k
k
k
k
x
f
x
f
x
f
f
f
f
S
L
x
x
x
;
λ
(k)
– величина шага в направлении градиента.
4.3.1.
Метод крутого восхождения Бокса – Уилсона
Метод крутого восхождения Бокса – Уилсона представляет собой поша-
говую процедуру движения по поверхности отклика, в которой для оценки со-
ставляющих градиента ∇f(x) = [b
0
(k)
, b
1
(k)
, b
2
(k)
, …, b
n
(k)
] используется линейное
уравнение регрессии f(x)=b
0
(k)
+b
1
(k)
x
1
+b
2
(k)
x
2
+...+b
n
(k)
x
n
, полученное в ре-
зультате планирования эксперимента в окрестности точки x
(k)
.
Затем совершается движение по поверхности отклика в направлении гра-
диента с величиной шага, пропорциональной произведению коэффициента b
j
(k)
на интервал варьирования ∆x
j
. Движение по поверхности осуществляется до тех
пор, пока параметр оптимизации не начнет увеличиваться (в случае поиска ми-
нимума). В полученной точке вновь производится планирование эксперимента 
                                           10
                             4.3. Градиентные методы

     Суть всех градиентных методов заключается в использовании вектора
градиента для определения направления движения к оптимуму. Вектор гради-
                   ⎛ ∂f ∂f          ∂f ⎞
ента   ∇f (x) = ⎜⎜      ,      ,K ,      ⎟⎟ обладает несколькими свойствами, кото-
                     ∂
                   ⎝ 1x   ∂x 2      ∂x n ⎠
рые и обуславливают его эффективное применение при поиске экстремальных
значений функции многих переменных. Выделим некоторые из них.
    • Вектор градиента всегда направлен в сторону наиболее быстрого возрас-
      тания функции в данной точке. Поэтому очевидно, что при поиске ми-
      нимальных значений функции необходимо двигаться в противополож-
      ную сторону. Такое направление движения называют антиградиентом
      (-∇f(x) ) или отрицательным градиентом и оно характеризует направле-
      ние наиболее быстрого убывания функции.
    • Градиент всегда ортогонален линии равного уровня, проходящей через
      данную точку x(k).
    • Согласно необходимому условию существования экстремума функции
      многих переменных в точке экстремума градиент функции обращается в
      ноль. Это свойство часто используется для проверки условия окончания
      поиска в градиентных методах, т.е. ∇f (x (k ) ) ≤ ε .
      Общий алгоритм всех градиентных методов заключается в построении из
некоторой начальной точки x(0) последовательности приближений (рассматри-
ваем задачу минимизации):
                         x(k+1)= x(k)-λ(k)S(k)       (k=0, 1, …),
             (k)
      где S - единичный вектор в направлении градиента целевой функции f(x)
                               ∇f ( x ( k ) )                  ∇f ( x ( k ) )
в точке x(k):     S (k ) =            (k )
                                              =                                         ;
                               ∇f ( x )                  2
                                                ⎛ ∂f ⎞ ⎛ ∂f ⎞
                                                                      2
                                                                              ⎛ ∂f ⎞
                                                                                      2

                                                ⎜⎜     ⎟⎟ + ⎜⎜      ⎟⎟ + L + ⎜⎜    ⎟⎟
                                                   ∂x
                                                 ⎝ 1⎠ ⎝ 2⎠     ∂x               ∂x
                                                                              ⎝ n⎠
          λ(k) – величина шага в направлении градиента.

              4.3.1. Метод крутого восхождения Бокса – Уилсона

      Метод крутого восхождения Бокса – Уилсона представляет собой поша-
говую процедуру движения по поверхности отклика, в которой для оценки со-
ставляющих градиента ∇f(x) = [b0(k), b1(k), b2(k), …, bn(k)] используется линейное
уравнение регрессии f(x)=b0(k)+b1(k)x1+b2(k)x2+...+bn(k)xn,     полученное в ре-
                                                                (k)
зультате планирования эксперимента в окрестности точки x .
      Затем совершается движение по поверхности отклика в направлении гра-
диента с величиной шага, пропорциональной произведению коэффициента bj(k)
на интервал варьирования ∆xj. Движение по поверхности осуществляется до тех
пор, пока параметр оптимизации не начнет увеличиваться (в случае поиска ми-
нимума). В полученной точке вновь производится планирование эксперимента

Страницы