Метод Флетчера-Ривса

Как бы­ло по­ка­за­но в пре­ды­ду­щем раз­де­ле, за­дачу ми­ни­ми­за­ции ква­д­ра­тичной функ­ции N пе­ре­мен­ных мо­ж­но ре­шить не бо­лее чем за N од­но­мер­ных по­ис­ков, ес­ли про­во­дить их вдоль на­пра­в­ле­ний, со­пря­жен­ных от­но­си­тель­но ма­т­ри­цы A. Соб­ст­вен­но го­во­ря, ми­ни­мум ква­д­ра­тичной функ­ции не­за­ви­си­мо от чис­ла пе­ре­мен­ных мо­ж­но най­ти еще бы­ст­рее — за один шаг, ре­шив си­с­те­му ли­ней­ных урав­не­ний (16). Ме­тод со­пря­жен­ных на­пра­в­ле­ний бо­лее ин­те­ре­сен с точки зре­ния его при­ме­не­ния для ми­ни­ми­за­ции функ­ций об­ще­го ви­да.

Пусть F(x) – про­из­воль­ная функ­ция N пе­ре­мен­ных, а x*– точка ее ми­ни­му­ма (воз­мо­ж­но, ло­каль­но­го). Пред­по­ла­гая, что F(x) по мень­шей ме­ре два­ж­ды не­пре­рыв­но диф­фе­рен­ци­ру­е­ма, при­бли­жен­но пред­ста­вим ее в ок­ре­ст­но­сти x*с по­мо­щью фор­му­лы Тей­ло­ра:

(29)

где H – ма­т­ри­ца вто­рых про­из­вод­ных (ма­т­ри­ца Гес­се), вычис­лен­ная в точке x*(оп­ре­де­ле­ние H см. в раз­де­ле 2.3.2). Вы­ра­же­ние (29) не со­дер­жит пер­вых про­из­вод­ных функ­ции F(x), по­сколь­ку в точке ми­ни­му­ма x*они рав­ны ну­лю.

Срав­ни­вая (29) с (14), ви­дим, что в до­с­та­точной бли­зо­сти от ми­ни­му­ма (ко­г­да вклад треть­ей и бо­лее вы­со­ких сте­пе­ней рас­сто­я­ния x-x*мал) лю­бая функ­ция мо­жет при­бли­жен­но рас­сма­т­ри­вать­ся как ква­д­ра­тичная, причем ма­т­ри­це A из пред­ста­в­ле­ния (14) со­от­вет­ст­ву­ет ма­т­ри­ца Гес­се H. Не­об­хо­ди­мым ус­ло­ви­ем ми­ни­му­ма яв­ля­ет­ся по­ло­жи­тель­ная оп­ре­де­лен­ность ма­т­ри­цы Гес­се в точке x*. Два пер­вых сла­га­е­мых во вто­рой стро­ке (29) со­от­вет­ст­ву­ют ска­ляр­ной кон­стан­те c в (16). Тре­тий член в (29) со­дер­жит сла­га­е­мые, ли­ней­ные от­но­си­тель­но x, причем ве­к­то­ру ко­эф­фи­ци­ен­тов b из (16) со­от­вет­ст­ву­ет про­из­ве­де­ние Hx*.

По­сколь­ку ме­тод со­пря­жен­ных на­пра­в­ле­ний на­хо­дит ми­ни­мум ква­д­ра­тичной функ­ции за ко­нечное чис­ло ша­гов, мо­ж­но на­де­ять­ся, что в об­щем случае он по­з­во­лит бы­ст­ро до­с­тичь ко­нечно­го ре­зуль­та­та по­с­ле то­го, как те­ку­щая точка при­бли­зи­лась к ми­ни­му­му, и фор­му­ла (29) ста­ла удо­в­ле­тво­ри­тель­но ап­про­к­си­ми­ро­вать по­ве­де­ние F(x). Од­на­ко, ва­ри­ант ме­то­да, рас­смо­т­рен­ный в пре­ды­ду­щем раз­де­ле, вряд ли мо­жет быть по­лез­ным, по­сколь­ку в расчет­ные фор­му­лы вхо­дит ма­т­ри­ца A, а сле­до­ва­тель­но, при­дет­ся вычис­лять вто­рые про­из­вод­ные. К то­му же при­бли­же­ние (29) пред­по­ла­га­ет, что ма­т­ри­ца H рассчиты­ва­ет­ся в точке ми­ни­му­ма x*, ко­то­рая пер­во­началь­но не­из­ве­ст­на.

Ока­зы­ва­ет­ся, со­пря­жен­ные на­пра­в­ле­ния мо­ж­но по­стро­ить, не зная ма­т­ри­цы A. Со­от­вет­ст­ву­ю­щий ал­го­ритм был пред­ло­жен Флетчером и Рив­сом (R. Fletcher, C. M. Reeves; 1964).

Во-пер­вых, не­об­хо­ди­мо от­ка­зать­ся от вычис­ле­ния ко­эф­фи­ци­ен­тов a_k по яв­ным фор­му­лам (19), (24), (28) и т. д., а точку ми­ни­му­ма вдоль за­дан­но­го на­пра­в­ле­ния на­хо­дить с по­мо­щью не­по­сред­ст­вен­ной од­но­мер­ной оп­ти­ми­за­ции, при­ме­няя ме­то­ды, опи­сан­ные в раз­де­ле 1 (см. так­же п. 2.1.2). Во-вто­рых, вы­ра­же­ния для ко­эф­фи­ци­ен­тов b_k мо­ж­но пре­об­ра­зо­вать сле­ду­ю­щим об­ра­зом.

Пусть на k-м ша­ге ал­го­рит­ма про­во­дил­ся по­иск ми­ни­му­ма от точки x_k вдоль на­пра­в­ле­ния p_k=g_k+b_k-1p_k-1, причем в ре­зуль­та­те по­лучена точка ми­ни­му­ма x_k+1. На сле­ду­ю­щем ша­ге для по­ис­ка бе­рет­ся на­пра­в­ле­ние p_k+1=g_k+1+b_kp_k. На­пра­в­ле­ния p_k и p_k+1 со­пря­же­ны, т. е.

(g_k+1+b_kp_k)¢Ap_k=0. (30)

Точки x_k и x_k+1 ле­жат на пря­мой, па­рал­лель­ной p_k, так что в урав­не­нии (30) ве­к­тор p_k (с точно­стью до ко­эф­фи­ци­ен­та -a_k) мо­ж­но за­ме­нить раз­но­стью x_k+1-x_k:

(g_k+1+b_kp_k)¢A(x_k+1-x_k)=0.

Да­лее, так как, со­г­ла­с­но (15), g_k=Ax_k+b и g_k+1=Ax_k+1+b, то g_k+1-g_k=Ax_k+1-Ax_k. Под­ста­в­ляя это со­от­но­ше­ние в пре­ды­ду­щее урав­не­ние, име­ем:

(g_k+1+b_kp_k)¢(g_k+1-g_k)=0. (31)

Учиты­вая, что на­пра­в­ле­ние по­ис­ка и гра­ди­ент в най­ден­ной точке ми­ни­му­ма вза­им­но ор­то­го­наль­ны, т. е. p¢_k-1g_k=0 и p_k¢g_k+1=0, то из (31) окончатель­но по­лучаем:

. (32)

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

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