Математичною оптимізацією (інколи, оптимізацією) або математичним програмуванням в математиці, інформатиці та дослідженні операцій називають відбір найкращого елементу (за певним критерієм) з множини доступних альтернатив.
У найпростішому випадку задача оптимізації полягає у знаходженні екстремуму (мінімуму або максимуму) дійсної функції шляхом систематичного вибору вхідних значень з дозволеного набору та обчислення значення функції. Подальші узагальнення теорії та методів оптимізації до інших формулювань становлять велику область прикладної математики. Взагалі, оптимізація охоплює знаходження «найкращих можливих» значень деякої цільової функції в межах області визначення, включаючи різні типи цільових функцій та різні типи областей значення.
Постановка задачі оптимізації
У процесі проєктування ставиться, звичайно, задача визначення найкращих, у деякому значенні, структури або значення параметрів об'єктів. Така задача називається оптимізаційною. Якщо оптимізація пов'язана з розрахунком оптимальних значень параметрів при заданій структурі об'єкта, то вона називається параметричною. Задача вибору оптимальної структури є структурною оптимізацією.
Стандартна математична задача оптимізації формулюється в такий спосіб. Серед елементів χ, що утворюють множину Χ, знайти такий елемент χ*, що надає мінімальне значення f(χ*) заданій функції f(χ). Для того щоб коректно поставити задачу оптимізації необхідно задати:
- Допустиму множину — множину (функції задають обмеження на );
- Цільову функцію — відображення ;
- Критерій пошуку (max або min).
Тоді вирішити задачу (при пошуку максимуму буде аналогічне визначення) означає одне з:
- Показати, що .
- Показати, що цільова функція не обмежена знизу.
- Знайти .
- Якщо , то знайти .
Якщо мінімізована функція не є опуклою, то часто обмежуються пошуком локальних мінімумів і максимумів: точок таких, що всюди в деякому їхньому околі для мінімуму й для максимуму.
Якщо допустима множина , то така задача називається задачею безумовної оптимізації, в іншому разі — задачею умовної оптимізації.
Функцію f в різних галузях називають по різному, цільовою функцією (англ. objective function), функцією втрат (англ. loss function) чи функцією витрат (англ. cost function) (при мінімізації), або функцією корисності (англ. utility function) чи функцією допасованості (англ. fitness function) (максимізація), функцією енергії (англ. energy function) або функціоналом енергії (англ. energy functional).
Нотація
Задача оптимізації часто записується у своєрідній спеціальній нотації. Ось деякі приклади:
Мінімальне і максимальне значення функції
Розглянемо наступний запис:
Він позначає мінімальне значення цільової функції , якщо x обирається із множини дійсних чисел . Мінімальне значення в такому випадку дорівнює , що відповідає значенню .
Аналогічно, нотація
запитує максимальне значення цільової функції 2x, де x може бути будь-яким дійсним числом. В даному випадку, не існує такого максимуму, оскільки цільова функція необмежена, тож відповідь буде «нескінченністю» або «невизначена».
Оптимальні вхідні аргументи
Розглянемо наступний приклад:
або еквівалентно
Такий запис представляє значення (або декілька значень) аргументу в інтервалі , що мінімізує цільову функцію (пошук фактичного значення мінімуму функції, в цій задачі не вимагається). В даному випадку, відповідь становить , оскільки не підходить, бо не належить заданому інтервалу.
Аналогічно,
або еквівалентно
представляє пару (або пари) значень, яка максимізує (які максимізують) значення цільової функції , із заданими обмеженнями, що знаходиться в інтервалі (знову ж таки, фактичне максимальне значення для виразу не має значення). В цьому випадку, рішеннями будуть пари значень наступної форми: та , де може приймати будь-яке ціле значення.
Оператори та іноді записують як та , що розуміють як аргумент для мінімуму та аргумент для максимуму.
Класифікація методів оптимізації
Методи оптимізації класифікують відповідно до задач оптимізації:
- Локальні методи: сходяться до якого-небудь локального екстремуму цільової функції. У разі унімодальної цільової функції, цей екстремум єдиний, і буде глобальним максимумом/мінімумом.
- Глобальні методи: мають справу з багатоекстремальними цільовими функціями. При глобальному пошуку основною задачею є виявлення тенденцій глобальної поведінки цільової функції.
Існуючі в цей час методи пошуку можна розбити на три великі групи:
- детерміновані;
- випадкові (стохастичні);
- комбіновані.
За критерієм вимірності допустимої множини, методи оптимізації поділяють на методи одномірної оптимізації і методи багатомірної оптимізації.
За видом цільової функції й допустимої множини, задачі оптимізації й методи їхнього розв'язання можна розділити на такі класи:
- Задачі оптимізації, у яких цільова функція і обмеження є лінійними функціями, розв'язуються так званими методами лінійного програмування.
- В іншому разі мають справу із задачею нелінійного програмування і застосовують відповідні методи. У свою чергу з них виділяють дві часткові задачі:
- якщо і — опуклі функції, то таку задачу називають задачею опуклого програмування;
- якщо , то мають справу із задачею цілочислового (дискретного) програмування.
За вимогами до гладкості й наявності в цільової функції частинних похідних, їх також можна розділити на:
- прямі методи, що вимагають тільки обчислень цільової функції в точках наближень;
- методи першого порядку: вимагають обчислення перших частинних похідних функції, тобто якобіана цільової функції;
- методи другого порядку: вимагають обчислення других частинних похідних, тобто гессіана цільової функції.
Крім того, оптимізаційні методи поділяються на такі групи:
- аналітичні методи (наприклад, метод множників Лагранжа і умови Каруша-Куна-Такера);
- чисельні методи;
- .
Залежно від природи множини X задачі математичного програмування класифікуються так:
- задачі дискретного програмування (або комбінаторної оптимізації) — якщо X скінченна або зліченна;
- задачі цілочислового програмування — якщо X є підмножиною множини цілих чисел;
- задачі нелінійного програмування, якщо обмеження або цільова функція містять нелінійні функції і X є підмножиною скінченновимірного векторного простору.
- Якщо ж усі обмеження і цільова функція містять лише лінійні функції, то це — задача лінійного програмування.
Крім того, розділами математичного програмування є параметричне програмування, динамічне програмування і стохастичне програмування. Математичне програмування використовується при розв'язанні оптимізаційних задач дослідження операцій.
Спосіб знаходження екстремуму повністю обумовлюється класом задачі. Але перед тим, як отримати математичну модель, потрібно виконати 4 етапи моделювання:
- Визначення меж системи оптимізації
- Відкидаємо ті зв'язки об'єкта оптимізації із зовнішнім світом, які не можуть сильно вплинути на результат оптимізації, а, точніше, ті, без яких розв'язання спрощується
- Вибір змінних проєктування (керованих змінних)
- «Заморожуємо» значення деяких змінних (некеровані змінні). Інші залишаємо приймати будь-які значення з області допустимих рішень (керовані змінні)
- Визначення обмежень на керовані змінні
- … (рівності й\або нерівності)
- Вибір числового критерію оптимізації
- Створюємо цільову функцію
Історія
Задачі лінійного програмування були першими, докладно вивченими задачами пошуку екстремума функцій при наявності обмежень типу нерівностей. В 1820 р. Ж. Фур'є і потім в 1947 р. Дж. Данціг запропонував метод направленого перебору суміжних вершин у напрямку зростання цільової функції — симплекс-метод, що став основним при розв'язанні задач лінійного програмування.
Присутність у назві дисципліни терміна «програмування» пояснюється тим, що перші дослідження й перші застосування лінійних оптимізаційних задач були в сфері економіки, тому що в англійській мові слово «programming» означає планування, складання планів або програм. Цілком природно, що термінологія відображає тісний зв'язок, що існує між математичною постановкою задачі і її економічною інтерпретацією (вивчення оптимальної економічної програми). Термін «лінійне програмування» був запропонований Дж. Данцігом в 1949 році для вивчення теоретичних і алгоритмічних задач, пов'язаних з оптимізацією лінійних функцій при лінійних обмеженнях. Тому найменування «Математичне програмування» пов'язане з тим, що метою розв'язання задач є вибір оптимальної програми дій.
Виділення класу екстремальних задач, обумовлених лінійним функціоналом на множині, що задається лінійними обмеженнями, варто віднести до 30-х років XX сторіччя. Одними з перших, що досліджували в загальній формі задачі лінійного програмування, були: Джон фон Нейман, знаменитий математик і фізик, що довів основну теорему про матричні ігри й вивчив економічну модель, що носить його ім'я; радянський академік, лауреат нобелівської премії (1975 р.) Л. В. Канторович, що сформулював ряд задач лінійного програмування й запропонував (1939 р.) метод їхнього розв'язання (), що незначно відрізняється від симплекс-методу.
В 1931 р. угорський математик [en] розглянув математичну постановку й вирішив задачу лінійного програмування, що має назва «проблема вибору», метод розв'язання одержав назву «угорського методу».
Л. В. Канторовичем разом із М. К. Гавуриним в 1949 р. розроблено [ru], що застосовується при розв'язанні транспортних задач. У наступних роботах Л. В. Канторовича, В. С. Немчинова, В. В. Новожилова, А. Л. Лур'є, А. Брудно, [ru], Д. Б. Юдіна, Е. Г. Гольштейна й інших математиків і економістів отримали подальший розвиток як математична теорія лінійного і нелінійного програмування, так і застосування її методів до дослідження різних економічних проблем. Методам лінійного програмування присвячено багато робіт зарубіжних учених. В 1941 р. [en] поставив транспортну задачу. Основний метод розв'язання задач лінійного програмування — симплекс-метод — був опублікований в 1949 р. Дж. Данцігом. Подальший розвиток методи лінійного і нелінійного програмування отримали в роботах [en], [en], (Gass S. I.), (Charnes A.), Е. М. Біла (Beale E. M.) та інших.
Одночасно з розвитком лінійного програмування велика увага приділялася задачам нелінійного програмування, у яких або цільова функція, або обмеження, або те й те нелінійні. В 1951 р. була опублікована робота Куна й Таккера, у якій наведені необхідні й достатні умови оптимальності для розв'язання задач нелінійного програмування. Ця робота послужила основою для наступних досліджень у цій галузі.
Починаючи з 1955 р., опубліковано багато робіт з квадратичного програмування (роботи Била, (Barankin E.) і Дорфмана (Dorfman R.), [en], [en], Г. Марковіца та інших). У роботах (Dennis J. B.), (Rosen J. B.) і (Zontendijk G.) розроблено градієнтні методи розв'язання задач нелінійного програмування.
У даний час для ефективного застосування методів математичного програмування й розв'язання задач на комп'ютерах розроблені мови алгебраїчного моделювання, представниками якими є AMPL і .
Обчислювальні методи оптимізації
Для розв'язання задач, дослідники можуть використовувати алгоритми, які зупиняються за скінченну кількість кроків, або ітераційні методи, які збігаються до рішення (на певному класі задач), або евристики, які можуть надати приблизні рішення деяких задач (хоча їхні ітерації не обов'язково будуть сходитись).
Алгоритми оптимізації
- Симплекс-метод Джорджа Данцига, створений для лінійного програмування.
- Розширення симплексного-методу, створене для квадратичного програмування і для дробово-лінійного програмування.
- Варіанти симплекс-методу, які особливо пасують у випадку оптимізації мережі.
- Комбінаторні алгоритми
- Алгоритми квантової оптимізації
Алгоритм оптимізації машинного навчання
Алгоритм оптимізації машинного навчання виконується ітераційним шляхом порівняння різних рішень до досягнення оптимального або задовільного рішення. Алгоритми оптимізації допомагають мінімізувати або максимізувати цільову функцію E(x), яка є просто математичною функцією, залежною від внутрішніх параметрів моделі, що використовуються в моделі при обчисленні цільових значень (Y) по множині предикторів (X). Існують два типи алгоритмів оптимізації, які широко використовуються, це алгоритми нульового порядку, алгоритми оптимізації першого порядку та алгоритми оптимізації другого порядку.
Алгоритми нульового порядку
Алгоритми нульового порядку (або без похідних) використовують лише значення критерію на деяких позиціях. Це популярний метод, коли інформацію про градієнт і гессіан складно або не можливо отримати, наприклад, функції не вказано явно.
Алгоритми оптимізації першого порядку
Ці алгоритми мінімізують або максимізують функцію втрат E(x) за допомогою значення градієнта обчисленного по параметрам. Найбільш широко використовуваним алгоритмом оптимізації першого порядку є градієнтний спуск. Похідна першого порядку відображає, як зменшується чи збільшується функція в певній точці. Похідні першого порядку описують пряму, дотичну до точки на поверхні похибки.
Алгоритми оптимізації другого порядку
Методи другого порядку використовують похідну другого порядку, яка також називається гессіаном, для мінімізації або максимізації функції втрат. Гессіан є матрицею часткових похідних другого порядку. Оскільки, обчислення других похідних є затратною дією по кількості операцій, тому такі алгоритми не мають широкого вжитку. Похідна другого порядку повідомляє нам, чи збільшується або зменшується перша похідна, що загалом вказує на (кривину) функції. Також гесіан задає поверхню другого порядку, дотичну до поверхні похибки та яка має таку саму кривину.
Ітераційні методи
Ітераційні методи, що використовуються для вирішення завдань нелінійного програмування, розрізняються залежно від того, чи оцінюють вони гессіан, градієнт або тільки значення функцій. При оцінці гессіану (H) і градієнту (G) покращується швидкість збіжності, для функцій, для яких ці величини існують і змінюються досить гладко, використання цих оцінок збільшує обчислювальну складність (або обчислювальну вартість) кожної ітерації. У деяких випадках обчислювальна складність може бути занадто високою.
Одним з основних критеріїв для оптимізаторів є просто кількість необхідних оцінок функцій, оскільки це часто потребує набагато більше обчислень, ніж потрібно самому оптимізатору, який здебільшого мусить оперувати над N змінними. Похідні надають детальну інформацію для оптимізаторів, але їх і важче обчислити, наприклад, апроксимація градієнта потребує принаймні N + 1 оцінку функцій. Для наближень 2-х похідних (вони знаходяться у матриці Гессе) число оцінок функцій буде порядку N². Метод Ньютона вимагає похідних 2-го порядку, тому для кожної ітерації кількість викликів функцій має порядок N², але для більш простого чистого градієнтного оптимізатора потрібно лише N. Однак оптимізатори градієнтів потребують зазвичай більше ітерацій, ніж алгоритм Ньютона. Яка з них буде найкращою за кількостю викликів функцій залежить від конкретної задачі.
- Методи, які оцінюють гессіан (або наближений гессіан через скінченні різниці):
- Метод Ньютона в оптимізації
- Послідовне квадратичне програмування: метод на основі Ньютона для проблем малого та середнього масштабу. Деякі версії можуть впоратись з багатовимірними проблемами.
- Методи внутрішньої точки: Це великий клас методів для умовної оптимізації. Деякі методи внутрішньої точки використовують тільки інформацію про градієнт, а інші вимагають оцінки гессіанів.
- Методи, які оцінюють градієнт, або апроксимують значення градієнту (або навіть субградієнту):
- Методи координатного спуску: алгоритми, які оновлюють одну координату за одну ітерацію
- Метод спряжених градієнтів: ітераційні методи для великих задач. (Теоретично ці методи закінчуються за кінцеву кількість кроків з квадратичними цільовими функціями, проте на практиці не спостерігається зупинка за кінцеву кількість кроків на комп'ютерах зі скінченною точністю.)
- Градієнтний спуск (інколи, «крутий спуск» чи «крутий підйом»): (повільний) метод з точки зору історичного та теоретичного інтересу, який наново викликав інтерес до знаходження наближених розв'язань величезних проблем.
- Субградієнтні методи — ітераційний метод для великих локально ліпшицевих функцій з використанням узагальнених градієнтів . За Борисом Т. Поляком, субградієнтно-проєкційні методи схожі з методами спряжених градієнтів.
- Методи, які оцінюють тільки значення функцій: Якщо задача неперервно диференційовна, то градієнти можна апроксимувати за допомогою скінченних різниць, в такому випадку можна використовувати метод на основі градієнта.
- Методи інтерполяції.
- Методи пошуку шаблону, які мають кращі властивості збіжності, ніж евристика Нелдера — Міда, яка наведена нижче.
Див. також
- (Алгоритми оптимізації)
- Задача оптимізації
- Складність апроксимації
- Алгоритм Франк — Вульфа
Примітки
- «The Nature of Mathematical Programming [ 2014-03-05 у Wayback Machine.],» Mathematical Programming Glossary, INFORMS Computing Society.
- W. Erwin Diewert (2008). "cost functions, " The New Palgrave Dictionary of Economics, 2nd Edition Contents.
- Walia, A (2017). Типи алгоритмів оптимізації, що використовуються в нейронних мережах і способах оптимізації сходження градієнтів. https://towardsdatascience.com/types-of-optimization-algorithms-used-in-neural-networks-and-ways-to-optimize-gradient-95ae5d39529f [ 2020-01-18 у Wayback Machine.]
- 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
- Ye.Y. Алгоритми оптимізації нульового порядку та першого порядку І. https://web.stanford.edu/class/msande311/lecture10.pdf
- Manson, L.; Baxter, J.; Bartlett. P. & Fream, M. Boosting algorithms as gradient descent.
Література
- Варіаційне числення та методи оптимізації: підручник / О. М. Піддубний, Ю. І. Харкевич ; Східноєвроп. нац. ун-т ім. Лесі Українки. — Луцьк: Гадяк Ж. В., 2015. — 331 с. — (Посібники та підручники СНУ ім. Лесі Українки). — . — (серія)
- Дослідження операцій і методи оптимізації: навч. посібник для студ. вищ. навч. закладів / М. Є. Корольов [та ін.] ; Відкритий міжнародний ун-т розвитку людини «Україна». — К. : Університет «Україна», 2007. — 177 с. —
- Задачі, методи та алгоритми оптимізації: навч. посіб. для студ. вищ. навч. закл. / І. В. Бейко, П. М. Зінько, О. Г. Наконечний ; Київ. нац. ун-т ім. Тараса Шевченка. — 2-ге вид., переробл. — К. : Київ. ун-т, 2012. — 799 с. — Бібліогр.: с. 769—779. —
- Комп'ютерна реалізація методів оптимізації: навч. посіб. для студ. та асп. фіз.-мат., інж. та екон. спец. / В. О. Любчак, Л. Г. Острівна ; Сумський держ. ун-т. — Суми: Видавництво Сумського держ. ун-ту, 2002. — 161 с.: рис. —
- Математичні методи оптимізації: навч. посіб. / М. І. Горбійчук ; Івано-Франків. нац. техн. ун-т нафти і газу. — Івано-Франківськ: ІФНТУНГ, 2018. — 302 с. : рис., табл. —
- Математичні методи оптимізації: навч. посіб. / О. К. Молодід ; Нац. техн. ун-т України «Київ. політехн. ін-т». — К. : НТУУ «КПІ», 2012. — 204 с. : рис., табл.
- Методи оптимізації: алгоритми, приклади, задачі: навч. посіб. для студ. усіх спец. напряму підгот. «Комп'ютерні науки» / Г. А. Гайна ; Київський національний ун-т будівництва і архітектури. — К. : КНУБА, 2005. — 144 с.
- Методи оптимізації: навч. посіб. до проведення лаб. і практ. робіт / О. В. Карташов, А. В. Бабкіна, Н. Ю. Ємцева, Р. А. Пудло ; Нац. аерокосм. ун-т ім. М. Є. Жуковського «Харк. авіац. ін-т». — Х. : ХАІ, 2009. — 111 с.
- Методи оптимізації складних систем: навч. посіб. для студ. спец. «Комп'ютеризовані системи управління і автоматики» / І. В. Кузьмін [та ін.] ; Вінницький держ. технічний ун-т. — Вінниця: ВДТУ, 2003. — 165 с.: рис.
- Методи оптимізації та дослідження операцій [Текст]: навч. посіб. / П. М. Мартинюк, О. Р. Мічута ; Нац. ун-т вод. госп-ва та природокористування. — Рівне: НУВГП, 2011. — 283 с.
- Оптимізаційні методи та моделі: підручник / В. С. Григорків, М. В. Григорків ; Чернів. нац. ун-т ім. Юрія Федьковича. — Чернівці: Рута, 2016. — 400 с. : рис., табл. —
- Основи теорії і методів оптимізації: навч. посібник для студ. мат. спец. вищих навч. закл. / М. І. Жалдак, Ю. В. Триус. — Черкаси: Брама-Україна, 2005. — 608 с.: рис. —
- Теорія оптимізації: навч. посіб. для студентів ВНЗ / О. І. Щепотьєв, А. В. Жильцов. — Київ: Компринт, 2017. — 241 с. : рис., табл. —
- Уханська О. М. Тексти лекцій з курсу «Методи оптимізації». — Львів: В-во НУ «ЛП», 2003. — 107 с.
- Худий М.І. Методи оптимізації. Лінійне програмування. — Львів, 1977.
- Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М. : Мир, 1985.
- Mathematical optimization methods: manual for higher educational institutions / V. Klymenko, O. Akmaldinova. — K. : NAU-druk, 2009. — 196 p. : fig., tab. —
- Methods and models of optimization: work book: an educational book / G. G. Shvachich [et al.] ; Alfred Nobel univ., Dnipropetrovs'k. — Dnipropetrovs'k: Alfred Nobel univ., Dnipropetrovs'k, 2012. — 120 p. : fig., tab. —
- Optimization theory / H. T. Jongen [та ін.]. — Boston[etc.]: Kluwer academic publishers, 2004. — XI, 443 p.: fig. — Бібліогр.: p. 429—443. —
В іншому мовному розділі є повніша стаття Mathematical optimization(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою з англійської.
|
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U Vikipediyi ye statti pro inshi znachennya cogo termina optimizaciya Matematichnoyu optimizaciyeyu inkoli optimizaciyeyu abo matematichnim programuvannyam v matematici informatici ta doslidzhenni operacij nazivayut vidbir najkrashogo elementu za pevnim kriteriyem z mnozhini dostupnih alternativ Grafik paraboloyidu zadanogo rivnyannyam z f x y x y 4 Globalnij maksimum v tochci x y z 0 0 4 poznacheno sinoyu tochkoyu Poshuk minimumu funkciyi Simionesku metodom Neldera Mida Simpleks vershini vporyadkovani za velichinoyu z najmenshim najkrashim znachennyam 1 U najprostishomu vipadku zadacha optimizaciyi polyagaye u znahodzhenni ekstremumu minimumu abo maksimumu dijsnoyi funkciyi shlyahom sistematichnogo viboru vhidnih znachen z dozvolenogo naboru ta obchislennya znachennya funkciyi Podalshi uzagalnennya teoriyi ta metodiv optimizaciyi do inshih formulyuvan stanovlyat veliku oblast prikladnoyi matematiki Vzagali optimizaciya ohoplyuye znahodzhennya najkrashih mozhlivih znachen deyakoyi cilovoyi funkciyi v mezhah oblasti viznachennya vklyuchayuchi rizni tipi cilovih funkcij ta rizni tipi oblastej znachennya Postanovka zadachi optimizaciyiDokladnishe Zadacha optimizaciyi U procesi proyektuvannya stavitsya zvichajno zadacha viznachennya najkrashih u deyakomu znachenni strukturi abo znachennya parametriv ob yektiv Taka zadacha nazivayetsya optimizacijnoyu Yaksho optimizaciya pov yazana z rozrahunkom optimalnih znachen parametriv pri zadanij strukturi ob yekta to vona nazivayetsya parametrichnoyu Zadacha viboru optimalnoyi strukturi ye strukturnoyu optimizaciyeyu Standartna matematichna zadacha optimizaciyi formulyuyetsya v takij sposib Sered elementiv x sho utvoryuyut mnozhinu X znajti takij element x sho nadaye minimalne znachennya f x zadanij funkciyi f x Dlya togo shob korektno postaviti zadachu optimizaciyi neobhidno zadati Dopustimu mnozhinu mnozhinu X x g i x 0 i 1 m R n displaystyle mathbb X vec x g i vec x leq 0 i 1 ldots m subset mathbb R n funkciyi g i displaystyle g i zadayut obmezhennya na X displaystyle mathbb X Cilovu funkciyu vidobrazhennya f X R displaystyle f colon mathbb X to mathbb R Kriterij poshuku max abo min Todi virishiti zadachu f x min x X displaystyle f x to min vec x in mathrm X pri poshuku maksimumu bude analogichne viznachennya oznachaye odne z Pokazati sho X displaystyle mathbb X varnothing Pokazati sho cilova funkciya f x displaystyle f vec x ne obmezhena znizu Znajti x X f x min x X f x displaystyle vec x in mathbb X f vec x min vec x in mathbb X f vec x Yaksho x displaystyle nexists vec x to znajti inf x X f x displaystyle inf vec x in mathbb X f vec x Yaksho minimizovana funkciya ne ye opukloyu to chasto obmezhuyutsya poshukom lokalnih minimumiv i maksimumiv tochok x 0 displaystyle x 0 takih sho vsyudi v deyakomu yihnomu okoli f x f x 0 displaystyle f x geq f x 0 dlya minimumu j f x f x 0 displaystyle f x leq f x 0 dlya maksimumu Yaksho dopustima mnozhina X R n displaystyle mathbb X mathbb R n to taka zadacha nazivayetsya zadacheyu bezumovnoyi optimizaciyi v inshomu razi zadacheyu umovnoyi optimizaciyi Funkciyu f v riznih galuzyah nazivayut po riznomu cilovoyu funkciyeyu angl objective function funkciyeyu vtrat angl loss function chi funkciyeyu vitrat angl cost function pri minimizaciyi abo funkciyeyu korisnosti angl utility function chi funkciyeyu dopasovanosti angl fitness function maksimizaciya funkciyeyu energiyi angl energy function abo funkcionalom energiyi angl energy functional NotaciyaZadacha optimizaciyi chasto zapisuyetsya u svoyeridnij specialnij notaciyi Os deyaki prikladi Minimalne i maksimalne znachennya funkciyi Rozglyanemo nastupnij zapis min x R x 2 1 displaystyle min x in mathbb R x 2 1 Vin poznachaye minimalne znachennya cilovoyi funkciyi x 2 1 displaystyle x 2 1 yaksho x obirayetsya iz mnozhini dijsnih chisel R displaystyle mathbb R Minimalne znachennya v takomu vipadku dorivnyuye 1 displaystyle 1 sho vidpovidaye znachennyu x 0 displaystyle x 0 Analogichno notaciya max x R 2 x displaystyle max x in mathbb R 2x zapituye maksimalne znachennya cilovoyi funkciyi 2x de x mozhe buti bud yakim dijsnim chislom V danomu vipadku ne isnuye takogo maksimumu oskilki cilova funkciya neobmezhena tozh vidpovid bude neskinchennistyu abo neviznachena Optimalni vhidni argumenti Dokladnishe Argumenti maksimizaciyi ta minimizaciyi Rozglyanemo nastupnij priklad a r g m i n x 1 x 2 1 displaystyle underset x in infty 1 operatorname arg min x 2 1 abo ekvivalentno a r g m i n x x 2 1 koli x 1 displaystyle underset x operatorname arg min x 2 1 text koli x in infty 1 Takij zapis predstavlyaye znachennya abo dekilka znachen argumentu x displaystyle x v intervali 1 displaystyle infty 1 sho minimizuye cilovu funkciyu x 2 1 displaystyle x 2 1 poshuk faktichnogo znachennya minimumu funkciyi v cij zadachi ne vimagayetsya V danomu vipadku vidpovid stanovit x 1 displaystyle x 1 oskilki x 0 displaystyle x 0 ne pidhodit bo ne nalezhit zadanomu intervalu Analogichno a r g m a x x 5 5 y R x cos y displaystyle underset x in 5 5 y in mathbb R operatorname arg max x cos y abo ekvivalentno a r g m a x x y x cos y koli x 5 5 y R displaystyle underset x y operatorname arg max x cos y text koli x in 5 5 y in mathbb R predstavlyaye paru x y displaystyle x y abo pari znachen yaka maksimizuye yaki maksimizuyut znachennya cilovoyi funkciyi x cos y displaystyle x cos y iz zadanimi obmezhennyami sho x displaystyle x znahoditsya v intervali 5 5 displaystyle 5 5 znovu zh taki faktichne maksimalne znachennya dlya virazu ne maye znachennya V comu vipadku rishennyami budut pari znachen nastupnoyi formi 5 2 k p displaystyle 5 2k pi ta 5 2 k 1 p displaystyle 5 2k 1 pi de k displaystyle k mozhe prijmati bud yake cile znachennya Operatori a r g m i n displaystyle operatorname arg min ta a r g m a x displaystyle operatorname arg max inodi zapisuyut yak argmin displaystyle operatorname argmin ta argmax displaystyle operatorname argmax sho rozumiyut yak argument dlya minimumu ta argument dlya maksimumu Klasifikaciya metodiv optimizaciyiMetodi optimizaciyi klasifikuyut vidpovidno do zadach optimizaciyi Lokalni metodi shodyatsya do yakogo nebud lokalnogo ekstremumu cilovoyi funkciyi U razi unimodalnoyi cilovoyi funkciyi cej ekstremum yedinij i bude globalnim maksimumom minimumom Globalni metodi mayut spravu z bagatoekstremalnimi cilovimi funkciyami Pri globalnomu poshuku osnovnoyu zadacheyu ye viyavlennya tendencij globalnoyi povedinki cilovoyi funkciyi Isnuyuchi v cej chas metodi poshuku mozhna rozbiti na tri veliki grupi determinovani vipadkovi stohastichni kombinovani Za kriteriyem vimirnosti dopustimoyi mnozhini metodi optimizaciyi podilyayut na metodi odnomirnoyi optimizaciyi i metodi bagatomirnoyi optimizaciyi Za vidom cilovoyi funkciyi j dopustimoyi mnozhini zadachi optimizaciyi j metodi yihnogo rozv yazannya mozhna rozdiliti na taki klasi Zadachi optimizaciyi u yakih cilova funkciya f x displaystyle f vec x i obmezhennya g i x i 1 m displaystyle g i vec x i 1 ldots m ye linijnimi funkciyami rozv yazuyutsya tak zvanimi metodami linijnogo programuvannya V inshomu razi mayut spravu iz zadacheyu nelinijnogo programuvannya i zastosovuyut vidpovidni metodi U svoyu chergu z nih vidilyayut dvi chastkovi zadachi yaksho f x displaystyle f vec x i g i x i 1 m displaystyle g i vec x i 1 ldots m opukli funkciyi to taku zadachu nazivayut zadacheyu opuklogo programuvannya yaksho X Z displaystyle mathbb X subset mathbb Z to mayut spravu iz zadacheyu cilochislovogo diskretnogo programuvannya Za vimogami do gladkosti j nayavnosti v cilovoyi funkciyi chastinnih pohidnih yih takozh mozhna rozdiliti na pryami metodi sho vimagayut tilki obchislen cilovoyi funkciyi v tochkah nablizhen metodi pershogo poryadku vimagayut obchislennya pershih chastinnih pohidnih funkciyi tobto yakobiana cilovoyi funkciyi metodi drugogo poryadku vimagayut obchislennya drugih chastinnih pohidnih tobto gessiana cilovoyi funkciyi Krim togo optimizacijni metodi podilyayutsya na taki grupi analitichni metodi napriklad metod mnozhnikiv Lagranzha i umovi Karusha Kuna Takera chiselni metodi Zalezhno vid prirodi mnozhini X zadachi matematichnogo programuvannya klasifikuyutsya tak zadachi diskretnogo programuvannya abo kombinatornoyi optimizaciyi yaksho X skinchenna abo zlichenna zadachi cilochislovogo programuvannya yaksho X ye pidmnozhinoyu mnozhini cilih chisel zadachi nelinijnogo programuvannya yaksho obmezhennya abo cilova funkciya mistyat nelinijni funkciyi i X ye pidmnozhinoyu skinchennovimirnogo vektornogo prostoru Yaksho zh usi obmezhennya i cilova funkciya mistyat lishe linijni funkciyi to ce zadacha linijnogo programuvannya Krim togo rozdilami matematichnogo programuvannya ye parametrichne programuvannya dinamichne programuvannya i stohastichne programuvannya Matematichne programuvannya vikoristovuyetsya pri rozv yazanni optimizacijnih zadach doslidzhennya operacij Sposib znahodzhennya ekstremumu povnistyu obumovlyuyetsya klasom zadachi Ale pered tim yak otrimati matematichnu model potribno vikonati 4 etapi modelyuvannya Viznachennya mezh sistemi optimizaciyi Vidkidayemo ti zv yazki ob yekta optimizaciyi iz zovnishnim svitom yaki ne mozhut silno vplinuti na rezultat optimizaciyi a tochnishe ti bez yakih rozv yazannya sproshuyetsya Vibir zminnih proyektuvannya kerovanih zminnih Zamorozhuyemo znachennya deyakih zminnih nekerovani zminni Inshi zalishayemo prijmati bud yaki znachennya z oblasti dopustimih rishen kerovani zminni Viznachennya obmezhen na kerovani zminni rivnosti j abo nerivnosti Vibir chislovogo kriteriyu optimizaciyi Stvoryuyemo cilovu funkciyuIstoriyaZadachi linijnogo programuvannya buli pershimi dokladno vivchenimi zadachami poshuku ekstremuma funkcij pri nayavnosti obmezhen tipu nerivnostej V 1820 r Zh Fur ye i potim v 1947 r Dzh Dancig zaproponuvav metod napravlenogo pereboru sumizhnih vershin u napryamku zrostannya cilovoyi funkciyi simpleks metod sho stav osnovnim pri rozv yazanni zadach linijnogo programuvannya Prisutnist u nazvi disciplini termina programuvannya poyasnyuyetsya tim sho pershi doslidzhennya j pershi zastosuvannya linijnih optimizacijnih zadach buli v sferi ekonomiki tomu sho v anglijskij movi slovo programming oznachaye planuvannya skladannya planiv abo program Cilkom prirodno sho terminologiya vidobrazhaye tisnij zv yazok sho isnuye mizh matematichnoyu postanovkoyu zadachi i yiyi ekonomichnoyu interpretaciyeyu vivchennya optimalnoyi ekonomichnoyi programi Termin linijne programuvannya buv zaproponovanij Dzh Dancigom v 1949 roci dlya vivchennya teoretichnih i algoritmichnih zadach pov yazanih z optimizaciyeyu linijnih funkcij pri linijnih obmezhennyah Tomu najmenuvannya Matematichne programuvannya pov yazane z tim sho metoyu rozv yazannya zadach ye vibir optimalnoyi programi dij Vidilennya klasu ekstremalnih zadach obumovlenih linijnim funkcionalom na mnozhini sho zadayetsya linijnimi obmezhennyami varto vidnesti do 30 h rokiv XX storichchya Odnimi z pershih sho doslidzhuvali v zagalnij formi zadachi linijnogo programuvannya buli Dzhon fon Nejman znamenitij matematik i fizik sho doviv osnovnu teoremu pro matrichni igri j vivchiv ekonomichnu model sho nosit jogo im ya radyanskij akademik laureat nobelivskoyi premiyi 1975 r L V Kantorovich sho sformulyuvav ryad zadach linijnogo programuvannya j zaproponuvav 1939 r metod yihnogo rozv yazannya sho neznachno vidriznyayetsya vid simpleks metodu V 1931 r ugorskij matematik en rozglyanuv matematichnu postanovku j virishiv zadachu linijnogo programuvannya sho maye nazva problema viboru metod rozv yazannya oderzhav nazvu ugorskogo metodu L V Kantorovichem razom iz M K Gavurinim v 1949 r rozrobleno ru sho zastosovuyetsya pri rozv yazanni transportnih zadach U nastupnih robotah L V Kantorovicha V S Nemchinova V V Novozhilova A L Lur ye A Brudno ru D B Yudina E G Golshtejna j inshih matematikiv i ekonomistiv otrimali podalshij rozvitok yak matematichna teoriya linijnogo i nelinijnogo programuvannya tak i zastosuvannya yiyi metodiv do doslidzhennya riznih ekonomichnih problem Metodam linijnogo programuvannya prisvyacheno bagato robit zarubizhnih uchenih V 1941 r en postaviv transportnu zadachu Osnovnij metod rozv yazannya zadach linijnogo programuvannya simpleks metod buv opublikovanij v 1949 r Dzh Dancigom Podalshij rozvitok metodi linijnogo i nelinijnogo programuvannya otrimali v robotah en en Gass S I Charnes A E M Bila Beale E M ta inshih Odnochasno z rozvitkom linijnogo programuvannya velika uvaga pridilyalasya zadacham nelinijnogo programuvannya u yakih abo cilova funkciya abo obmezhennya abo te j te nelinijni V 1951 r bula opublikovana robota Kuna j Takkera u yakij navedeni neobhidni j dostatni umovi optimalnosti dlya rozv yazannya zadach nelinijnogo programuvannya Cya robota posluzhila osnovoyu dlya nastupnih doslidzhen u cij galuzi Pochinayuchi z 1955 r opublikovano bagato robit z kvadratichnogo programuvannya roboti Bila Barankin E i Dorfmana Dorfman R en en G Markovica ta inshih U robotah Dennis J B Rosen J B i Zontendijk G rozrobleno gradiyentni metodi rozv yazannya zadach nelinijnogo programuvannya U danij chas dlya efektivnogo zastosuvannya metodiv matematichnogo programuvannya j rozv yazannya zadach na komp yuterah rozrobleni movi algebrayichnogo modelyuvannya predstavnikami yakimi ye AMPL i Obchislyuvalni metodi optimizaciyiDlya rozv yazannya zadach doslidniki mozhut vikoristovuvati algoritmi yaki zupinyayutsya za skinchennu kilkist krokiv abo iteracijni metodi yaki zbigayutsya do rishennya na pevnomu klasi zadach abo evristiki yaki mozhut nadati priblizni rishennya deyakih zadach hocha yihni iteraciyi ne obov yazkovo budut shoditis Algoritmi optimizaciyi Div takozh Spisok algoritmiv Algoritmi optimizaciyi Simpleks metod Dzhordzha Danciga stvorenij dlya linijnogo programuvannya Rozshirennya simpleksnogo metodu stvorene dlya kvadratichnogo programuvannya i dlya drobovo linijnogo programuvannya Varianti simpleks metodu yaki osoblivo pasuyut u vipadku optimizaciyi merezhi Kombinatorni algoritmi Algoritmi kvantovoyi optimizaciyi Algoritm optimizaciyi mashinnogo navchannya Algoritm optimizaciyi mashinnogo navchannya vikonuyetsya iteracijnim shlyahom porivnyannya riznih rishen do dosyagnennya optimalnogo abo zadovilnogo rishennya Algoritmi optimizaciyi dopomagayut minimizuvati abo maksimizuvati cilovu funkciyu E x yaka ye prosto matematichnoyu funkciyeyu zalezhnoyu vid vnutrishnih parametriv modeli sho vikoristovuyutsya v modeli pri obchislenni cilovih znachen Y po mnozhini prediktoriv X Isnuyut dva tipi algoritmiv optimizaciyi yaki shiroko vikoristovuyutsya ce algoritmi nulovogo poryadku algoritmi optimizaciyi pershogo poryadku ta algoritmi optimizaciyi drugogo poryadku Algoritmi nulovogo poryadku Algoritmi nulovogo poryadku abo bez pohidnih vikoristovuyut lishe znachennya kriteriyu na deyakih poziciyah Ce populyarnij metod koli informaciyu pro gradiyent i gessian skladno abo ne mozhlivo otrimati napriklad funkciyi ne vkazano yavno Algoritmi optimizaciyi pershogo poryadku Ci algoritmi minimizuyut abo maksimizuyut funkciyu vtrat E x za dopomogoyu znachennya gradiyenta obchislennogo po parametram Najbilsh shiroko vikoristovuvanim algoritmom optimizaciyi pershogo poryadku ye gradiyentnij spusk Pohidna pershogo poryadku vidobrazhaye yak zmenshuyetsya chi zbilshuyetsya funkciya v pevnij tochci Pohidni pershogo poryadku opisuyut pryamu dotichnu do tochki na poverhni pohibki Algoritmi optimizaciyi drugogo poryadku Metodi drugogo poryadku vikoristovuyut pohidnu drugogo poryadku yaka takozh nazivayetsya gessianom dlya minimizaciyi abo maksimizaciyi funkciyi vtrat Gessian ye matriceyu chastkovih pohidnih drugogo poryadku Oskilki obchislennya drugih pohidnih ye zatratnoyu diyeyu po kilkosti operacij tomu taki algoritmi ne mayut shirokogo vzhitku Pohidna drugogo poryadku povidomlyaye nam chi zbilshuyetsya abo zmenshuyetsya persha pohidna sho zagalom vkazuye na krivinu funkciyi Takozh gesian zadaye poverhnyu drugogo poryadku dotichnu do poverhni pohibki ta yaka maye taku samu krivinu Iteracijni metodi Dokladnishe Metod iteraciyi algoritm Div takozh Skinchenni riznici Teoriya nablizhen ta Chiselni metodi Iteracijni metodi sho vikoristovuyutsya dlya virishennya zavdan nelinijnogo programuvannya rozriznyayutsya zalezhno vid togo chi ocinyuyut voni gessian gradiyent abo tilki znachennya funkcij Pri ocinci gessianu H i gradiyentu G pokrashuyetsya shvidkist zbizhnosti dlya funkcij dlya yakih ci velichini isnuyut i zminyuyutsya dosit gladko vikoristannya cih ocinok zbilshuye obchislyuvalnu skladnist abo obchislyuvalnu vartist kozhnoyi iteraciyi U deyakih vipadkah obchislyuvalna skladnist mozhe buti zanadto visokoyu Odnim z osnovnih kriteriyiv dlya optimizatoriv ye prosto kilkist neobhidnih ocinok funkcij oskilki ce chasto potrebuye nabagato bilshe obchislen nizh potribno samomu optimizatoru yakij zdebilshogo musit operuvati nad N zminnimi Pohidni nadayut detalnu informaciyu dlya optimizatoriv ale yih i vazhche obchisliti napriklad aproksimaciya gradiyenta potrebuye prinajmni N 1 ocinku funkcij Dlya nablizhen 2 h pohidnih voni znahodyatsya u matrici Gesse chislo ocinok funkcij bude poryadku N Metod Nyutona vimagaye pohidnih 2 go poryadku tomu dlya kozhnoyi iteraciyi kilkist viklikiv funkcij maye poryadok N ale dlya bilsh prostogo chistogo gradiyentnogo optimizatora potribno lishe N Odnak optimizatori gradiyentiv potrebuyut zazvichaj bilshe iteracij nizh algoritm Nyutona Yaka z nih bude najkrashoyu za kilkostyu viklikiv funkcij zalezhit vid konkretnoyi zadachi Metodi yaki ocinyuyut gessian abo nablizhenij gessian cherez skinchenni riznici Metod Nyutona v optimizaciyi Poslidovne kvadratichne programuvannya metod na osnovi Nyutona dlya problem malogo ta serednogo masshtabu Deyaki versiyi mozhut vporatis z bagatovimirnimi problemami Metodi vnutrishnoyi tochki Ce velikij klas metodiv dlya umovnoyi optimizaciyi Deyaki metodi vnutrishnoyi tochki vikoristovuyut tilki informaciyu pro gradiyent a inshi vimagayut ocinki gessianiv Metodi yaki ocinyuyut gradiyent abo aproksimuyut znachennya gradiyentu abo navit subgradiyentu Metodi koordinatnogo spusku algoritmi yaki onovlyuyut odnu koordinatu za odnu iteraciyu Metod spryazhenih gradiyentiv iteracijni metodi dlya velikih zadach Teoretichno ci metodi zakinchuyutsya za kincevu kilkist krokiv z kvadratichnimi cilovimi funkciyami prote na praktici ne sposterigayetsya zupinka za kincevu kilkist krokiv na komp yuterah zi skinchennoyu tochnistyu Gradiyentnij spusk inkoli krutij spusk chi krutij pidjom povilnij metod z tochki zoru istorichnogo ta teoretichnogo interesu yakij nanovo viklikav interes do znahodzhennya nablizhenih rozv yazan velicheznih problem Subgradiyentni metodi iteracijnij metod dlya velikih lokalno lipshicevih funkcij z vikoristannyam uzagalnenih gradiyentiv Za Borisom T Polyakom subgradiyentno proyekcijni metodi shozhi z metodami spryazhenih gradiyentiv Metodi yaki ocinyuyut tilki znachennya funkcij Yaksho zadacha neperervno diferencijovna to gradiyenti mozhna aproksimuvati za dopomogoyu skinchennih riznic v takomu vipadku mozhna vikoristovuvati metod na osnovi gradiyenta Metodi interpolyaciyi Metodi poshuku shablonu yaki mayut krashi vlastivosti zbizhnosti nizh evristika Neldera Mida yaka navedena nizhche Div takozhAlgoritmi optimizaciyi Zadacha optimizaciyi Skladnist aproksimaciyi Algoritm Frank VulfaPrimitki The Nature of Mathematical Programming 2014 03 05 u Wayback Machine Mathematical Programming Glossary INFORMS Computing Society W Erwin Diewert 2008 cost functions The New Palgrave Dictionary of Economics 2nd Edition Contents Walia A 2017 Tipi algoritmiv optimizaciyi sho vikoristovuyutsya v nejronnih merezhah i sposobah optimizaciyi shodzhennya gradiyentiv https towardsdatascience com types of optimization algorithms used in neural networks and ways to optimize gradient 95ae5d39529f 2020 01 18 u Wayback Machine E Ruffio D Saury D Petit M Girault Algoritmi optimizaciyi nulovogo poryadku http www sft asso fr Local sft dir user 3775 documents actes Metti5 School Lectures amp Tutorials Texts Text T2 Ruffio pdf Ye Y Algoritmi optimizaciyi nulovogo poryadku ta pershogo poryadku I https web stanford edu class msande311 lecture10 pdf Manson L Baxter J Bartlett P amp Fream M Boosting algorithms as gradient descent LiteraturaVariacijne chislennya ta metodi optimizaciyi pidruchnik O M Piddubnij Yu I Harkevich Shidnoyevrop nac un t im Lesi Ukrayinki Luck Gadyak Zh V 2015 331 s Posibniki ta pidruchniki SNU im Lesi Ukrayinki ISBN 978 617 7129 36 2 ISBN 978 966 600 5 seriya Doslidzhennya operacij i metodi optimizaciyi navch posibnik dlya stud vish navch zakladiv M Ye Korolov ta in Vidkritij mizhnarodnij un t rozvitku lyudini Ukrayina K Universitet Ukrayina 2007 177 s ISBN 978 966 388 182 9 Zadachi metodi ta algoritmi optimizaciyi navch posib dlya stud vish navch zakl I V Bejko P M Zinko O G Nakonechnij Kiyiv nac un t im Tarasa Shevchenka 2 ge vid pererobl K Kiyiv un t 2012 799 s Bibliogr s 769 779 ISBN 978 966 439 564 6 Komp yuterna realizaciya metodiv optimizaciyi navch posib dlya stud ta asp fiz mat inzh ta ekon spec V O Lyubchak L G Ostrivna Sumskij derzh un t Sumi Vidavnictvo Sumskogo derzh un tu 2002 161 s ris ISBN 966 7668 11 8 Matematichni metodi optimizaciyi navch posib M I Gorbijchuk Ivano Frankiv nac tehn un t nafti i gazu Ivano Frankivsk IFNTUNG 2018 302 s ris tabl ISBN 978 966 694 295 4 Matematichni metodi optimizaciyi navch posib O K Molodid Nac tehn un t Ukrayini Kiyiv politehn in t K NTUU KPI 2012 204 s ris tabl Metodi optimizaciyi algoritmi prikladi zadachi navch posib dlya stud usih spec napryamu pidgot Komp yuterni nauki G A Gajna Kiyivskij nacionalnij un t budivnictva i arhitekturi K KNUBA 2005 144 s Metodi optimizaciyi navch posib do provedennya lab i prakt robit O V Kartashov A V Babkina N Yu Yemceva R A Pudlo Nac aerokosm un t im M Ye Zhukovskogo Hark aviac in t H HAI 2009 111 s Metodi optimizaciyi skladnih sistem navch posib dlya stud spec Komp yuterizovani sistemi upravlinnya i avtomatiki I V Kuzmin ta in Vinnickij derzh tehnichnij un t Vinnicya VDTU 2003 165 s ris Metodi optimizaciyi ta doslidzhennya operacij Tekst navch posib P M Martinyuk O R Michuta Nac un t vod gosp va ta prirodokoristuvannya Rivne NUVGP 2011 283 s Optimizacijni metodi ta modeli pidruchnik V S Grigorkiv M V Grigorkiv Cherniv nac un t im Yuriya Fedkovicha Chernivci Ruta 2016 400 s ris tabl ISBN 978 966 423 364 1 Osnovi teoriyi i metodiv optimizaciyi navch posibnik dlya stud mat spec vishih navch zakl M I Zhaldak Yu V Trius Cherkasi Brama Ukrayina 2005 608 s ris ISBN 966 8756 04 5 Teoriya optimizaciyi navch posib dlya studentiv VNZ O I Shepotyev A V Zhilcov Kiyiv Komprint 2017 241 s ris tabl ISBN 978 966 929 586 6 Uhanska O M Teksti lekcij z kursu Metodi optimizaciyi Lviv V vo NU LP 2003 107 s Hudij M I Metodi optimizaciyi Linijne programuvannya Lviv 1977 Gill F Myurrej U Rajt M Prakticheskaya optimizaciya Per s angl M Mir 1985 Mathematical optimization methods manual for higher educational institutions V Klymenko O Akmaldinova K NAU druk 2009 196 p fig tab 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 Dnipropetrovs k Alfred Nobel univ Dnipropetrovs k 2012 120 p fig tab ISBN 978 966 434 125 4 Optimization theory H T Jongen ta in Boston etc Kluwer academic publishers 2004 XI 443 p fig Bibliogr p 429 443 ISBN 1 4020 8098 0 V inshomu movnomu rozdili ye povnisha stattya Mathematical optimization angl Vi mozhete dopomogti rozshirivshi potochnu stattyu za dopomogoyu perekladu z anglijskoyi Divitis avtoperekladenu versiyu statti z movi anglijska Perekladach povinen rozumiti sho vidpovidalnist za kincevij vmist statti u Vikipediyi nese same avtor redaguvan Onlajn pereklad nadayetsya lishe yak korisnij instrument pereglyadu vmistu zrozumiloyu movoyu Ne vikoristovujte nevichitanij i nevidkorigovanij mashinnij pereklad u stattyah ukrayinskoyi Vikipediyi Mashinnij pereklad Google ye korisnoyu vidpravnoyu tochkoyu dlya perekladu ale perekladacham neobhidno vipravlyati pomilki ta pidtverdzhuvati tochnist perekladu a ne prosto skopiyuvati mashinnij pereklad do ukrayinskoyi Vikipediyi Ne perekladajte tekst yakij vidayetsya nedostovirnim abo neyakisnim Yaksho mozhlivo perevirte tekst za posilannyami podanimi v inshomovnij statti Dokladni rekomendaciyi div Vikipediya Pereklad Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi