Квазиньютоновские методы
Войти  |  Регистрация
Авторизация
» » Квазиньютоновские методы

Квазиньютоновские методы



Квазиньютоновские методы — методы оптимизации, основанные на накоплении информации о кривизне целевой функции по наблюдениям за изменением градиента, чем принципиально отличаются от ньютоновских методов. Класс квазиньютоновских методов исключает явное формирование матрицы Гессе, заменяя её некоторым приближением.

Описание

Разложим градиент g → ( x → k ) {displaystyle {vec {g}}({vec {x}}_{k})} исходной функции в ряд Тейлора в окрестности точки очередного приближения x → k {displaystyle {vec {x}}_{k}} по степеням следующего шага алгоритма s → k {displaystyle {vec {s}}_{k}} :

g → ( x → k + s → k ) ≈ g → ( x → k ) + G ( x → k ) s → k {displaystyle {vec {g}}({vec {x}}_{k}+{vec {s}}_{k})approx {vec {g}}({vec {x}}_{k})+G({vec {x}}_{k}){vec {s}}_{k}}

Тогда оценка матрицы Гессе B k + 1 {displaystyle B_{k+1}} должна удовлетворять равенству:

B k + 1 s → k = y → k {displaystyle B_{k+1}{vec {s}}_{k}={vec {y}}_{k}} ,

где y → k = g → ( x → k + s → k ) − g → ( x → k ) {displaystyle {vec {y}}_{k}={vec {g}}({vec {x}}_{k}+{vec {s}}_{k})-{vec {g}}({vec {x}}_{k})}

это условие называют квазиньютоновским.

На каждой итерации с помощью B k {displaystyle B_{k}} определяется следующее направление поиска p → k {displaystyle {vec {p}}_{k}} , и матрица B {displaystyle B} обновляется с учётом вновь полученной информации о кривизне:

B k p → k = − g → ( x → k ) {displaystyle B_{k}{vec {p}}_{k}=-{vec {g}}({vec {x}}_{k})} B k + 1 = B k + U k {displaystyle B_{k+1}=B_{k}+U_{k}} ,

где U k {displaystyle U_{k}} — матрица, характеризующая поправку, вносимую на очередном шаге.

В качестве начального приближения B 0 {displaystyle B_{0}} кладут единичную матрицу, таким образом первое направление p → 0 {displaystyle {vec {p}}_{0}} будет в точности совпадать с направлением наискорейшего спуска.

Поправка единичного ранга

Один шаг алгоритма даёт информацию о кривизне вдоль одного направления, поэтому ранг матрицы U k {displaystyle U_{k}} полагают малым, и даже единичным:

B k + 1 = B k + u → v → T {displaystyle B_{k+1}=B_{k}+{vec {u}}{vec {v}}^{T}}

где u → {displaystyle {vec {u}}} и v → {displaystyle {vec {v}}} некоторые вектора.

Тогда, квазиньютоновское условие примет вид:

( B k + u → v → T ) s → k = y → k {displaystyle (B_{k}+{vec {u}}{vec {v}}^{T}){vec {s}}_{k}={vec {y}}_{k}} u → ( v → T s → k ) = y → k − B k s → k {displaystyle {vec {u}}({vec {v}}^{T}{vec {s}}_{k})={vec {y}}_{k}-B_{k}{vec {s}}_{k}}

Полагая, что предыдущая матрица B k {displaystyle B_{k}} на очередном шаге квазиньютоновскому условию не удовлетворяет (т.е. разность в правой части не равна нулю), и что вектор v → {displaystyle {vec {v}}} не ортогонален s → k {displaystyle {vec {s}}_{k}} , получают выражение для u → {displaystyle {vec {u}}} и B k + 1 {displaystyle B_{k+1}} :

u → = 1 v → T s → k ( y → k − B k s → k ) {displaystyle {vec {u}}={frac {1}{{vec {v}}^{T}{vec {s}}_{k}}}({vec {y}}_{k}-B_{k}{vec {s}}_{k})} B k + 1 = B k + 1 v → T s → k ( y → k − B k s → k ) v → T {displaystyle B_{k+1}=B_{k}+{frac {1}{{vec {v}}^{T}{vec {s}}_{k}}}({vec {y}}_{k}-B_{k}{vec {s}}_{k}){vec {v}}^{T}}

Из соображений симметричности матрицы Гессе, вектор v → {displaystyle {vec {v}}} берут коллинеарным u → {displaystyle {vec {u}}} :

B k + 1 = B k + 1 ( y → k − B k s → k ) T s → k ( y → k − B k s → k ) ( y → k − B k s → k ) T {displaystyle B_{k+1}=B_{k}+{frac {1}{({vec {y}}_{k}-B_{k}{vec {s}}_{k})^{T}{vec {s}}_{k}}}({vec {y}}_{k}-B_{k}{vec {s}}_{k})({vec {y}}_{k}-B_{k}{vec {s}}_{k})^{T}}

Полученное уравнение называется симметричной формулой ранга один.

Поправки ранга два

Один из способов конструирования поправок ранга два заключается в построении сходящейся последовательности матриц B ( j ) {displaystyle B^{(j)}} . В качестве начального значения B ( 0 ) {displaystyle B^{(0)}} берут B k {displaystyle B_{k}} , B ( 1 ) {displaystyle B^{(1)}} вычисляют по формуле:

B ( 1 ) = B ( 0 ) + 1 v → T s → k ( y → k − B ( 0 ) s → k ) v → T {displaystyle B^{(1)}=B^{(0)}+{frac {1}{{vec {v}}^{T}{vec {s}}_{k}}}({vec {y}}_{k}-B^{(0)}{vec {s}}_{k}){vec {v}}^{T}}

После чего её симметризуют:

B ( 2 ) = B ( 1 ) + B ( 1 ) T 2 {displaystyle B^{(2)}={frac {B^{(1)}+B^{(1)T}}{2}}}

Однако полученная матрица больше не удовлетворяет квазиньютоновскому условию. Чтобы это исправить, процедуру повторяют. В результате на j {displaystyle j} -м шаге:

B ( 2 j + 1 ) = B ( 2 j ) + 1 v → T s → k ( y → k − B ( 2 j ) s → k ) v → T {displaystyle B^{(2j+1)}=B^{(2j)}+{frac {1}{{vec {v}}^{T}{vec {s}}_{k}}}({vec {y}}_{k}-B^{(2j)}{vec {s}}_{k}){vec {v}}^{T}} B ( 2 j + 2 ) = B ( 2 j + 1 ) + B ( 2 j + 1 ) T 2 {displaystyle B^{(2j+2)}={frac {B^{(2j+1)}+B^{(2j+1)T}}{2}}}

Предел этой последовательности равен:

B k + 1 = B k + 1 v → T s → k [ ( y → k − B k s → k ) v → T + v → ( y → k − B k s → k ) T ] − ( y → k − B k s → k ) T s → k ( v → T s → k ) 2 v → v → T {displaystyle B_{k+1}=B_{k}+{frac {1}{{vec {v}}^{T}{vec {s}}_{k}}}[({vec {y}}_{k}-B_{k}{vec {s}}_{k}){vec {v}}^{T}+{vec {v}}({vec {y}}_{k}-B_{k}{vec {s}}_{k})^{T}]-{frac {({vec {y}}_{k}-B_{k}{vec {s}}_{k})^{T}{vec {s}}_{k}}{({vec {v}}^{T}{vec {s}}_{k})^{2}}}{vec {v}}{vec {v}}^{T}}

При выборе различных v → {displaystyle {vec {v}}} (не ортогональных s → k {displaystyle {vec {s}}_{k}} ) получаются различные формулы пересчёта матрицы B {displaystyle B} :

  • v → = y → k − B k s → k {displaystyle {vec {v}}={vec {y}}_{k}-B_{k}{vec {s}}_{k}} приводит к симметричной формуле ранга один;
  • v → = s → k {displaystyle {vec {v}}={vec {s}}_{k}} приводит к симметричной формуле Пауэлла — Бройдена (PSB);
  • v → = y → k {displaystyle {vec {v}}={vec {y}}_{k}} приводит к симметричной формуле Девидона — Флетчера — Пауэлла (DFP):
B k + 1 = B k − 1 s → k T B k s → k B k s → k s → k T B k + 1 y → k T s → k y → k y → k T + ( s → k T B k s → k ) ω → k ω → k T {displaystyle B_{k+1}=B_{k}-{frac {1}{{vec {s}}_{k}^{T}B_{k}{vec {s}}_{k}}}B_{k}{vec {s}}_{k}{vec {s}}_{k}^{T}B_{k}+{frac {1}{{vec {y}}_{k}^{T}{vec {s}}_{k}}}{vec {y}}_{k}{vec {y}}_{k}^{T}+({vec {s}}_{k}^{T}B_{k}{vec {s}}_{k}){vec {omega }}_{k}{vec {omega }}_{k}^{T}} ,

где ω → k = 1 y → k T s → k y → k − 1 s → k T B k s → k B k s → k {displaystyle {vec {omega }}_{k}={frac {1}{{vec {y}}_{k}^{T}{vec {s}}_{k}}}{vec {y}}_{k}-{frac {1}{{vec {s}}_{k}^{T}B_{k}{vec {s}}_{k}}}B_{k}{vec {s}}_{k}}

Нетрудно проверить, что ω → k {displaystyle {vec {omega }}_{k}} ортогонален s → k {displaystyle {vec {s}}_{k}} . Таким образом добавление слагаемого ω → k ω → k T {displaystyle {vec {omega }}_{k}{vec {omega }}_{k}^{T}} не нарушит ни квазиньютоновского условия, ни условия симметричности. Поэтому проводился ряд теоретических исследований, подвергавших последнее слагаемое масштабированию на предмет получения наилучшего приближения. В результате была принята точка зрения, что наилучшим вариантом является отвечающий полному отсутствию последнего слагаемого. Этот вариант пересчёта известен под именем формулы Бройдена — Флетчера — Гольдфарба — Шанно (BFGS):

B k + 1 = B k − 1 s → k T B k s → k B k s → k s → k T B k + 1 y → k T s → k y → k y → k T {displaystyle B_{k+1}=B_{k}-{frac {1}{{vec {s}}_{k}^{T}B_{k}{vec {s}}_{k}}}B_{k}{vec {s}}_{k}{vec {s}}_{k}^{T}B_{k}+{frac {1}{{vec {y}}_{k}^{T}{vec {s}}_{k}}}{vec {y}}_{k}{vec {y}}_{k}^{T}}
Добавлено Admin 3-12-2020, 12:02 Просмотров: 61
Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent