Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Квазі Ньютонівські методи це методи що використовуються для пошуку нулів або локальних максимумів та мінімумів функцій я

Квазі-ньютонів метод

Квазі-ньютонів метод

Квазі-Ньютонівські методи — це методи, що використовуються для пошуку нулів або локальних максимумів та мінімумів функцій, як альтернатива методу Ньютона. Їх можливо використовувати, якщо якобіан або гессіан недоступні або обчислення на кожній ітерації займає забагато ресурсів. «Повний» метод Ньютона вимагає наявності якобіана для пошуку нулів або гессіана для знаходження екстремумів. Деякі [en], що зводяться до методу Ньютона, такі як SLSQP, можуть вважатися квазі-Ньютонівськими.

Пошук нулів: знаходження коренів

Метод Ньютона для визначення нулів функції image кількох змінних визначається як image, де image — лівий обернений якобіан матриці image для image у точці image.

Загалом, будь-який метод, який замість точного якобіану image використовує наближене значення, є квазі-Ньютонівським методом. Простим прикладом є метод хорд, в якому на всіх ітераціях image замінюється на image. Наведені нижче методи оптимізації вказують на важливий підклас квазі-Ньютонівських методів, які засновані на методі хорд.

Використання методів, які розроблено для пошуку екстремумів з метою визначення нулів, не завжди є конструктивною стратегією, оскільки більшість таких методів вимагають, щоб матриця була симетричною. У контексті пошуку екстремумів це має місце, проте це малоймовірно у випадку визначення нулів. Методи Бройдена — «добрий» і «поганий» — це два методи, які часто використовуються для пошуку екстремумів і також можуть бути застосовані для визначення нулів. Інші методи, які можуть бути використані, — це , , квазі-Ньютонівський метод найменших квадратів і квазі-Ньютонівський метод обернених найменших квадратів.

Нещодавно квазі-Ньютонівські методи були застосовані для знаходження розв'язку множини зв'язаних систем рівнянь (наприклад, проблеми взаємодії рідини та структури або проблеми взаємодії у фізиці). Вони дозволяють знаходити розв'язок шляхом окремого розв'язання кожної складової системи (що є простішим, ніж пошук розв'язку для глобальної системи) у циклічному ітеративному порядку, поки не буде знайдено розв'язок глобальної системи.

Пошук екстремуму: оптимізація

Пошук мінімуму або максимуму скалярної функції представляє собою визначення нулів градієнта цієї функції. Таким чином, квазі-Ньютонівські методи можна легко використовувати для пошуку екстремумів функції. Іншими словами, якщо image — це градієнт image, то визначення нулів векторної функції image еквівалентне пошуку екстремумів скалярної функції image; якобіан image тепер стає гессіаном image. Основна відмінність полягає в тому, що матриця Гессе є симетричною, на відміну від якобіана при визначенні нулів. Більшість використовуваних в оптимізації квазі-Ньютонівських методів користуються цією властивістю.

В оптимізації квазі-Ньютонівські методи (особливий випадок методів змінної метрики) — це алгоритми пошуку локальних максимумів і мінімумів функцій. Квазі-Ньютонівські методи базуються на методі Ньютона для пошуку стаціонарної точки функції, де градієнт дорівнює 0. Метод Ньютона передбачає, що функцію можна локально апроксимувати квадратичною функцією у деякому околі оптимуму, та використовує перші i другі похідні для знаходження точок стаціонарності. У багатовимірних просторах метод Ньютона використовує градієнт та матрицю Гессе других похідних функції, яку потрібно мінімізувати.

У квазі-Ньютонівських методах немає потреби в обчисленні матриці гессіана. Оновлення гессіана здійснюється за допомогою аналізу послідовних векторів градієнта. Квазі-Ньютонівські методи представляють собою узагальнення методу хорд для пошуку кореня першої похідної в багатовимірних задачах. У випадку багатовимірних задач рівняння хорд є [en], і квазі-Ньютонівські методи відрізняються тим, як вони обмежують рішення, зазвичай додаванням простого низькорангового оновлення до поточної оцінки гессіана.

Перший квазі-Ньютонівський алгоритм був запропонований [en], фізиком, який працював в Аргоннській національній лабораторії. Він розробив перший квазі-Ньютонівський алгоритм у 1959 році: [en], яка пізніше стала популярною завдяки Флетчеру і Пауеллу в 1963 році, але сьогодні рідко використовується. Серед найпоширеніших квазі-Ньютонівських алгоритмів в наш час варто відзначити [en] («симетричний ранг-один»), метод [en], широко поширений метод BFGS (запропонований незалежно Бройденом, Флетчером, Голдфарбом і Шанно в 1970 році) та його розширення з обмеженим використанням пам'яті [en]. Клас Бройдена представляє собою лінійною комбінацією методів DFP і BFGS.

Формула SR1 не гарантує, що оновлена матриця буде залишатися [en] і може бути використана для невизначених задач. Метод Бройдена не вимагає, щоб оновлена матриця була симетричною і використовується для пошуку кореня загальної системи рівнянь (а не градієнта), оновлюючи якобіан (замість Гессе).

Однією з головних переваг квазі-Ньютонівські методів над методом Ньютона є те, що немає необхідності знаходити обернену матрицю Гессе (або, у випадку квазі-Ньютонівських методів, її наближення) image . Метод Ньютона та його похідні, такі як методи внутрішньої точки, вимагають оберненої матриці Гессе, що, зазвичай реалізується шляхом розв'язання системи лінійних рівнянь, і є витратним процесом. На відміну від цього, квазі-Ньютонівські методи зазвичай генерують безпосередню оцінку матриці image.

Як і в методі Ньютона, використовується апроксимація другого порядку для пошуку мінімуму функції image. Ряд Тейлора image в околі ітеративної точки виглядає наступним чином:

image

де (image) — градієнт, а image наближення матриці Гессе. Градієнт цієї апроксимації (відносно image) виглядає наступним чином:

image

і встановлення цього градієнту рівним нулю (що є метою оптимізації) дає крок Ньютона:

image

Наближення матриці Гессе image обирається так, щоб задовольнити умовний вираз:

image

який називається рівнянням хорд (ряд Тейлора градієнта). У багатовимірному випадку матриця image [en]. В одновимірному випадку розв'язання для image та застосування кроку Ньютона з оновленою величиною еквівалентне методу хорд. Квазі-Ньютонові методи відрізняються своїм вибором розв'язку рівняння хорди (у одновимірному випадку всі варіанти еквівалентні). Більшість методів (але є винятки, такі як метод Бройдена) шукають симетричний розв'язок (image); крім того, варіанти, що перелічено нижче, можуть бути обгрунтовані пошуком оновлення image яке якомога ближче до image за якоюсь нормою; тобто, image, де image — це деяка [en], яка визначає норму. Приблизне початкове значення image часто є достатнім для швидкої збіжності, хоча немає загальної стратегії вибору image. Зверніть увагу, що image повинна бути додатньо-визначеною. Невідомий image оновлюється застосуванням кроку Ньютона, розрахованого за допомогою поточної приблизної матриці Гессе image:

  • image, де image, обрано так, щоб задовольняти умовам Вольфе;
  • image;
  • Градієнт, обчислений у новій точці image, та
image

використовується для оновлення наближення матриці Гессе image, або безпосередньо її оберненої матриці image за допомогою [en].

  • Ключовою властивістю оновлень BFGS і DFP є те, що якщо image є додатньо-визначеною, і image обрано так, щоб задовольняти умовам Вольфе image також є додатньо-визначеною.

Найпопулярніші формули оновлення:

Метод image image
BFGS image image
Бройден image image
Сімейство Бройдена image
[en] image image
[en] image image

Інші методи включають метод Пірсона, метод Маккорміка, симетричний метод Бройдена Пауелла (PSB) та метод Грінштадта.

Зв'язок з оберненою матрицею

Коли функція image є опуклою квадратичною функцією з додатно-визначеною матрицею Гессе image, можна очікувати, що матриці image створені квазі-Ньютоновським методом, будуть збігатися до оберненої матриці Гессе image. Це дійсно так для класу квазі-Ньютоновських методів, які ґрунтуються на оновленнях з мінімальними змінами.

Відомі реалізації

Реалізації квазі-Ньютоновських методів доступні в багатьох мовах програмування.

Серед реалізації з відкритим кодом найбільше відомі такі:

  • GNU Octave використовую модифікацію BFGS у своїй функції fsolve з додаванням [en].
  • GNU Scientific Library реалізує алгоритм Бройдена-Флетчера-Голдфарба-Шанно (BFGS).
  • [en] реалізує (L)BFGS мовами програмування C++ та C#
  • у R загальнозначущий оптимізатор, реалізований в функції optim, використовує метод BFGS з параметром method="BFGS".
  • Scipy.optimize містить функцію fmin_bfgs. У бібліотеці SciPy для мови програмування Python, функція scipy.optimize.minimize включає, серед інших методів, реалізацію BFGS.

Серед реалізацій з власницьким кодом найбільш відомі такі:

  • Mathematica включає рішення з використанням квазі-Ньютонівських методів.
  • [en] містить кілька процедур для мінімізації або максимізації функції, які використовують квазі-Ньютонівські алгоритми.
  • У MATLAB [en], функція fminunc використовує (поміж інших методів) квазі-Ньютонівський метод BFGS. Багато з обмежених методів також використовують BFGS та його варіант [en].

Див. також

Список літератури

  1. Broyden, C. G. (1972). Quasi-Newton Methods. У Murray, W. (ред.). Numerical Methods for Unconstrained Optimization. London: Academic Press. с. 87—106. ISBN .
  2. Haelterman, Rob (2009). Analytical study of the Least Squares Quasi-Newton method for interaction problems. PhD Thesis, Ghent University. Процитовано 14 серпня 2014.
  3. Rob Haelterman; Dirk Van Eester; Daan Verleyen (2015). Accelerating the solution of a physics model inside a tokamak using the (Inverse) Column Updating Method. Journal of Computational and Applied Mathematics. 279: 133—144. doi:10.1016/j.cam.2014.11.005.
  4. Introduction to Taylor's theorem for multivariable functions - Math Insight. mathinsight.org. Процитовано 11 листопада 2021.
  5. Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization. New York: Springer. с. 142. ISBN .
  6. Robert Mansel Gower; Peter Richtarik (2015). Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms. arXiv:1602.01768 [math.NA].
  7. optim function - RDocumentation. www.rdocumentation.org (англ.). Процитовано 21 лютого 2022.
  8. Scipy.optimize.minimize — SciPy v1.7.1 Manual.
  9. Unconstrained Optimization: Methods for Local Minimization—Wolfram Language Documentation. reference.wolfram.com. Процитовано 21 лютого 2022.
  10. The Numerical Algorithms Group. Keyword Index: Quasi-Newton. NAG Library Manual, Mark 23. Процитовано 9 лютого 2012.
  11. The Numerical Algorithms Group. E04 – Minimizing or Maximizing a Function (PDF). NAG Library Manual, Mark 23. Процитовано 9 лютого 2012.
  12. Find minimum of unconstrained multivariable function - MATLAB fminunc.
  13. Constrained Nonlinear Optimization Algorithms - MATLAB & Simulink. www.mathworks.com. Процитовано 21 лютого 2022.

Додаткові матеріали

  • Bonnans, J. F.; Gilbert, J. Ch.; Lemaréchal, C.; Sagastizábal, C. A. (2006). Numerical Optimization : Theoretical and Numerical Aspects (вид. Second). Springer. ISBN .
  • Fletcher, Roger (1987), Practical methods of optimization (вид. 2nd), New York: , ISBN .
  • Nocedal, Jorge; Wright, Stephen J. (1999). Quasi-Newton Methods. Numerical Optimization. New York: Springer. с. 192—221. ISBN .
  • Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). Section 10.9. Quasi-Newton or Variable Metric Methods in Multidimensions. Numerical Recipes: The Art of Scientific Computing (вид. 3rd). Cambridge University Press. ISBN .
  • Scales, L. E. (1985). Introduction to Non-Linear Optimization. New York: MacMillan. с. 84—106. ISBN .

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Kvazi Nyutonivski metodi ce metodi sho vikoristovuyutsya dlya poshuku nuliv abo lokalnih maksimumiv ta minimumiv funkcij yak alternativa metodu Nyutona Yih mozhlivo vikoristovuvati yaksho yakobian abo gessian nedostupni abo obchislennya na kozhnij iteraciyi zajmaye zabagato resursiv Povnij metod Nyutona vimagaye nayavnosti yakobiana dlya poshuku nuliv abo gessiana dlya znahodzhennya ekstremumiv Deyaki en sho zvodyatsya do metodu Nyutona taki yak SLSQP mozhut vvazhatisya kvazi Nyutonivskimi Poshuk nuliv znahodzhennya korenivMetod Nyutona dlya viznachennya nuliv funkciyi g displaystyle g kilkoh zminnih viznachayetsya yak x n 1 x n J g x n 1 g x n displaystyle x n 1 x n J g x n 1 g x n de J g x n 1 displaystyle J g x n 1 livij obernenij yakobian matrici J g x n displaystyle J g x n dlya g displaystyle g u tochci x n displaystyle x n Zagalom bud yakij metod yakij zamist tochnogo yakobianu J g x n displaystyle J g x n vikoristovuye nablizhene znachennya ye kvazi Nyutonivskim metodom Prostim prikladom ye metod hord v yakomu na vsih iteraciyah J g x n displaystyle J g x n zaminyuyetsya na J g x 0 displaystyle J g x 0 Navedeni nizhche metodi optimizaciyi vkazuyut na vazhlivij pidklas kvazi Nyutonivskih metodiv yaki zasnovani na metodi hord Vikoristannya metodiv yaki rozrobleno dlya poshuku ekstremumiv z metoyu viznachennya nuliv ne zavzhdi ye konstruktivnoyu strategiyeyu oskilki bilshist takih metodiv vimagayut shob matricya bula simetrichnoyu U konteksti poshuku ekstremumiv ce maye misce prote ce malojmovirno u vipadku viznachennya nuliv Metodi Brojdena dobrij i poganij ce dva metodi yaki chasto vikoristovuyutsya dlya poshuku ekstremumiv i takozh mozhut buti zastosovani dlya viznachennya nuliv Inshi metodi yaki mozhut buti vikoristani ce kvazi Nyutonivskij metod najmenshih kvadrativ i kvazi Nyutonivskij metod obernenih najmenshih kvadrativ Neshodavno kvazi Nyutonivski metodi buli zastosovani dlya znahodzhennya rozv yazku mnozhini zv yazanih sistem rivnyan napriklad problemi vzayemodiyi ridini ta strukturi abo problemi vzayemodiyi u fizici Voni dozvolyayut znahoditi rozv yazok shlyahom okremogo rozv yazannya kozhnoyi skladovoyi sistemi sho ye prostishim nizh poshuk rozv yazku dlya globalnoyi sistemi u ciklichnomu iterativnomu poryadku poki ne bude znajdeno rozv yazok globalnoyi sistemi Poshuk ekstremumu optimizaciyaPoshuk minimumu abo maksimumu skalyarnoyi funkciyi predstavlyaye soboyu viznachennya nuliv gradiyenta ciyeyi funkciyi Takim chinom kvazi Nyutonivski metodi mozhna legko vikoristovuvati dlya poshuku ekstremumiv funkciyi Inshimi slovami yaksho g displaystyle g ce gradiyent f displaystyle f to viznachennya nuliv vektornoyi funkciyi g displaystyle g ekvivalentne poshuku ekstremumiv skalyarnoyi funkciyi f displaystyle f yakobian g displaystyle g teper staye gessianom f displaystyle f Osnovna vidminnist polyagaye v tomu sho matricya Gesse ye simetrichnoyu na vidminu vid yakobiana pri viznachenni nuliv Bilshist vikoristovuvanih v optimizaciyi kvazi Nyutonivskih metodiv koristuyutsya ciyeyu vlastivistyu V optimizaciyi kvazi Nyutonivski metodi osoblivij vipadok metodiv zminnoyi metriki ce algoritmi poshuku lokalnih maksimumiv i minimumiv funkcij Kvazi Nyutonivski metodi bazuyutsya na metodi Nyutona dlya poshuku stacionarnoyi tochki funkciyi de gradiyent dorivnyuye 0 Metod Nyutona peredbachaye sho funkciyu mozhna lokalno aproksimuvati kvadratichnoyu funkciyeyu u deyakomu okoli optimumu ta vikoristovuye pershi i drugi pohidni dlya znahodzhennya tochok stacionarnosti U bagatovimirnih prostorah metod Nyutona vikoristovuye gradiyent ta matricyu Gesse drugih pohidnih funkciyi yaku potribno minimizuvati U kvazi Nyutonivskih metodah nemaye potrebi v obchislenni matrici gessiana Onovlennya gessiana zdijsnyuyetsya za dopomogoyu analizu poslidovnih vektoriv gradiyenta Kvazi Nyutonivski metodi predstavlyayut soboyu uzagalnennya metodu hord dlya poshuku korenya pershoyi pohidnoyi v bagatovimirnih zadachah U vipadku bagatovimirnih zadach rivnyannya hord ye en i kvazi Nyutonivski metodi vidriznyayutsya tim yak voni obmezhuyut rishennya zazvichaj dodavannyam prostogo nizkorangovogo onovlennya do potochnoyi ocinki gessiana Pershij kvazi Nyutonivskij algoritm buv zaproponovanij en fizikom yakij pracyuvav v Argonnskij nacionalnij laboratoriyi Vin rozrobiv pershij kvazi Nyutonivskij algoritm u 1959 roci en yaka piznishe stala populyarnoyu zavdyaki Fletcheru i Pauellu v 1963 roci ale sogodni ridko vikoristovuyetsya Sered najposhirenishih kvazi Nyutonivskih algoritmiv v nash chas varto vidznachiti en simetrichnij rang odin metod en shiroko poshirenij metod BFGS zaproponovanij nezalezhno Brojdenom Fletcherom Goldfarbom i Shanno v 1970 roci ta jogo rozshirennya z obmezhenim vikoristannyam pam yati en Klas Brojdena predstavlyaye soboyu linijnoyu kombinaciyeyu metodiv DFP i BFGS Formula SR1 ne garantuye sho onovlena matricya bude zalishatisya en i mozhe buti vikoristana dlya neviznachenih zadach Metod Brojdena ne vimagaye shob onovlena matricya bula simetrichnoyu i vikoristovuyetsya dlya poshuku korenya zagalnoyi sistemi rivnyan a ne gradiyenta onovlyuyuchi yakobian zamist Gesse Odniyeyu z golovnih perevag kvazi Nyutonivski metodiv nad metodom Nyutona ye te sho nemaye neobhidnosti znahoditi obernenu matricyu Gesse abo u vipadku kvazi Nyutonivskih metodiv yiyi nablizhennya B displaystyle B Metod Nyutona ta jogo pohidni taki yak metodi vnutrishnoyi tochki vimagayut obernenoyi matrici Gesse sho zazvichaj realizuyetsya shlyahom rozv yazannya sistemi linijnih rivnyan i ye vitratnim procesom Na vidminu vid cogo kvazi Nyutonivski metodi zazvichaj generuyut bezposerednyu ocinku matrici B 1 displaystyle B 1 Yak i v metodi Nyutona vikoristovuyetsya aproksimaciya drugogo poryadku dlya poshuku minimumu funkciyi f x displaystyle f x Ryad Tejlora f x displaystyle f x v okoli iterativnoyi tochki viglyadaye nastupnim chinom f x k D x f x k f x k T D x 1 2 D x T B D x displaystyle f x k Delta x approx f x k nabla f x k mathrm T Delta x frac 1 2 Delta x mathrm T B Delta x de f displaystyle nabla f gradiyent a B displaystyle B nablizhennya matrici Gesse Gradiyent ciyeyi aproksimaciyi vidnosno D x displaystyle Delta x viglyadaye nastupnim chinom f x k D x f x k B D x displaystyle nabla f x k Delta x approx nabla f x k B Delta x i vstanovlennya cogo gradiyentu rivnim nulyu sho ye metoyu optimizaciyi daye krok Nyutona D x B 1 f x k displaystyle Delta x B 1 nabla f x k Nablizhennya matrici Gesse B displaystyle B obirayetsya tak shob zadovolniti umovnij viraz f x k D x f x k B D x displaystyle nabla f x k Delta x nabla f x k B Delta x yakij nazivayetsya rivnyannyam hord ryad Tejlora gradiyenta U bagatovimirnomu vipadku matricya B displaystyle B en V odnovimirnomu vipadku rozv yazannya dlya B displaystyle B ta zastosuvannya kroku Nyutona z onovlenoyu velichinoyu ekvivalentne metodu hord Kvazi Nyutonovi metodi vidriznyayutsya svoyim viborom rozv yazku rivnyannya hordi u odnovimirnomu vipadku vsi varianti ekvivalentni Bilshist metodiv ale ye vinyatki taki yak metod Brojdena shukayut simetrichnij rozv yazok B T B displaystyle B T B krim togo varianti sho perelicheno nizhche mozhut buti obgruntovani poshukom onovlennya B k 1 displaystyle B k 1 yake yakomoga blizhche do B k displaystyle B k za yakoyus normoyu tobto B k 1 argmin B B B k V displaystyle B k 1 operatorname argmin B B B k V de V displaystyle V ce deyaka en yaka viznachaye normu Priblizne pochatkove znachennya B 0 b I displaystyle B 0 beta I chasto ye dostatnim dlya shvidkoyi zbizhnosti hocha nemaye zagalnoyi strategiyi viboru b displaystyle beta Zvernit uvagu sho B 0 displaystyle B 0 povinna buti dodatno viznachenoyu Nevidomij x k displaystyle x k onovlyuyetsya zastosuvannyam kroku Nyutona rozrahovanogo za dopomogoyu potochnoyi pribliznoyi matrici Gesse B k displaystyle B k D x k a k B k 1 f x k displaystyle Delta x k alpha k B k 1 nabla f x k de a displaystyle alpha obrano tak shob zadovolnyati umovam Volfe x k 1 x k D x k displaystyle x k 1 x k Delta x k Gradiyent obchislenij u novij tochci f x k 1 displaystyle nabla f x k 1 ta y k f x k 1 f x k displaystyle y k nabla f x k 1 nabla f x k vikoristovuyetsya dlya onovlennya nablizhennya matrici Gesse B k 1 displaystyle B k 1 abo bezposeredno yiyi obernenoyi matrici H k 1 B k 1 1 displaystyle H k 1 B k 1 1 za dopomogoyu en Klyuchovoyu vlastivistyu onovlen BFGS i DFP ye te sho yaksho B k displaystyle B k ye dodatno viznachenoyu i a k displaystyle alpha k obrano tak shob zadovolnyati umovam Volfe B k 1 displaystyle B k 1 takozh ye dodatno viznachenoyu Najpopulyarnishi formuli onovlennya Metod B k 1 displaystyle displaystyle B k 1 H k 1 B k 1 1 displaystyle H k 1 B k 1 1 BFGS B k y k y k T y k T D x k B k D x k B k D x k T D x k T B k D x k displaystyle B k frac y k y k mathrm T y k mathrm T Delta x k frac B k Delta x k B k Delta x k mathrm T Delta x k mathrm T B k Delta x k I D x k y k T y k T D x k H k I y k D x k T y k T D x k D x k D x k T y k T D x k displaystyle left I frac Delta x k y k mathrm T y k mathrm T Delta x k right H k left I frac y k Delta x k mathrm T y k mathrm T Delta x k right frac Delta x k Delta x k mathrm T y k mathrm T Delta x k Brojden B k y k B k D x k D x k T D x k D x k T displaystyle B k frac y k B k Delta x k Delta x k mathrm T Delta x k Delta x k mathrm T H k D x k H k y k D x k T H k D x k T H k y k displaystyle H k frac Delta x k H k y k Delta x k mathrm T H k Delta x k mathrm T H k y k Simejstvo Brojdena 1 f k B k 1 BFGS f k B k 1 DFP f 0 1 displaystyle 1 varphi k B k 1 text BFGS varphi k B k 1 text DFP quad varphi in 0 1 en I y k D x k T y k T D x k B k I D x k y k T y k T D x k y k y k T y k T D x k displaystyle left I frac y k Delta x k mathrm T y k mathrm T Delta x k right B k left I frac Delta x k y k mathrm T y k mathrm T Delta x k right frac y k y k mathrm T y k mathrm T Delta x k H k D x k D x k T D x k T y k H k y k y k T H k y k T H k y k displaystyle H k frac Delta x k Delta x k mathrm T Delta x k mathrm T y k frac H k y k y k mathrm T H k y k mathrm T H k y k en B k y k B k D x k y k B k D x k T y k B k D x k T D x k displaystyle B k frac y k B k Delta x k y k B k Delta x k mathrm T y k B k Delta x k mathrm T Delta x k H k D x k H k y k D x k H k y k T D x k H k y k T y k displaystyle H k frac Delta x k H k y k Delta x k H k y k mathrm T Delta x k H k y k mathrm T y k Inshi metodi vklyuchayut metod Pirsona metod Makkormika simetrichnij metod Brojdena Pauella PSB ta metod Grinshtadta Zv yazok z obernenoyu matriceyuKoli funkciya f displaystyle f ye opukloyu kvadratichnoyu funkciyeyu z dodatno viznachenoyu matriceyu Gesse B displaystyle B mozhna ochikuvati sho matrici H k displaystyle H k stvoreni kvazi Nyutonovskim metodom budut zbigatisya do obernenoyi matrici Gesse H B 1 displaystyle H B 1 Ce dijsno tak dlya klasu kvazi Nyutonovskih metodiv yaki gruntuyutsya na onovlennyah z minimalnimi zminami Vidomi realizaciyiRealizaciyi kvazi Nyutonovskih metodiv dostupni v bagatoh movah programuvannya Sered realizaciyi z vidkritim kodom najbilshe vidomi taki GNU Octave vikoristovuyu modifikaciyu BFGS u svoyij funkciyi fsolve z dodavannyam en GNU Scientific Library realizuye algoritm Brojdena Fletchera Goldfarba Shanno BFGS en realizuye L BFGS movami programuvannya C ta C u R zagalnoznachushij optimizator realizovanij v funkciyi optim vikoristovuye metod BFGS z parametrom method BFGS Scipy optimize mistit funkciyu fmin bfgs U biblioteci SciPy dlya movi programuvannya Python funkciya scipy optimize minimize vklyuchaye sered inshih metodiv realizaciyu BFGS Sered realizacij z vlasnickim kodom najbilsh vidomi taki Mathematica vklyuchaye rishennya z vikoristannyam kvazi Nyutonivskih metodiv en mistit kilka procedur dlya minimizaciyi abo maksimizaciyi funkciyi yaki vikoristovuyut kvazi Nyutonivski algoritmi U MATLAB en funkciya fminunc vikoristovuye pomizh inshih metodiv kvazi Nyutonivskij metod BFGS Bagato z obmezhenih metodiv takozh vikoristovuyut BFGS ta jogo variant en Div takozhMetodi BFGS en en Metod Brojdena en Metod Nyutona Metod Nyutona v optimizaciyi en Spisok literaturiBroyden C G 1972 Quasi Newton Methods U Murray W red Numerical Methods for Unconstrained Optimization London Academic Press s 87 106 ISBN 0 12 512250 0 Haelterman Rob 2009 Analytical study of the Least Squares Quasi Newton method for interaction problems PhD Thesis Ghent University Procitovano 14 serpnya 2014 Rob Haelterman Dirk Van Eester Daan Verleyen 2015 Accelerating the solution of a physics model inside a tokamak using the Inverse Column Updating Method Journal of Computational and Applied Mathematics 279 133 144 doi 10 1016 j cam 2014 11 005 Introduction to Taylor s theorem for multivariable functions Math Insight mathinsight org Procitovano 11 listopada 2021 Nocedal Jorge Wright Stephen J 2006 Numerical Optimization New York Springer s 142 ISBN 0 387 98793 2 Robert Mansel Gower Peter Richtarik 2015 Randomized Quasi Newton Updates are Linearly Convergent Matrix Inversion Algorithms arXiv 1602 01768 math NA optim function RDocumentation www rdocumentation org angl Procitovano 21 lyutogo 2022 Scipy optimize minimize SciPy v1 7 1 Manual Unconstrained Optimization Methods for Local Minimization Wolfram Language Documentation reference wolfram com Procitovano 21 lyutogo 2022 The Numerical Algorithms Group Keyword Index Quasi Newton NAG Library Manual Mark 23 Procitovano 9 lyutogo 2012 The Numerical Algorithms Group E04 Minimizing or Maximizing a Function PDF NAG Library Manual Mark 23 Procitovano 9 lyutogo 2012 Find minimum of unconstrained multivariable function MATLAB fminunc Constrained Nonlinear Optimization Algorithms MATLAB amp Simulink www mathworks com Procitovano 21 lyutogo 2022 Dodatkovi materialiBonnans J F Gilbert J Ch Lemarechal C Sagastizabal C A 2006 Numerical Optimization Theoretical and Numerical Aspects vid Second Springer ISBN 3 540 35445 X Fletcher Roger 1987 Practical methods of optimization vid 2nd New York John Wiley amp Sons ISBN 978 0 471 91547 8 Nocedal Jorge Wright Stephen J 1999 Quasi Newton Methods Numerical Optimization New York Springer s 192 221 ISBN 0 387 98793 2 Press W H Teukolsky S A Vetterling W T Flannery B P 2007 Section 10 9 Quasi Newton or Variable Metric Methods in Multidimensions Numerical Recipes The Art of Scientific Computing vid 3rd Cambridge University Press ISBN 978 0 521 88068 8 Scales L E 1985 Introduction to Non Linear Optimization New York MacMillan s 84 106 ISBN 0 333 32552 4

Дата публікації:
Топ