Оптимізація (математика)

Математичною оптимізацією (інколи, оптимізацією) або математичним програмуванням в математиці, інформатиці та дослідженні операцій називають відбір найкращого елементу (за певним критерієм) з множини доступних альтернатив.^[1]

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

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

Стандартна математична задача оптимізації формулюється в такий спосіб. Серед елементів χ, що утворюють множину Χ, знайти такий елемент χ^*, що надає мінімальне значення f(χ^*) заданій функції f(χ). Для того щоб коректно поставити задачу оптимізації необхідно задати:

1. Допустиму множину — множину ${\displaystyle \mathbb {X} =\{{\vec {x}}|\;g_{i}({\vec {x}})\leq 0,\;i=1,\ldots ,m\}\subset \mathbb {R} ^{n}}$ (функції ${\displaystyle g_{i}}$ задають обмеження на ${\displaystyle \mathbb {X} }$);
2. Цільову функцію — відображення ${\displaystyle f\colon \mathbb {X} \to \mathbb {R} }$;
3. Критерій пошуку (max або min).

Тоді вирішити задачу ${\displaystyle f(x)\to \min _{{\vec {x}}\in \mathrm {X} }}$ (при пошуку максимуму буде аналогічне визначення) означає одне з:

1. Показати, що ${\displaystyle \mathbb {X} =\varnothing }$.
2. Показати, що цільова функція ${\displaystyle f({\vec {x}})}$ не обмежена знизу.
3. Знайти ${\displaystyle {\vec {x}}^{*}\in \mathbb {X} :\;f({\vec {x}}^{*})=\min _{{\vec {x}}\in \mathbb {X} }f({\vec {x}})}$.
4. Якщо ${\displaystyle \nexists {\vec {x}}^{*}}$, то знайти ${\displaystyle \inf _{{\vec {x}}\in \mathbb {X} }f({\vec {x}})}$.

Якщо мінімізована функція не є опуклою, то часто обмежуються пошуком локальних мінімумів і максимумів: точок ${\displaystyle x_{0}}$ таких, що всюди в деякому їхньому околі ${\displaystyle f(x)\geq f(x_{0})}$ для мінімуму й ${\displaystyle f(x)\leq f(x_{0})}$ для максимуму.

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

Функцію f в різних галузях називають по різному, цільовою функцією (англ. objective function), функцією втрат (англ. loss function) чи функцією витрат (англ. cost function) (при мінімізації),^[2] або функцією корисності (англ. utility function) чи функцією допасованості (англ. fitness function) (максимізація), функцією енергії (англ. energy function) або функціоналом енергії (англ. energy functional).

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

Розглянемо наступний запис:

${\displaystyle \min _{x\in \mathbb {R} }\;(x^{2}+1)}$

Він позначає мінімальне значення цільової функції ${\displaystyle x^{2}+1}$, якщо x обирається із множини дійсних чисел ${\displaystyle \mathbb {R} }$. Мінімальне значення в такому випадку дорівнює ${\displaystyle 1}$, що відповідає значенню ${\displaystyle x=0}$.

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

${\displaystyle \max _{x\in \mathbb {R} }\;2x}$

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

Розглянемо наступний приклад:

${\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,}$

або еквівалентно

${\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{коли}}\;x\in (-\infty ,-1].}$

Такий запис представляє значення (або декілька значень) аргументу ${\displaystyle x}$ в інтервалі ${\displaystyle (-\infty ,-1]}$, що мінімізує цільову функцію ${\displaystyle x^{2}+1}$ (пошук фактичного значення мінімуму функції, в цій задачі не вимагається). В даному випадку, відповідь становить ${\displaystyle x=-1}$, оскільки ${\displaystyle x=0}$ не підходить, бо не належить заданому інтервалу.

Аналогічно,

${\displaystyle {\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos(y),}$

або еквівалентно

${\displaystyle {\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos(y),\;{\text{коли}}\;x\in [-5,5],\;y\in \mathbb {R} ,}$

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

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

Методи оптимізації класифікують відповідно до задач оптимізації:

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

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

1. детерміновані;
2. випадкові (стохастичні);
3. комбіновані.

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

За видом цільової функції й допустимої множини, задачі оптимізації й методи їхнього розв'язання можна розділити на такі класи:

• Задачі оптимізації, у яких цільова функція ${\displaystyle f({\vec {x}})}$ і обмеження ${\displaystyle g_{i}({\vec {x}}),\;i=1,\ldots ,m}$ є лінійними функціями, розв'язуються так званими методами лінійного програмування.
• В іншому разі мають справу із задачею нелінійного програмування і застосовують відповідні методи. У свою чергу з них виділяють дві часткові задачі:
  • якщо ${\displaystyle f({\vec {x}})}$ і ${\displaystyle g_{i}({\vec {x}}),\;i=1,\ldots ,m}$ — опуклі функції, то таку задачу називають задачею опуклого програмування;
  • якщо ${\displaystyle \mathbb {X} \subset \mathbb {Z} }$, то мають справу із задачею цілочислового (дискретного) програмування.

За вимогами до гладкості й наявності в цільової функції частинних похідних, їх також можна розділити на:

• прямі методи, що вимагають тільки обчислень цільової функції в точках наближень;
• методи першого порядку: вимагають обчислення перших частинних похідних функції, тобто якобіана цільової функції;
• методи другого порядку: вимагають обчислення других частинних похідних, тобто гессіана цільової функції.

Крім того, оптимізаційні методи поділяються на такі групи:

• аналітичні методи (наприклад, метод множників Лагранжа і умови Каруша-Куна-Такера);
• чисельні методи;
• графічні методи.

Залежно від природи множини 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 і LANGO.

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

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

Алгоритм оптимізації машинного навчання виконується ітераційним шляхом порівняння різних рішень до досягнення оптимального або задовільного рішення. Алгоритми оптимізації допомагають мінімізувати або максимізувати цільову функцію E(x), яка є просто математичною функцією, залежною від внутрішніх параметрів моделі, що використовуються в моделі при обчисленні цільових значень (Y) по множині предикторів (X). Існують два типи алгоритмів оптимізації, які широко використовуються, це алгоритми нульового порядку, алгоритми оптимізації першого порядку та алгоритми оптимізації другого порядку.^[3]

Алгоритми нульового порядку (або без похідних) використовують лише значення критерію на деяких позиціях. Це популярний метод, коли інформацію про градієнт і гессіан складно або не можливо отримати, наприклад, функції не вказано явно.^[4]

Ці алгоритми мінімізують або максимізують функцію втрат E(x) за допомогою значення градієнта обчисленного по параметрам. Найбільш широко використовуваним алгоритмом оптимізації першого порядку є градієнтний спуск. Похідна першого порядку відображає, як зменшується чи збільшується функція в певній точці. Похідні першого порядку описують пряму, дотичну до точки на поверхні похибки.^[5]

Методи другого порядку використовують похідну другого порядку, яка також називається гессіаном, для мінімізації або максимізації функції втрат. Гессіан є матрицею часткових похідних другого порядку. Оскільки, обчислення других похідних є затратною дією по кількості операцій, тому такі алгоритми не мають широкого вжитку. Похідна другого порядку повідомляє нам, чи збільшується або зменшується перша похідна, що загалом вказує на кривину функції. Також гесіан задає поверхню другого порядку, дотичну до поверхні похибки та яка має таку саму кривину.^[6]

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

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

• Методи, які оцінюють гессіан (або наближений гессіан через скінченні різниці):
  • Метод Ньютона в оптимізації
  • Послідовне квадратичне програмування: метод на основі Ньютона для проблем малого та середнього масштабу. Деякі версії можуть впоратись з багатовимірними проблемами.
  • Методи внутрішньої точки: Це великий клас методів для умовної оптимізації. Деякі методи внутрішньої точки використовують тільки інформацію про градієнт, а інші вимагають оцінки гессіанів.
• Методи, які оцінюють градієнт, або апроксимують значення градієнту (або навіть субградієнту):
  • Методи координатного спуску: алгоритми, які оновлюють одну координату за одну ітерацію
  • Метод спряжених градієнтів: ітераційні методи для великих задач. (Теоретично ці методи закінчуються за кінцеву кількість кроків з квадратичними цільовими функціями, проте на практиці не спостерігається зупинка за кінцеву кількість кроків на комп'ютерах зі скінченною точністю.)
  • Градієнтний спуск (інколи, «крутий спуск» чи «крутий підйом»): (повільний) метод з точки зору історичного та теоретичного інтересу, який наново викликав інтерес до знаходження наближених розв'язань величезних проблем.
  • Субградієнтні методи — ітераційний метод для великих локально ліпшицевих функцій з використанням узагальнених градієнтів . За Борисом Т. Поляком, субградієнтно-проєкційні методи схожі з методами спряжених градієнтів.
• Методи, які оцінюють тільки значення функцій: Якщо задача неперервно диференційовна, то градієнти можна апроксимувати за допомогою скінченних різниць, в такому випадку можна використовувати метод на основі градієнта.
  • Методи інтерполяції.
  • Методи пошуку шаблону, які мають кращі властивості збіжності, ніж евристика Нелдера — Міда, яка наведена нижче.

• Алгоритми оптимізації
• Задача оптимізації
• Складність апроксимації
• Алгоритм Франк — Вульфа
• Неперервна оптимізація
• Дискретна оптимізація

В іншому мовному розділі є повніша стаття Mathematical optimization(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. Дивитись автоперекладену версію статті з мови «англійська». Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії! Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії. Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті. Докладні рекомендації: див. Вікіпедія:Переклад.

Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її.