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

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

Описание

Разложим градиент <math>\vec{g}(\vec{x}_k)</math> исходной функции в ряд Тейлора в окрестности точки очередного приближения <math>\vec{x}_k</math> по степеням следующего шага алгоритма <math>\vec{s}_k</math>:

<math>\vec{g}(\vec{x}_k+\vec{s}_k)\approx \vec{g}(\vec{x}_k)+G(\vec{x}_k)\vec{s}_k</math>

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

<math>B_{k+1}\vec{s}_k=\vec{y}_k</math>,

где <math>\vec{y}_k=\vec{g}(\vec{x}_k+\vec{s}_k)- \vec{g}(\vec{x}_k)</math>

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

На каждой итерации с помощью <math>B_k</math> определяется следующее направление поиска <math>\vec{p}_k</math>, и матрица <math>B</math> обновляется с учётом вновь полученной информации о кривизне:

<math>B_k\vec{p}_k=-\vec{g}(\vec{x}_k)</math>

<math>B_{k+1}=B_k+U_k</math>,

где <math>U_k</math> — матрица, характеризующая поправку, вносимую на очередном шаге.

В качестве начального приближения <math>B_0</math> кладут единичную матрицу, таким образом первое направление <math>\vec{p}_0</math> будет в точности совпадать с направлением наискорейшего спуска.

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

Один шаг алгоритма даёт информацию о кривизне вдоль одного направления, поэтому ранг матрицы <math>U_k</math> полагают малым, и даже единичным:

<math>B_{k+1}=B_k+\vec{u}\vec{v}^T</math>

где <math>\vec{u}</math> и <math>\vec{v}</math> некоторые вектора.

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

<math>(B_k+\vec{u}\vec{v}^T)\vec{s}_k=\vec{y}_k</math>

<math>\vec{u}(\vec{v}^T\vec{s}_k)=\vec{y}_k-B_k\vec{s}_k</math>

Полагая, что предыдущая матрица <math>B_k</math> на очередном шаге квазиньютоновскому условию не удовлетворяет (т.е. разность в правой части не равна нулю), и что вектор <math>\vec{v}</math> не ортогонален <math>\vec{s}_k</math>, получают выражение для <math>\vec{u}</math> и <math>B_{k+1}</math>:

<math>\vec{u}=\frac{1}{\vec{v}^T\vec{s}_k}(\vec{y}_k-B_k\vec{s}_k)</math>

<math>B_{k+1}=B_k+\frac{1}{\vec{v}^T\vec{s}_k}(\vec{y}_k-B_k\vec{s}_k)\vec{v}^T</math>

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

<math>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</math>

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

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

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

<math>B^{(1)}=B^{(0)}+\frac{1}{\vec{v}^T\vec{s}_k}(\vec{y}_k-B^{(0)}\vec{s}_k)\vec{v}^T</math>

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

<math>B^{(2)}=\frac{B^{(1)}+B^{(1)T}}{2}</math>

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

<math>B^{(2j+1)}=B^{(2j)}+\frac{1}{\vec{v}^T\vec{s}_k}(\vec{y}_k-B^{(2j)}\vec{s}_k)\vec{v}^T</math>

<math>B^{(2j+2)}=\frac{B^{(2j+1)}+B^{(2j+1)T}}{2}</math>

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

<math>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</math>

При выборе различных <math>\vec{v}</math> (не ортогональных <math>\vec{s}_k</math>) получаются различные формулы пересчёта матрицы <math>B</math>:

• <math>\vec{v}=\vec{y}_k-B_k\vec{s}_k</math> приводит к симметричной формуле ранга один;
• <math>\vec{v}=\vec{s}_k</math> приводит к симметричной формуле Пауэлла — Бройдена (PSB);
• <math>\vec{v}=\vec{y}_k</math> приводит к симметричной формуле Девидона — Флетчера — Пауэлла (DFP):

<math>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</math>,

где <math>\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</math>

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

<math>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</math>

Литература

• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = practical optimization.

Отрывок, характеризующий Квазиньютоновские методы

– Ну, теперь прощай! – Он дал поцеловать сыну свою руку и обнял его. – Помни одно, князь Андрей: коли тебя убьют, мне старику больно будет… – Он неожиданно замолчал и вдруг крикливым голосом продолжал: – а коли узнаю, что ты повел себя не как сын Николая Болконского, мне будет… стыдно! – взвизгнул он.
– Этого вы могли бы не говорить мне, батюшка, – улыбаясь, сказал сын.
Старик замолчал.
– Еще я хотел просить вас, – продолжал князь Андрей, – ежели меня убьют и ежели у меня будет сын, не отпускайте его от себя, как я вам вчера говорил, чтоб он вырос у вас… пожалуйста.
– Жене не отдавать? – сказал старик и засмеялся.
Они молча стояли друг против друга. Быстрые глаза старика прямо были устремлены в глаза сына. Что то дрогнуло в нижней части лица старого князя.
– Простились… ступай! – вдруг сказал он. – Ступай! – закричал он сердитым и громким голосом, отворяя дверь кабинета.
– Что такое, что? – спрашивали княгиня и княжна, увидев князя Андрея и на минуту высунувшуюся фигуру кричавшего сердитым голосом старика в белом халате, без парика и в стариковских очках.
Князь Андрей вздохнул и ничего не ответил.
– Ну, – сказал он, обратившись к жене.
И это «ну» звучало холодною насмешкой, как будто он говорил: «теперь проделывайте вы ваши штуки».
– Andre, deja! [Андрей, уже!] – сказала маленькая княгиня, бледнея и со страхом глядя на мужа.
Он обнял ее. Она вскрикнула и без чувств упала на его плечо.
Он осторожно отвел плечо, на котором она лежала, заглянул в ее лицо и бережно посадил ее на кресло.
– Adieu, Marieie, [Прощай, Маша,] – сказал он тихо сестре, поцеловался с нею рука в руку и скорыми шагами вышел из комнаты.
Княгиня лежала в кресле, m lle Бурьен терла ей виски. Княжна Марья, поддерживая невестку, с заплаканными прекрасными глазами, всё еще смотрела в дверь, в которую вышел князь Андрей, и крестила его. Из кабинета слышны были, как выстрелы, часто повторяемые сердитые звуки стариковского сморкания. Только что князь Андрей вышел, дверь кабинета быстро отворилась и выглянула строгая фигура старика в белом халате.
– Уехал? Ну и хорошо! – сказал он, сердито посмотрев на бесчувственную маленькую княгиню, укоризненно покачал головою и захлопнул дверь.



В октябре 1805 года русские войска занимали села и города эрцгерцогства Австрийского, и еще новые полки приходили из России и, отягощая постоем жителей, располагались у крепости Браунау. В Браунау была главная квартира главнокомандующего Кутузова.
11 го октября 1805 года один из только что пришедших к Браунау пехотных полков, ожидая смотра главнокомандующего, стоял в полумиле от города. Несмотря на нерусскую местность и обстановку (фруктовые сады, каменные ограды, черепичные крыши, горы, видневшиеся вдали), на нерусский народ, c любопытством смотревший на солдат, полк имел точно такой же вид, какой имел всякий русский полк, готовившийся к смотру где нибудь в середине России.
С вечера, на последнем переходе, был получен приказ, что главнокомандующий будет смотреть полк на походе. Хотя слова приказа и показались неясны полковому командиру, и возник вопрос, как разуметь слова приказа: в походной форме или нет? в совете батальонных командиров было решено представить полк в парадной форме на том основании, что всегда лучше перекланяться, чем не докланяться. И солдаты, после тридцативерстного перехода, не смыкали глаз, всю ночь чинились, чистились; адъютанты и ротные рассчитывали, отчисляли; и к утру полк, вместо растянутой беспорядочной толпы, какою он был накануне на последнем переходе, представлял стройную массу 2 000 людей, из которых каждый знал свое место, свое дело и из которых на каждом каждая пуговка и ремешок были на своем месте и блестели чистотой. Не только наружное было исправно, но ежели бы угодно было главнокомандующему заглянуть под мундиры, то на каждом он увидел бы одинаково чистую рубаху и в каждом ранце нашел бы узаконенное число вещей, «шильце и мыльце», как говорят солдаты. Было только одно обстоятельство, насчет которого никто не мог быть спокоен. Это была обувь. Больше чем у половины людей сапоги были разбиты. Но недостаток этот происходил не от вины полкового командира, так как, несмотря на неоднократные требования, ему не был отпущен товар от австрийского ведомства, а полк прошел тысячу верст.