БЕЗУСЛО́ВНОЙ МИНИМИЗА́ЦИИ МЕ́ТОДЫ

БЕЗУСЛО́ВНОЙ МИНИМИЗА́ЦИИ МЕ́ТО­ДЫ, ме­то­ды, пред­на­зна­чен­ные для на­хо­ж­де­ния ми­ни­му­ма функ­ции мно­гих пе­ре­мен­ных $f(x)$ в слу­чае, ко­гда на зна­че­ния ар­гу­мен­та не на­ла­га­ют­ся до­пол­нит. ог­ра­ни­че­ния. Б. м. м. со­став­ля­ют важ­ный класс ме­то­дов оп­ти­ми­за­ции. За­да­ча о на­хож­де­нии мак­си­му­ма из­ме­не­ни­ем зна­ка функ­ции $f(x)$ сво­дит­ся к за­да­че о на­хож­де­нии ми­ни­му­ма. В слу­чае, ко­гда $f$ за­ви­сит от од­ной ска­ляр­ной пе­ре­мен­ной $x$, ми­ни­ми­за­цию функ­ции $f(x)$ обыч­но на­зы­ва­ют од­но­мер­ной. К груп­пе ме­то­дов од­но­мер­ной ми­ни­ми­за­ции от­но­сят­ся: ме­тод по­ло­вин­но­го де­ле­ния, слу­чай­ный по­иск, ме­тод Фи­бо­нач­чи, ме­тод зо­ло­то­го се­че­ния и др.

В Б. м. м. в про­цес­се ми­ни­ми­за­ции стро­ит­ся не­ко­то­рая по­сле­до­ва­тель­ность то­чек $x_1,\, x_2,\, …,\, x_k$ мно­го­мер­но­го про­стран­ст­ва и в за­ви­си­мо­сти от зна­че­ний функ­ции $f$ в этих точ­ках на­хо­дит­ся но­вая точ­ка $x_{k+1}$. Пра­ви­ло по­строе­ния по­сле­до­ва­тель­но­сти оп­ре­де­ля­ет­ся вы­бран­ным ме­то­дом ми­ни­ми­за­ции.

В Б. м. м. важ­ную роль иг­ра­ет глад­кость функ­ции $f$. Уве­ли­че­ние глад­ко­сти ми­ни­ми­зи­руе­мой функ­ции $f$ по­зво­ля­ет стро­ить бо­лее эф­фек­тив­ные ме­то­ды. Б. м. м. под­раз­де­ля­ют на три осн. клас­са.

Один из клас­сов со­став­ля­ют ме­то­ды, не ис­поль­зую­щие про­из­вод­ные функ­ции $f$. В этот класс вхо­дят слу­чай­ный по­иск, ме­тод по­ко­ор­ди­нат­но­го спус­ка и др.

Дру­гой класс об­ра­зу­ют гра­ди­ент­ные ме­то­ды, в ко­то­рых пред­по­ла­га­ет­ся, что функ­ция $f$ один раз диф­фе­рен­ци­руе­ма. В ме­то­де гра­ди­ент­но­го спус­ка по­сле вы­чис­ле­ния зна­че­ния функ­ции $f$ и её гра­ди­ен­та $f_x$ в точ­ке $x_k$ но­вая точ­ка на­хо­дит­ся по фор­му­ле $$x_{k+1}=x_k-α_kf_x(x_k),$$ где $α_k$ – не­от­ри­ца­тель­ное чис­ло (шаг спус­ка). При не­ко­то­рых ус­ло­ви­ях по­сле­до­ва­тель­ность $x_1,\, x_2,\, …$ схо­дит­ся к точ­ке ло­каль­но­го ми­ни­му­ма функ­ции $f(x)$. Ес­ли при ка­ж­дом $k$ ве­ли­чи­на $α_k$ оп­ре­де­ля­ет­ся из ус­ло­вия од­но­мер­ной ми­ни­ми­за­ции функ­ции $f(x_{k+1})$ по $α_k$, то при­ходят к ме­то­ду на­ис­ко­рей­ше­го спус­ка. Су­ще­ст­ву­ют так­же ме­то­ды, на­зы­вае­мые $s$-ша­го­вы­ми, в ко­то­рых но­вая точ­ка $x_k$ оп­ре­де­ля­ет­ся по $s$ пре­ды­ду­щим точ­кам. Од­ним из про­стей­ших двух­ша­го­вых ме­то­дов яв­ля­ет­ся ме­тод со­пря­жён­но­го гра­ди­ен­та, в ко­то­ром $$x_{k+1}=x_k-α_kf_x(x_k)+β_k(x_k-x_{k-1}),$$ где $α_k⩾0,\, β_k⩾0$ – па­ра­мет­ры, оп­ре­де­ляе­мые ре­ше­ни­ем за­да­чи дву­мер­ной ми­ни­ми­за­ции $f(x_{k+1})$ по $α_k$ и $β_k$.

К треть­ему клас­су от­но­сит­ся ме­тод Нью­то­на и его мо­ди­фи­ка­ции. Пред­по­ла­га­ет­ся, что функ­ция $f$ два­ж­ды диф­фе­рен­ци­руе­ма. Точ­ка $x_{k+1}$ вы­чис­ля­ет­ся по фор­му­ле $$x_{k+1}=x_k - α_k f_{xx}^{-1} (x_k) f_x (x_k),$$ где $f_{xx}^{-1}(x_k)$ – мат­ри­ца, об­рат­ная к мат­ри­це вто­рых про­из­вод­ных $f_{xx}(x_k)$. При $α_k≡1$ этот ме­тод на­зы­ва­ет­ся ме­то­дом Нью­то­на и час­то при­ме­ня­ет­ся при ре­ше­нии при­клад­ных за­дач. Не­дос­тат­ком это­го ме­то­да яв­ля­ет­ся тру­до­ём­кость вы­чис­ле­ний и ло­каль­ный ха­рак­тер схо­ди­мо­сти.

Су­ще­ст­ву­ют мо­ди­фи­ка­ции ме­то­да Нью­то­на. В не­ко­то­рых из них для умень­ше­ния вре­ме­ни рас­чё­тов мат­ри­ца $f_{xx}(x_k)$ фик­си­ру­ет­ся на не­сколь­ких под­ряд иду­щих ша­гах. В др. ва­ри­ан­тах шаг $α_k$ вы­би­ра­ет­ся из ус­ло­вия ми­ни­му­ма зна­че­ния функ­ции $f(x_{k+1})$ ли­бо нор­мы её гра­ди­ен­та.

Пе­ре­чис­лен­ные Б. м. м. пред­на­зна­че­ны для оты­ска­ния ло­каль­ных ми­ни­му­мов функ­ции $f(x)$, и толь­ко для вы­пук­лых функ­ций най­ден­ные ре­ше­ния да­ют гло­баль­ный ми­ни­мум. За­да­ча о по­ис­ке ми­ни­му­ма ещё бо­лее ус­лож­ня­ет­ся в слу­чае оты­ска­ния ус­лов­но­го ми­ни­му­ма, ко­гда на зна­че­ния ар­гу­мен­та $x$ на­ла­га­ют­ся до­пол­нит. ог­ра­ни­че­ния.