Редактирование: Методы безусловной минимизации

Материал из Documentation.

'''Методы безусловной минимизации''' ('''МБМ''') — ме­то­ды, пред­на­зна­чен­ные для на­хо­ж­де­ния [[минимум функции|ми­ни­му­ма]] [[функция|функ­ции]] мно­гих пе­ре­мен­ных $f(x)$ в слу­чае, ко­гда на зна­че­ния ар­гу­мен­та не на­ла­га­ют­ся до­пол­нительные ог­ра­ни­че­ния. МБМ со­став­ля­ют важ­ный класс [[Методы оптимизации|ме­то­дов оп­ти­ми­за­ции]]. За­да­ча о на­хож­де­нии мак­си­му­ма из­ме­не­ни­ем зна­ка функ­ции $f(x)$ сво­дит­ся к за­да­че о на­хож­де­нии ми­ни­му­ма. В слу­чае, ко­гда $f$ за­ви­сит от од­ной ска­ляр­ной пе­ре­мен­ной $x$, ми­ни­ми­за­цию функ­ции $f(x)$ обыч­но на­зы­ва­ют од­но­мер­ной. К груп­пе ме­то­дов од­но­мер­ной ми­ни­ми­за­ции от­но­сят­ся: [[ме­тод по­ло­вин­но­го де­ле­ния]], [[слу­чай­ный по­иск]], [[ме­тод Фи­бо­нач­чи]], [[ме­тод зо­ло­то­го се­че­ния]] и др.<ref>[https://bigenc.ru/mathematics/text/1852451 Безусловной минимизации методы]</ref> В МБМ в про­цес­се ми­ни­ми­за­ции стро­ит­ся не­ко­то­рая по­сле­до­ва­тель­ность то­чек $x_1,\, x_2,\, …,\, x_k$ мно­го­мер­но­го про­стран­ст­ва и в за­ви­си­мо­сти от зна­че­ний функ­ции $f$ в этих точ­ках на­хо­дит­ся но­вая точ­ка $x_{k+1}$. Пра­ви­ло по­строе­ния по­сле­до­ва­тель­но­сти оп­ре­де­ля­ет­ся вы­бран­ным ме­то­дом ми­ни­ми­за­ции.<ref>[https://bigenc.ru/mathematics/text/1852451 Безусловной минимизации методы]</ref> В МБМ важ­ную роль иг­ра­ет глад­кость функ­ции $f$. Уве­ли­че­ние глад­ко­сти ми­ни­ми­зи­руе­мой функ­ции $f$ по­зво­ля­ет стро­ить бо­лее эф­фек­тив­ные ме­то­ды.<ref>[https://bigenc.ru/mathematics/text/1852451 Безусловной минимизации методы]</ref> МБМ под­раз­де­ля­ют на три основных клас­са.<ref>[https://bigenc.ru/mathematics/text/1852451 Безусловной минимизации методы]</ref> Один из клас­сов со­став­ля­ют ме­то­ды, не ис­поль­зую­щие про­из­вод­ные функ­ции $f$. В этот класс вхо­дят [[слу­чай­ный по­иск]], [[ме­тод по­ко­ор­ди­нат­но­го спус­ка]] и др.<ref>[https://bigenc.ru/mathematics/text/1852451 Безусловной минимизации методы]</ref> Дру­гой класс об­ра­зу­ют [[гра­ди­ент­ные ме­то­ды]], в ко­то­рых пред­по­ла­га­ет­ся, что функ­ция $f$ один раз диф­фе­рен­ци­руе­ма. В ме­то­де гра­ди­ент­но­го спус­ка по­сле вы­чис­ле­ния зна­че­ния функ­ции $f$ и её гра­ди­ен­та $f_x$ в точ­ке $x_k$ но­вая точ­ка на­хо­дит­ся по фор­му­ле xk+1=xk−αkfx(xk), где $α_k$ — не­от­ри­ца­тель­ное чис­ло (шаг спус­ка). При не­ко­то­рых ус­ло­ви­ях по­сле­до­ва­тель­ность $x_1,\, x_2,\, …$ схо­дит­ся к точ­ке ло­каль­но­го ми­ни­му­ма функ­ции $f(x)$. Ес­ли при ка­ж­дом $k$ ве­ли­чи­на $α_k$ оп­ре­де­ля­ет­ся из ус­ло­вия од­но­мер­ной ми­ни­ми­за­ции функ­ции $f(x_{k+1})$ по $α_k$, то при­ходят к ме­то­ду на­ис­ко­рей­ше­го спус­ка. Су­ще­ст­ву­ют так­же ме­то­ды, на­зы­вае­мые $s$-ша­го­вы­ми, в ко­то­рых но­вая точ­ка $x_k$ оп­ре­де­ля­ет­ся по $s$ пре­ды­ду­щим точ­кам. Од­ним из про­стей­ших двух­ша­го­вых ме­то­дов яв­ля­ет­ся ме­тод со­пря­жён­но­го гра­ди­ен­та, в ко­то­ром xk+1=xk−αkfx(xk)+βk(xk−xk−1), где $α_k⩾0,\, β_k⩾0$ — па­ра­мет­ры, оп­ре­де­ляе­мые ре­ше­ни­ем за­да­чи дву­мер­ной ми­ни­ми­за­ции $f(x_{k+1})$ по $α_k$ и $β_k$.<ref>[https://bigenc.ru/mathematics/text/1852451 Безусловной минимизации методы]</ref> К треть­ему клас­су от­но­сит­ся [[ме­тод Нью­то­на]] и его мо­ди­фи­ка­ции. Пред­по­ла­га­ет­ся, что функ­ция $f$ два­ж­ды диф­фе­рен­ци­руе­ма. Точ­ка $x_{k+1}$ вы­чис­ля­ет­ся по фор­му­ле xk+1=xk−αkf−1xx(xk)fx(xk), где $f_{xx}^{-1}(x_k)$ — мат­ри­ца, об­рат­ная к мат­ри­це вто­рых про­из­вод­ных $f_{xx}(x_k)$. При $α_k≡1$ этот ме­тод на­зы­ва­ет­ся ме­то­дом Нью­то­на и час­то при­ме­ня­ет­ся при ре­ше­нии при­клад­ных за­дач. Не­дос­тат­ком это­го ме­то­да яв­ля­ет­ся тру­до­ём­кость вы­чис­ле­ний и ло­каль­ный ха­рак­тер схо­ди­мо­сти.<ref>[https://bigenc.ru/mathematics/text/1852451 Безусловной минимизации методы]</ref> Су­ще­ст­ву­ют мо­ди­фи­ка­ции ме­то­да Нью­то­на. В не­ко­то­рых из них для умень­ше­ния вре­ме­ни рас­чё­тов мат­ри­ца $f_{xx}(x_k)$ фик­си­ру­ет­ся на не­сколь­ких под­ряд иду­щих ша­гах. В других ва­ри­ан­тах шаг $α_k$ вы­би­ра­ет­ся из ус­ло­вия ми­ни­му­ма зна­че­ния функ­ции $f(x_{k+1})$ ли­бо нор­мы её гра­ди­ен­та.<ref>[https://bigenc.ru/mathematics/text/1852451 Безусловной минимизации методы]</ref> Пе­ре­чис­лен­ные МБМ пред­на­зна­че­ны для оты­ска­ния ло­каль­ных ми­ни­му­мов функ­ции $f(x)$, и толь­ко для вы­пук­лых функ­ций най­ден­ные ре­ше­ния да­ют гло­баль­ный ми­ни­мум. За­да­ча о по­ис­ке ми­ни­му­ма ещё бо­лее ус­лож­ня­ет­ся в слу­чае оты­ска­ния ус­лов­но­го ми­ни­му­ма, ко­гда на зна­че­ния ар­гу­мен­та $x$ на­ла­га­ют­ся до­пол­нительные ог­ра­ни­че­ния.<ref>[https://bigenc.ru/mathematics/text/1852451 Безусловной минимизации методы]</ref> == Примечания == <references /> [[Категория:Математика]]

---

Описание изменений:

Отменить | Справка по редактированию (в новом окне)