Метод Дэвидона-Флетчера-Пауэлла

Флетчер и Па­у­элл (R. Fletcher, M. J. D. Powell; 1963-1971) пред­ло­жи­ли вы­со­ко­эф­фе­к­тив­ный ме­тод ми­ни­ми­за­ции про­из­воль­ных функ­ций, со­еди­ня­ю­щий свой­ст­ва как ме­то­дов со­пря­жен­ных на­пра­в­ле­ний, так и ме­то­дов нью­то­нов­ско­го ти­па, и при этом не тре­бу­ю­щий вычис­ле­ния вто­рых про­из­вод­ных. По­л­ное обо­с­но­ва­ние это­го ме­то­да тре­бу­ет до­воль­но мно­го ме­с­та, по­э­то­му мы ог­ра­ничим­ся из­ло­же­ни­ем ос­нов­ных идей и расчет­ных фор­мул.

В ос­но­ве ме­то­да Флетчера-Па­у­эл­ла ле­жат ите­ра­ции нью­то­нов­ско­го ти­па (12), но вме­сто точной ма­т­ри­цы Гес­се H ис­поль­зу­ет­ся не­ко­то­рое при­бли­же­ние к ней, ко­то­рое по­сте­пен­но уточня­ет­ся по ме­ре при­бли­же­ния к ми­ни­му­му.

На k-м ша­ге ал­го­рит­ма ис­поль­зу­ет­ся на­пра­в­ле­ние по­ис­ка s_k, ко­то­рое оп­ре­де­ля­ет­ся как

s_k=-A_kg_k, (33)

где g_k – гра­ди­ент ми­ни­ми­зи­ру­е­мой функ­ции, вычис­лен­ный в началь­ной точке по­ис­ка x_k. Сле­ду­ю­щая точка x_k+1 по­лучает­ся в ре­зуль­та­те од­но­мер­ной ми­ни­ми­за­ции:

x_k+1=x_k+l_ks_k, (34)

причем l_k оп­ре­де­ля­ет­ся с по­мо­щью про­це­ду­ры ку­бичес­кой ин­тер­по­ля­ции Дэ­ви­до­на (см. п. 1.3). По­э­то­му весь ал­го­ритм обычно на­зы­ва­ют ме­то­дом Дэ­ви­до­на-Флетчера-Па­у­эл­ла (ДФП).

Срав­ни­вая урав­не­ния (12) и (33), ви­дим, что A_k име­ет смысл при­бли­же­ния к H^-1. При­ме­не­ние урав­не­ния (33) оз­начает, что вме­сто ан­ти­гра­ди­ен­та -g_k для спу­с­ка к ми­ни­му­му бе­рет­ся на­пра­в­ле­ние, по­лучае­мое в ре­зуль­та­те по­во­ро­та с по­мо­щью ма­т­ри­цы A_k. Эта гео­ме­т­ричес­кая ин­тер­пре­та­ция уже об­су­ж­да­лась в свя­зи с ме­то­дом Нью­то­на (см. рис. 8). Для то­го, что­бы по­вер­ну­тый ве­к­тор s_kбыл, тем не ме­нее, все­гда на­пра­в­лен в сто­ро­ну по­ни­же­ния значений функ­ции, не­об­хо­ди­мо, что­бы ма­т­ри­ца A_k бы­ла по­ло­жи­тель­но оп­ре­де­лен­ной.

На пер­вом ша­ге ал­го­рит­ма ДФП в качес­т­ве A_k бе­рут еди­ничную ма­т­ри­цу (A₁=E), так что s₁=-g₁, т. е. вначале дви­же­ние не от­личает­ся от ме­то­да ско­рей­ше­го спу­с­ка. За­тем ма­т­ри­цу A_k по­с­ле ка­ж­до­го ша­га кор­ре­к­ти­ру­ют, при­ме­няя сле­ду­ю­щие фор­му­лы:

Dx_k=x_k+1-x_k=l_ks_k=-l_kA_kg_k из­ме­не­ние x на k-м ша­ге,

Dg_k=g_k+1-g_k из­ме­не­ние гра­ди­ен­та на k-м ша­ге,

, ,

. (35)

Мо­ж­но по­ка­зать, что в случае ми­ни­ми­за­ции ква­д­ра­тичной функ­ции N пе­ре­мен­ных на­пра­в­ле­ния s_k ста­но­вят­ся со­пря­жен­ны­ми, а ма­т­ри­ца A_k через N ша­гов пре­вра­ща­ет­ся в H^-1, так что последний шаг приводит в точку минимума. Ес­ли функ­ция не яв­ля­ет­ся ква­д­ра­тичной, то про­цесс, во­об­ще го­во­ря, не за­канчивает­ся за N ша­гов, но A_k по ме­ре при­бли­же­ния к точке ми­ни­му­ма асим­п­то­тичес­ки стре­мит­ся к H^-1, а ско­рость схо­ди­мо­сти в пре­де­ле ста­но­вит­ся ква­д­ра­тичной, как у ме­то­да Нью­то­на.

Поиск по сайту: