Перегляд вихідного коду сторінки Оптимізація (математика)

{{Otheruses|оптимізація}}
[[Файл:Max paraboloid.svg|right|thumb|Графік [[параболоїд]]у, заданого рівнянням ''z'' = f(''x'', ''y'') = −(''x''² + ''y''²) + 4. Глобальний [[Екстремум|максимум]] в точці (''x, y, z'') = (0, 0, 4) позначено синьою точкою.]]
[[Файл:Nelder-Mead Simionescu.gif|thumb|Пошук мінімуму [[Тестові_функції_для_оптимізації#Функції_для_алгоритмів_пошуку_глобального_мінімуму|функції Сіміонеску]] [[Метод Нелдера – Міда|методом Нелдера–Міда]]. Симплекс-вершини впорядковані за величиною, з найменшим (найкращим) значенням 1.]]
'''Математичною оптимізацією''' (інколи, '''оптимізацією''') або '''математичним програмуванням''' в [[Математика|математиці]], [[Інформатика|інформатиці]] та [[Дослідження операцій|дослідженні операцій]] називають відбір найкращого елементу (за певним критерієм) з множини доступних альтернатив.<ref>«[http://glossary.computing.society.informs.org/index.php?page=nature.html The Nature of Mathematical Programming] {{webarchive|url=https://web.archive.org/web/20140305080324/http://glossary.computing.society.informs.org/index.php?page=nature.html |date=2014-03-05 }},» ''Mathematical Programming Glossary'', INFORMS Computing Society.</ref>

У найпростішому випадку '''[[задача оптимізації]]''' полягає у знаходженні [[екстремум]]у ([[мінімум]]у або [[максимум]]у) [[Дійсні числа|дійсної]] [[Функція (математика)|функції]] шляхом систематичного вибору [[Аргумент функції|вхідних значень]] з дозволеного набору та обчислення значення функції. Подальші узагальнення теорії та методів оптимізації до інших формулювань становлять велику область [[Прикладна математика|прикладної математики]]. Взагалі, оптимізація охоплює знаходження «найкращих можливих» значень деякої [[Цільова функція|цільової функції]] в межах [[Область визначення|області визначення]], включаючи різні типи цільових функцій та різні типи областей значення.

== Постановка задачі оптимізації ==
{{main|Задача оптимізації}}
У процесі проєктування ставиться, звичайно, задача визначення найкращих, у деякому значенні, структури або значення параметрів об'єктів. Така задача називається оптимізаційною. Якщо оптимізація пов'язана з розрахунком оптимальних значень параметрів при заданій структурі об'єкта, то вона називається параметричною. Задача вибору оптимальної структури є структурною оптимізацією.

Стандартна математична задача оптимізації формулюється в такий спосіб. Серед елементів χ, що утворюють множину Χ, знайти такий елемент χ<sup>*</sup>, що надає мінімальне значення f(χ<sup>*</sup>) заданій функції f(χ). Для того щоб коректно поставити задачу оптимізації необхідно задати:
# ''[[Допустима множина|Допустиму множину]]''&nbsp;— множину <math>\mathbb{X}=\{\vec{x}|\;g_i(\vec{x})\leq 0,\;i=1,\ldots,m\} \subset \mathbb{R}^n</math> (функції <math>g_i</math> задають обмеження на <math>\mathbb{X}</math>);
# ''[[Цільова функція|Цільову функцію]]''&nbsp;— відображення <math>f\colon\mathbb{X}\to\mathbb{R}</math>;
# ''Критерій пошуку'' (max або min).

Тоді вирішити задачу <math>f(x)\to \min_{\vec{x}\in\mathrm{X}}</math> (при пошуку максимуму буде аналогічне визначення) означає одне з:
# Показати, що <math>\mathbb{X}=\varnothing</math>.
# Показати, що цільова функція <math>f(\vec{x})</math> не обмежена знизу.
# Знайти <math>\vec{x}^*\in\mathbb{X}:\;f(\vec{x}^*)=\min_{\vec{x}\in\mathbb{X}}f(\vec{x})</math>.
# Якщо <math>\nexists \vec{x}^* </math>, то знайти <math>\inf_{\vec{x}\in\mathbb{X}}f(\vec{x})</math>.

Якщо мінімізована функція не є [[опукла функція|опуклою]], то часто обмежуються пошуком локальних мінімумів і максимумів: точок <math>x_0</math> таких, що всюди в деякому їхньому околі <math>f(x)\ge f(x_0)</math> для мінімуму й <math>f(x)\le f(x_0)</math> для максимуму.

Якщо допустима множина <math>\mathbb{X}=\mathbb{R}^n</math> , то така задача називається ''задачею безумовної оптимізації'', в іншому разі&nbsp;— ''задачею умовної оптимізації''.

Функцію ''f'' в різних галузях називають по різному, '''[[Цільова функція|цільовою функцією]]''' ({{lang-en|objective function}}), '''[[Функція втрат|функцією втрат]]''' ({{lang-en|loss function}}) чи '''функцією витрат''' ({{lang-en|cost function}}) (при мінімізації),<ref>W. Erwin Diewert (2008). "cost functions, " ''The New Palgrave Dictionary of Economics'', 2nd Edition [http://www.dictionaryofeconomics.com/article?id=pde2008_C000390&edition=current&q= Contents].</ref> або '''[[Функція корисності|функцією корисності]]''' ({{lang-en|utility function}}) чи '''[[Функція допасованості|функцією допасованості]]''' ({{lang-en|fitness function}}) (максимізація), '''функцією енергії''' ({{lang-en|energy function}}) або '''[[функціонал]]ом енергії''' ({{lang-en|energy functional}}).

== Нотація ==
Задача оптимізації часто записується у своєрідній спеціальній нотації. Ось деякі приклади:

=== Мінімальне і максимальне значення функції ===
Розглянемо наступний запис:
: <math>\min_{x\in\mathbb R}\; (x^2 + 1)</math>

Він позначає мінімальне значення цільової функції <math>x^2 + 1</math>, якщо ''x'' обирається із множини [[Дійсне число|дійсних чисел]] <math>\mathbb R</math>. Мінімальне значення в такому випадку дорівнює <math>1</math>, що відповідає значенню <math>x = 0</math>.

Аналогічно, нотація

: <math>\max_{x\in\mathbb R}\; 2x</math>

запитує максимальне значення цільової функції 2''x'', де ''x'' може бути будь-яким дійсним числом. В даному випадку, не існує такого максимуму, оскільки цільова функція необмежена, тож відповідь буде «[[нескінченність|нескінченністю]]» або «невизначена».

=== Оптимальні вхідні аргументи ===
{{Main|Аргументи максимізації та мінімізації}}
Розглянемо наступний приклад:
: <math>\underset{x\in(-\infty,-1]}{\operatorname{arg\,min}} \; x^2 + 1,</math>
або еквівалентно
: <math>\underset{x}{\operatorname{arg\,min}} \; x^2 + 1, \; \text{коли} \; x\in(-\infty,-1].</math>

Такий запис представляє значення (або декілька значень) [[Аргумент функції|аргументу]] <math>x</math> в [[Проміжок|інтервалі]] <math>(-\infty,-1]</math>, що мінімізує цільову функцію <math>x^2+1</math> (пошук фактичного значення мінімуму функції, в цій задачі не вимагається). В даному випадку, відповідь становить <math>x = -1 </math>, оскільки <math>x = 0</math> не підходить, бо не належить [[Область рішень|заданому інтервалу]].

Аналогічно,
: <math>\underset{x\in[-5,5], \; y\in\mathbb R}{\operatorname{arg\,max}} \; x\cos(y),</math>
або еквівалентно
: <math>\underset{x, \; y}{\operatorname{arg\,max}} \; x\cos(y), \; \text{коли} \; x\in[-5,5], \; y\in\mathbb R,</math>

представляє пару <math>(x,y)</math> (або пари) значень, яка максимізує (які максимізують) значення цільової функції <math>x\cos(y)</math>, із заданими обмеженнями, що <math>x</math> знаходиться в інтервалі <math>[-5,5]</math> (знову ж таки, фактичне максимальне значення для виразу не має значення). В цьому випадку, рішеннями будуть пари значень наступної форми: <math>(5,\,2k\pi)</math> та <math>(-5,\,(2k+1)\pi)</math>, де <math>k</math> може приймати будь-яке [[цілі числа|ціле]] значення.

Оператори <math>\operatorname{arg\,min} </math> та <math>\operatorname{arg\,max} </math> іноді записують як <math>\operatorname{argmin} </math> та <math>\operatorname{argmax} </math>, що розуміють як '''аргумент для мінімуму''' та '''аргумент для максимуму'''.

== Класифікація методів оптимізації ==
Методи оптимізації класифікують відповідно до задач оптимізації:
* Локальні методи: сходяться до якого-небудь локального екстремуму цільової функції. У разі унімодальної цільової функції, цей екстремум єдиний, і буде глобальним максимумом/мінімумом.
* Глобальні методи: мають справу з багатоекстремальними цільовими функціями. При глобальному пошуку основною задачею є виявлення тенденцій глобальної поведінки цільової функції.

Існуючі в цей час методи пошуку можна розбити на три великі групи:
# детерміновані;
# випадкові (стохастичні);
# комбіновані.

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

За видом [[цільова функція|цільової функції]] й [[Допустима множина|допустимої множини]], задачі оптимізації й методи їхнього розв'язання можна розділити на такі класи:
* Задачі оптимізації, у яких цільова функція <math>f(\vec{x})</math> і [[Обмеження (математика)|обмеження]] <math>g_i(\vec{x}),\; i=1,\ldots,m</math> є лінійними функціями, розв'язуються так званими методами ''[[лінійне програмування|лінійного програмування]]''.
* В іншому разі мають справу із задачею ''[[нелінійне програмування|нелінійного програмування]]'' і застосовують відповідні методи. У свою чергу з них виділяють дві часткові задачі:
** якщо <math>f(\vec{x})</math> і <math>g_i(\vec{x}),\;i=1,\ldots,m</math>&nbsp;— опуклі функції, то таку задачу називають задачею ''[[Опукле програмування|опуклого програмування]]'';
** якщо <math>\mathbb{X}\subset \mathbb{Z}</math>, то мають справу із задачею ''[[дискретне програмування|цілочислового (дискретного) програмування]]''.

За вимогами до гладкості й наявності в цільової функції частинних похідних, їх також можна розділити на:
* прямі методи, що вимагають тільки обчислень цільової функції в точках наближень;
* [[Градієнтні методи|методи першого порядку]]: вимагають обчислення перших частинних похідних функції, тобто [[Матриця Якобі|якобіана]] цільової функції;
* методи другого порядку: вимагають обчислення других частинних похідних, тобто [[Матриця Гессе|гессіана]] цільової функції.

Крім того, оптимізаційні методи поділяються на такі групи:
* [[аналітичні методи]] (наприклад, [[Множники Лагранжа|метод множників Лагранжа]] і [[умови Каруша-Куна-Такера]]);
* [[чисельні методи]];
* [[графічні методи]].

Залежно від природи множини '''X''' задачі [[математичне програмування|математичного програмування]] класифікуються так:
* задачі [[дискретне програмування|дискретного програмування]] (або [[комбінаторна оптимізація|комбінаторної оптимізації]])&nbsp;— якщо '''X''' [[Нескінченність|скінченна]] або [[Зліченна множина|зліченна]];
* задачі [[цілочислове програмування|цілочислового програмування]]&nbsp;— якщо '''X''' є [[підмножина|підмножиною]] [[множина|множини]] цілих чисел;
* задачі [[нелінійне програмування|нелінійного програмування]], якщо обмеження або [[цільова функція]] містять [[Лінійна функція|нелінійні функції]] і '''X''' є [[підмножина|підмножиною]] [[Скінченновимірний простір|скінченновимірного]] [[векторний простір|векторного простору]].
* Якщо ж усі [[Обмеження (математика)|обмеження]] і [[цільова функція]] містять лише лінійні функції, то це&nbsp;— задача [[лінійне програмування|лінійного програмування]].

Крім того, розділами [[Математичне програмування|математичного програмування]] є [[параметричне програмування]], [[динамічне програмування]] і [[стохастичне програмування]].
Математичне програмування використовується при розв'язанні оптимізаційних задач [[дослідження операцій]].

Спосіб знаходження екстремуму повністю обумовлюється класом задачі. Але перед тим, як отримати математичну модель, потрібно виконати 4 етапи моделювання:
* Визначення меж системи оптимізації
** Відкидаємо ті зв'язки об'єкта оптимізації із зовнішнім світом, які не можуть сильно вплинути на результат оптимізації, а, точніше, ті, без яких розв'язання спрощується
* Вибір змінних проєктування (керованих змінних)
** «Заморожуємо» значення деяких змінних (некеровані змінні). Інші залишаємо приймати будь-які значення з [[Область допустимих розв'язків|області допустимих рішень]] (керовані змінні)
* Визначення обмежень на керовані змінні
** … (рівності й\або нерівності)
* Вибір числового критерію оптимізації
** Створюємо цільову функцію

== Історія ==
Задачі [[лінійне програмування|лінійного програмування]] були першими, докладно вивченими задачами пошуку [[екстремум]]а функцій при наявності [[Обмеження (математика)|обмежень]] типу [[нерівність|нерівностей]]. В [[1820]]&nbsp;р. [[Фур'є, Жан Батист Жозеф|Ж. Фур'є]] і потім в [[1947]]&nbsp;р. [[Джордж Данціг|Дж. Данціг]] запропонував метод направленого перебору суміжних вершин у напрямку зростання [[цільова функція|цільової функції]]&nbsp;— [[симплекс-метод]], що став основним при розв'язанні задач [[лінійне програмування|лінійного програмування]].

Присутність у назві дисципліни терміна «програмування» пояснюється тим, що перші дослідження й перші застосування лінійних [[задача оптимізації|оптимізаційних задач]] були в сфері економіки, тому що в англійській мові слово «programming» означає [[планування]], складання планів або програм. Цілком природно, що термінологія відображає тісний зв'язок, що існує між математичною постановкою задачі і її економічною інтерпретацією (вивчення оптимальної економічної програми). Термін «[[лінійне програмування]]» був запропонований [[Джордж Данціг|Дж. Данцігом]] в [[1949]] році для вивчення теоретичних і алгоритмічних задач, пов'язаних з [[задача оптимізації|оптимізацією]] лінійних функцій при лінійних обмеженнях.
Тому найменування «Математичне програмування» пов'язане з тим, що метою розв'язання задач є вибір оптимальної програми дій.

Виділення класу екстремальних задач, обумовлених [[Лінійний функціонал|лінійним]] [[функціонал]]ом на множині, що задається лінійними обмеженнями, варто віднести до 30-х років XX сторіччя. Одними з перших, що досліджували в загальній формі задачі [[лінійне програмування|лінійного програмування]], були: [[Джон фон Нейман]], знаменитий математик і фізик, що довів основну теорему про матричні ігри й вивчив економічну [[Математична модель|модель]], що носить його ім'я; радянський академік, лауреат [[Нобелівська премія з економіки|нобелівської премії]] (1975&nbsp;р.) [[Канторович Леонід Віталійович|Л.&nbsp;В.&nbsp;Канторович]], що сформулював ряд задач лінійного програмування й запропонував (1939&nbsp;р.) метод їхнього розв'язання ([[метод розв'язних множників]]), що незначно відрізняється від [[симплекс-метод]]у.

В [[1931]]&nbsp;р. угорський математик {{Нп|Ейген Егерварі|||Jenő Egerváry}} розглянув математичну постановку й вирішив задачу [[лінійне програмування|лінійного програмування]], що має назва «проблема вибору», метод розв'язання одержав назву «[[Угорський алгоритм|угорського методу»]].

[[Канторович Леонід Віталійович|Л.&nbsp;В.&nbsp;Канторовичем]] разом із М.&nbsp;К.&nbsp;Гавуриним в 1949&nbsp;р. розроблено {{нп|метод потенціалів||ru|Метод потенциалов}}, що застосовується при розв'язанні [[транспортна задача|транспортних задач]]. У наступних роботах [[Канторович Леонід Віталійович|Л.&nbsp;В.&nbsp;Канторовича]], В.&nbsp;С.&nbsp;Немчинова, В.&nbsp;В.&nbsp;Новожилова, А.&nbsp;Л.&nbsp;Лур'є, А. Брудно, {{нп|Аганбегян Абел Гезевич|А. Г. Аганбегяна|ru|Аганбегян, Абел Гезевич}}, Д.&nbsp;Б.&nbsp;Юдіна, Е.&nbsp;Г.&nbsp;Гольштейна й інших математиків і економістів отримали подальший розвиток як математична теорія [[лінійне програмування|лінійного]] і [[нелінійне програмування|нелінійного програмування]], так і застосування її методів до дослідження різних економічних проблем.
Методам лінійного програмування присвячено багато робіт зарубіжних учених. В [[1941]]&nbsp;р. {{нп|Френк Лаврен Хітчкок|Ф. Л. Хітчкок||Frank Lauren Hitchcock}} поставив [[транспортна задача|транспортну задачу]]. Основний метод розв'язання задач [[лінійне програмування|лінійного програмування]]&nbsp;— [[симплекс-метод]]&nbsp;— був опублікований в 1949&nbsp;р. [[Джордж Данціг|Дж. Данцігом]]. Подальший розвиток методи [[лінійне програмування|лінійного]] і [[нелінійне програмування|нелінійного програмування]] отримали в роботах {{Нп|кун Гарольд|Г. Куна|en|Harold W. Kuhn}}, {{Нп|таккер Альберт|А. Таккера|en|Albert W. Tucker}}, [[Гасс]]а (Gass S. I.), [[Чарнес]]а (Charnes A.), Е.&nbsp;М.&nbsp;Біла (Beale E. M.) та інших.

Одночасно з розвитком [[лінійне програмування|лінійного програмування]] велика увага приділялася задачам нелінійного програмування, у яких або [[цільова функція]], або обмеження, або те й те нелінійні. В 1951&nbsp;р. була опублікована робота Куна й Таккера, у якій наведені необхідні й достатні умови оптимальності для розв'язання задач нелінійного програмування. Ця робота послужила основою для наступних досліджень у цій галузі.

Починаючи з 1955&nbsp;р., опубліковано багато робіт з [[квадратичне програмування|квадратичного програмування]] (роботи Била, [[Баранкін Едвард Вільям|Е. Баранкіна]] (Barankin E.) і [[Дорфман]]а (Dorfman R.), {{Не перекладено|Маргарита Франк|М. Франк|en|Marguerite Frank}}, {{Не перекладено|Філіп Вульф|Ф. Вульфа|en|Philip Wolfe (mathematician)}}, [[Гаррі Марковіц|Г. Марковіца]] та інших). У роботах [[Денніса]] (Dennis J. B.), [[Розена]] (Rosen J. B.) і [[Зонтендейка]] (Zontendijk G.) розроблено [[Градієнтний спуск|градієнтні методи]] розв'язання задач [[нелінійне програмування|нелінійного програмування]].

У даний час для ефективного застосування методів математичного програмування й розв'язання задач на комп'ютерах розроблені [[Мова алгебраїчного моделювання|мови алгебраїчного моделювання]], представниками якими є [[AMPL (мова програмування)|AMPL]] і [[LANGO]].


== Обчислювальні методи оптимізації ==
Для розв'язання задач, дослідники можуть використовувати алгоритми, які зупиняються за скінченну кількість кроків, або [[Метод ітерації (алгоритм)|ітераційні методи,]] які збігаються до рішення (на певному класі задач), або [[Евристичний алгоритм|евристики]], які можуть надати приблизні рішення деяких задач (хоча їхні ітерації не обов'язково будуть сходитись).

=== Алгоритми оптимізації ===
{{seealso|Список_алгоритмів#Алгоритми_оптимізації}}

* [[Симплекс-метод]] [[Джордж Данціг|Джорджа Данцига]], створений для [[Лінійне програмування|лінійного програмування]].
* Розширення симплексного-методу, створене для [[Квадратичне програмування|квадратичного програмування]] і для [[Задача дробово-лінійного програмування|дробово-лінійного програмування]].
* Варіанти симплекс-методу, які особливо пасують у випадку [[Потокова мережа|оптимізації мережі]].
* [[Комбінаторна оптимізація|Комбінаторні алгоритми]]
* [[Алгоритми квантової оптимізації]]

==== Алгоритм оптимізації машинного навчання ====
Алгоритм оптимізації [[Машинне навчання|машинного навчання]] виконується ітераційним шляхом порівняння різних рішень до досягнення оптимального або задовільного рішення. Алгоритми оптимізації допомагають мінімізувати або максимізувати [[Цільова функція|цільову функцію]] ''E(x)'', яка є просто математичною функцією, залежною від внутрішніх параметрів моделі, що використовуються в моделі при обчисленні цільових значень (''Y'') по множині предикторів (''X''). Існують два типи алгоритмів оптимізації, які широко використовуються, це алгоритми нульового порядку, алгоритми оптимізації першого порядку та алгоритми оптимізації другого порядку.<ref name="Walia,A 2017">Walia, A (2017). Типи алгоритмів оптимізації, що використовуються в нейронних мережах і способах оптимізації сходження градієнтів. https://towardsdatascience.com/types-of-optimization-algorithms-used-in-neural-networks-and-ways-to-optimize-gradient-95ae5d39529f {{Webarchive|url=https://web.archive.org/web/20200118085935/https://towardsdatascience.com/types-of-optimization-algorithms-used-in-neural-networks-and-ways-to-optimize-gradient-95ae5d39529f |date=2020-01-18 }}</ref>

===== Алгоритми нульового порядку =====
Алгоритми нульового порядку (або без похідних) використовують лише значення критерію на деяких позиціях. Це популярний метод, коли інформацію про [[градієнт]] і [[гессіан]] складно або не можливо отримати, наприклад, функції не вказано явно.<ref> E. Ruffio, D. Saury, D. Petit, M.Girault. Алгоритми оптимізації нульового порядку. http://www.sft.asso.fr/Local/sft/dir/user-3775/documents/actes/Metti5_School/Lectures&Tutorials-Texts/Text-T2-Ruffio.pdf </ref>

===== Алгоритми оптимізації першого порядку =====
Ці алгоритми мінімізують або максимізують функцію втрат ''E(x)'' за допомогою значення градієнта обчисленного по параметрам. Найбільш широко використовуваним алгоритмом оптимізації першого порядку є [[градієнтний спуск]]. Похідна першого порядку відображає, як зменшується чи збільшується функція в певній точці. Похідні першого порядку описують пряму, дотичну до точки на поверхні похибки.<ref>Ye.Y. Алгоритми оптимізації нульового порядку та першого порядку І. https://web.stanford.edu/class/msande311/lecture10.pdf </ref>

===== Алгоритми оптимізації другого порядку =====
Методи другого порядку використовують похідну другого порядку, яка також називається гессіаном, для мінімізації або максимізації функції втрат. Гессіан є матрицею часткових похідних другого порядку. Оскільки, обчислення других похідних є затратною дією по кількості операцій, тому такі алгоритми не мають широкого вжитку. Похідна другого порядку повідомляє нам, чи збільшується або зменшується перша похідна, що загалом вказує на [[Кривина_(математика)#Кривина_кривої|кривину]] функції. Також гесіан задає [[поверхня другого порядку|поверхню другого порядку]], дотичну до поверхні похибки та яка має таку саму кривину.<ref>Manson, L.; Baxter, J.; Bartlett. P. & Fream, M. Boosting algorithms as gradient descent.</ref>

=== Ітераційні методи ===
{{main|Метод ітерації (алгоритм)}}
{{seealso|Скінченні різниці|Теорія наближень|Чисельні методи}}
[[Метод ітерації (алгоритм)|Ітераційні методи]], що використовуються для вирішення завдань [[Нелінійне програмування|нелінійного програмування]], розрізняються залежно від того, чи оцінюють вони [[Матриця Гессе|гессіан]], градієнт або тільки значення функцій. При оцінці гессіану (''H'') і градієнту (''G'') покращується [[швидкість збіжності]], для функцій, для яких ці величини існують і змінюються досить гладко, використання цих оцінок збільшує [[Теорія складності обчислень|обчислювальну складність]] (або обчислювальну вартість) кожної ітерації. У деяких випадках обчислювальна складність може бути занадто високою.

Одним з основних критеріїв для оптимізаторів є просто кількість необхідних оцінок функцій, оскільки це часто потребує набагато більше обчислень, ніж потрібно самому оптимізатору, який здебільшого мусить оперувати над N змінними. Похідні надають детальну інформацію для оптимізаторів, але їх і важче обчислити, наприклад, [[апроксимація]] градієнта потребує принаймні ''N + 1'' оцінку функцій. Для наближень 2-х похідних (вони знаходяться у матриці Гессе) число оцінок функцій буде порядку ''N²''. Метод Ньютона вимагає похідних 2-го порядку, тому для кожної ітерації кількість викликів функцій має порядок ''N²'', але для більш простого чистого градієнтного оптимізатора потрібно лише ''N''. Однак оптимізатори градієнтів потребують зазвичай більше ітерацій, ніж алгоритм Ньютона. Яка з них буде найкращою за кількостю викликів функцій залежить від конкретної задачі.

* Методи, які оцінюють гессіан (або наближений гессіан через [[скінченні різниці]]):
** [[Метод Ньютона в оптимізації]]
** [[Послідовне квадратичне програмування]]: метод на основі Ньютона для проблем малого та середнього масштабу. Деякі версії можуть впоратись з багатовимірними проблемами.
** [[Метод внутрішньої точки|Методи внутрішньої точки]]: Це великий клас методів для умовної оптимізації. Деякі методи внутрішньої точки використовують тільки інформацію про градієнт, а інші вимагають оцінки гессіанів.
* Методи, які оцінюють градієнт, або апроксимують значення градієнту (або навіть [[Субдиференціал|субградієнту]]):
** Методи [[Координатний спуск|координатного спуску]]: алгоритми, які оновлюють одну координату за одну ітерацію
** [[Метод спряженого градієнта|Метод спряжених градієнтів]]: [[Метод ітерації (алгоритм)|ітераційні методи]] для великих задач. (Теоретично ці методи закінчуються за кінцеву кількість кроків з квадратичними цільовими функціями, проте на практиці не спостерігається зупинка за кінцеву кількість кроків на комп'ютерах зі скінченною точністю.)
** [[Градієнтний спуск]] (інколи, «крутий спуск» чи «крутий підйом»): (повільний) метод з точки зору історичного та теоретичного інтересу, який наново викликав інтерес до знаходження наближених розв'язань величезних проблем.
** [[Субградієнтний метод|Субградієнтні методи]]&nbsp;— ітераційний метод для великих [[Теорема Радемахера|локально]] [[Ліпшицеве відображення|ліпшицевих]] функцій з використанням [[Субдиференціал|узагальнених градієнтів]] . За Борисом Т.&nbsp;Поляком, субградієнтно-проєкційні методи схожі з методами спряжених градієнтів.
* Методи, які оцінюють тільки значення функцій: Якщо задача неперервно диференційовна, то градієнти можна апроксимувати за допомогою скінченних різниць, в такому випадку можна використовувати метод на основі градієнта.
** Методи [[Інтерполяція|інтерполяції]].
** Методи [[Метод Хука — Дживса|пошуку шаблону]], які мають кращі властивості збіжності, ніж евристика [[Метод Нелдера – Міда|Нелдера&nbsp;— Міда]], яка наведена нижче.

== Див. також ==
* [[Список_алгоритмів#Алгоритми_оптимізації|Алгоритми оптимізації]]
* [[Задача оптимізації]]
* [[Складність апроксимації]]
* [[Алгоритм Франк — Вульфа]]
* [[Неперервна оптимізація]]
* [[Дискретна оптимізація]]

== Примітки ==
{{reflist}}

== Література ==
{{2 стовпці}}
# [[Варіаційне числення]] та методи оптимізації: підручник / О.&nbsp;М.&nbsp;Піддубний, Ю.&nbsp;І.&nbsp;Харкевич ; Східноєвроп. нац. ун-т ім. Лесі Українки.&nbsp;— Луцьк: Гадяк Ж. В., 2015.&nbsp;— 331 с.&nbsp;— (Посібники та підручники СНУ ім. Лесі Українки).&nbsp;— ISBN 978-617-7129-36-2.&nbsp;— ISBN 978-966-600-5 (серія)
# Дослідження операцій і методи оптимізації: навч. посібник для студ. вищ. навч. закладів / М.&nbsp;Є.&nbsp;Корольов [та ін.] ; Відкритий міжнародний ун-т розвитку людини «Україна».&nbsp;— К. : Університет «Україна», 2007.&nbsp;— 177 с.&nbsp;— ISBN 978-966-388-182-9
# Задачі, методи та алгоритми оптимізації: навч. посіб. для студ. вищ. навч. закл. / І.&nbsp;В.&nbsp;Бейко, П.&nbsp;М.&nbsp;Зінько, О.&nbsp;Г.&nbsp;Наконечний ; Київ. нац. ун-т ім. Тараса Шевченка.&nbsp;— 2-ге вид., переробл.&nbsp;— К. : Київ. ун-т, 2012.&nbsp;— 799 с.&nbsp;— Бібліогр.: с. 769—779.&nbsp;— ISBN 978-966-439-564-6
# Комп'ютерна реалізація методів оптимізації: навч. посіб. для студ. та асп. фіз.-мат., інж. та екон. спец. / В.&nbsp;О.&nbsp;Любчак, Л.&nbsp;Г.&nbsp;Острівна ; Сумський держ. ун-т.&nbsp;— Суми: Видавництво Сумського держ. ун-ту, 2002.&nbsp;— 161 с.: рис.&nbsp;— ISBN 966-7668-11-8
# Математичні методи оптимізації: навч. посіб. / М.&nbsp;І.&nbsp;Горбійчук ; Івано-Франків. нац. техн. ун-т нафти і газу.&nbsp;— Івано-Франківськ: ІФНТУНГ, 2018.&nbsp;— 302 с. : рис., табл.&nbsp;— ISBN 978-966-694-295-4
# Математичні методи оптимізації: навч. посіб. / О.&nbsp;К.&nbsp;Молодід ; Нац. техн. ун-т України «Київ. політехн. ін-т».&nbsp;— К. : НТУУ «КПІ», 2012.&nbsp;— 204 с. : рис., табл.
# Методи оптимізації: алгоритми, приклади, задачі: навч. посіб. для студ. усіх спец. напряму підгот. «Комп'ютерні науки» / Г.&nbsp;А.&nbsp;Гайна ; Київський національний ун-т будівництва і архітектури.&nbsp;— К. : КНУБА, 2005.&nbsp;— 144 с.
# Методи оптимізації: навч. посіб. до проведення лаб. і практ. робіт / О.&nbsp;В.&nbsp;Карташов, А.&nbsp;В.&nbsp;Бабкіна, Н.&nbsp;Ю.&nbsp;Ємцева, Р.&nbsp;А.&nbsp;Пудло ; Нац. аерокосм. ун-т ім. М.&nbsp;Є.&nbsp;Жуковського «Харк. авіац. ін-т».&nbsp;— Х. : ХАІ, 2009.&nbsp;— 111 с.
# Методи оптимізації складних систем: навч. посіб. для студ. спец. «Комп'ютеризовані системи управління і автоматики» / І.&nbsp;В.&nbsp;Кузьмін [та ін.] ; Вінницький держ. технічний ун-т.&nbsp;— Вінниця: ВДТУ, 2003.&nbsp;— 165 с.: рис.
# Методи оптимізації та дослідження операцій [Текст]: навч. посіб. / П.&nbsp;М.&nbsp;Мартинюк, О.&nbsp;Р.&nbsp;Мічута ; Нац. ун-т вод. госп-ва та природокористування.&nbsp;— Рівне: НУВГП, 2011.&nbsp;— 283 с.
# Оптимізаційні методи та моделі: підручник / В.&nbsp;С.&nbsp;Григорків, М.&nbsp;В.&nbsp;Григорків ; Чернів. нац. ун-т ім. Юрія Федьковича.&nbsp;— Чернівці: Рута, 2016.&nbsp;— 400 с. : рис., табл.&nbsp;— ISBN 978-966-423-364-1
# Основи теорії і методів оптимізації: навч. посібник для студ. мат. спец. вищих навч. закл. / М.&nbsp;І.&nbsp;Жалдак, Ю.&nbsp;В.&nbsp;Триус.&nbsp;— Черкаси: Брама-Україна, 2005.&nbsp;— 608 с.: рис.&nbsp;— ISBN 966-8756-04-5
# Теорія оптимізації: навч. посіб. для студентів ВНЗ / О.&nbsp;І.&nbsp;Щепотьєв, А.&nbsp;В.&nbsp;Жильцов.&nbsp;— Київ: Компринт, 2017.&nbsp;— 241 с. : рис., табл.&nbsp;— ISBN 978-966-929-586-6
# ''Уханська О. М.'' Тексти лекцій з курсу «Методи оптимізації».&nbsp;— Львів: В-во НУ «ЛП», 2003.&nbsp;— 107 с.
# ''Худий М.І''. Методи оптимізації. Лінійне програмування.&nbsp;— Львів, 1977.
# {{книга|автор = Гилл Ф., Мюррей У., Райт М.|заголовок = Практическая оптимизация. Пер. с англ|місце = М.|видавництво = Мир|рік = 1985}}
# Mathematical optimization methods: manual for higher educational institutions / V. Klymenko, O. Akmaldinova.&nbsp;— K. : NAU-druk, 2009.&nbsp;— 196 p. : fig., tab.&nbsp;— ISBN 978-966-598-584-6
# Methods and models of optimization: work book: an educational book / G. G. Shvachich [et al.] ; Alfred Nobel univ., Dnipropetrovs'k.&nbsp;— Dnipropetrovs'k: Alfred Nobel univ., Dnipropetrovs'k, 2012.&nbsp;— 120 p. : fig., tab.&nbsp;— ISBN 978-966-434-125-4
# Optimization theory / H. T. Jongen [та ін.].&nbsp;— Boston[etc.]: Kluwer academic publishers, 2004.&nbsp;— XI, 443 p.: fig.&nbsp;— Бібліогр.: p. 429—443.&nbsp;— ISBN 1-4020-8098-0
</div>
{{Методи оптимізації}}
{{Інформатика}}
{{Розділи математики|state=collapsed}}
{{Системотехніка}}
{{Мікроекономіка}}
{{Перекласти|en|Mathematical optimization}}
{{Math-stub}}
[[Категорія:Оптимізація|Математика]]
[[Категорія:Дослідження операцій]]
[[Категорія:Проєктування]]
[[Категорія:Галузі інформатики]]