Глобальна оптимізація

Глобальна оптимізація — це розділ прикладної математики та числового аналізу, який намагається знайти глобальні мінімуми або максимуми функції або множини функцій на заданій множині. Зазвичай це описується як проблема мінімізації, оскільки максимізація дійсної функції $g(x)$ еквівалентна мінімізації функції $f(x):=-g(x)$.

Приклади екстремумів

Дано нелінійну та невипуклу неперервну функцію $f:\Omega \subset \mathbb {R} ^{n}\to \mathbb {R}$ з глобальними мінімумами $f^{*}$ і множина усіх глобальних мінімізаторів $X^{*}$ в $\Omega$, стандартну задачу мінімізації можна подати як

$\min _{x\in \Omega }f(x),$

тобто знаходження $f^{*}$ і глобальний мінімізатор в $X^{*}$; де $\Omega$ є (не обов'язково опуклою) компактною множиною, визначеною нерівностями $g_{i}(x)\geqslant 0,i=1,\ldots ,r$.

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

Загальна теорія

Сучасний підхід до проблеми глобальної оптимізації полягає в розподілі мінімумів. Далі продемонструємо зв'язок між будь-якою безперервною функцією $f$ на компактній множині $\Omega \subset \mathbb {R} ^{n}$ і її глобальними мінімумами $f^{*}$. Як типовий випадок, з цього випливає, що

$\lim _{k\to \infty }\int _{\Omega }f(x)m^{(k)}(x)\,\mathrm {d} x=f^{*},~~{\text{де}}~~m^{(k)}(x)={\frac {e^{-kf(x)}}{\int _{\Omega }e^{-kf(x)}\,\mathrm {d} x}};$

тим часом,

$\lim _{k\to \infty }m^{(k)}(x)=\left\{{\begin{array}{cl}{\frac {1}{\mu (X^{*})}},&x\in X^{*},\\0,&x\in \Omega -X^{*},\end{array}}\right.$

де $\mu (X^{*})$ — це $n$-вимірна міра Лебега множини мінімізаторів $X^{*}\in \Omega$. І якщо $f$ не є постійною на $\Omega$, монотонні нерівності

$\int _{\Omega }f(x)m^{(k)}(x)\,\mathrm {d} x>\int _{\Omega }f(x)m^{(k+\Delta k)}(x)\,\mathrm {d} x>f^{*}$

виконуються для всіх $k\in \mathbb {R}$ і $\Delta k>0$, що передбачає низку монотонних включень, і одним із них є, наприклад,

$\Omega \supset D_{f}^{(k)}\supset D_{f}^{(k+\Delta k)}\supset X^{*},{\text{ де }}D_{f}^{(k)}=\left\{x\in \Omega :f(x)\leqslant \int _{\Omega }f(t)m^{(k)}(t)\,\mathrm {d} t\right\}.$

Далі визначаємо розподіл мінімумів як слабку межу $m_{f,\Omega }$ таку, що тотожність

$\int _{\Omega }m_{f,\Omega }(x)\varphi (x)\,\mathrm {d} x=\lim _{k\to \infty }\int _{\Omega }m^{(k)}(x)\varphi (x)\,\mathrm {d} x$

виконується для кожної гладкої функції $\varphi$ з компактним носієм в $\Omega$. Ось дві безпосередні властивості $m_{f,\Omega }$:

1. $m_{f,\Omega }$ задовольняє тотожності $\int _{\Omega }m_{f,\Omega }(x)\,\mathrm {d} x=1$.
2. Якщо $f$ є неперервною на $\Omega$, то $f^{*}=\int _{\Omega }f(x)m_{f,\Omega }(x)\,\mathrm {d} x$.

Для порівняння, добре відомо, що зв'язок між будь-якою диференційованою опуклою функцією та її мінімумами строго встановлюється за допомогою градієнта. Якщо $f$ диференційована на опуклій множині $D$, то $f$ є опуклою тоді і тільки тоді, коли

$f(y)\geqslant f(x)+\nabla f(x)(y-x),~~\forall x,y\in D;$

таким чином, $\nabla f(x^{*})=0$ означає, що $f(y)\geqslant f(x^{*})$ виконується для всіх $y\in D$, тобто $x^{*}$ є глобальним мінімізатором $f$ на $D$.

Застосування

Типові приклади застосування глобальної оптимізації включають:

• Передбачення структури білка (мінімізація функції енергії/вільної енергії)
• Обчислювальна філогенетика (наприклад, мінімізація кількості перетворень символів у дереві)
• Задача комівояжера та побудова електричної схеми (мінімізація довжини шляху)
• Хімічна інженерія (наприклад, аналіз енергії Гіббса)
• Перевірка безпеки, техніка безпеки (наприклад, механічних конструкцій, будівель)
• Аналіз найгіршого випадку для алгоритмів
• Математичні задачі (наприклад, гіпотеза Кеплера)
• Задача пакування (розробки конфігурації) об'єктів
• Початковою точкою кількох симуляцій молекулярної динаміки є початкова оптимізація енергії системи, що моделюється
• Спінове скло
• Калібрування моделей розповсюдження радіохвиль і багатьох інших моделей у науці та техніці
• Допасовування кривої, як аналіз методу нелінійних найменших квадратів та інші узагальнення, які використовуються для допасовування параметрів моделі до експериментальних даних у хімії, фізиці, біології, економіці, фінансах, медицині, астрономії, інженерії
• Планування променевої терапії.

Детерміновані методи

Найуспішніші загальні точні стратегії:

Внутрішня і зовнішня апроксимація

В обох цих стратегіях множина, над якою функція повинна бути оптимізована, апроксимується многогранниками. У внутрішньому наближенні багатогранники містяться в множині, тоді як у зовнішньому наближенні багатогранники містять множину.

Методи січних площин

Метод січних площин — це загальний термін для методів оптимізації, які ітеративно уточнюють можливу множина або цільову функцію за допомогою лінійних нерівностей, які називаються перерізами. Такі процедури широко використовуються для пошуку цілочисельних розв'язків задач змішаного цілочисельного лінійного програмування, а також для вирішення загальних, не обов'язково диференційованих задач опуклої оптимізації. Використання січних площин для вирішення задач змішаного цілочисельного лінійного програмування було введено Ральфом Е. Гоморі та Вацлавом Хваталом.

Методи гілок і меж

Метод гілок і меж — це парадигма розробки алгоритму для задач дискретної та комбінаторної оптимізації. Алгоритм складається з систематичного перебору варіантів рішень за допомогою пошуку у просторі станів: множина можливих рішень утворює дерево, яке містить всі можливі розв'язки у корені. Алгоритм досліджує гілки цього дерева, які представляють підмножини множини рішень. Перед тим як розглядати можливі варіанти розв'язків гілки, виконують перевірку гілки на верхню та нижню оцінку оптимального розв'язку. Якщо перевірка показує, що гілка не може дати кращого розв'язку, ніж найкращий розв'язок, вже знайдений на поточний момент алгоритмом, то гілка пропускається.

Інтервальні методи

Інтервальна арифметика, інтервальна математика, інтервальний аналіз або інтервальне числення — це метод, розроблений математиками в 1960-х роках як підхід до встановлення обмежень на похибки округлення та вимірювання в математичних обчисленнях і, таким чином, для розробки чисельних методів, які дають надійні результати. Інтервальна арифметика допомагає знаходити надійні та гарантовані рішення рівнянь і задач оптимізації.

Методи, засновані на дійсній алгебричній геометрії

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

Стохастичні методи

Існує кілька точних або неточних алгоритмів на основі Монте-Карло:

Прямий вибірковий метод Монте-Карло

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

Приклад: задача комівояжера називається класичною задачею оптимізації. Тобто всі факти (відстані між кожною точкою призначення), необхідні для визначення оптимального шляху, відомі, і мета полягає в тому, щоб переглянути можливі варіанти подорожей, щоб знайти той, який має найменшу загальну відстань. Однак припустімо, що замість того, щоб мінімізувати загальну відстань, пройдену для відвідування кожного бажаного пункту призначення, ми хотіли мінімізувати загальний час, необхідний для досягнення кожного пункту призначення. Це виходить за рамки традиційної оптимізації, оскільки час у дорозі за своєю суттю є невизначеним (пробки, час доби, тощо). Як наслідок, щоб визначити наш оптимальний шлях, ми хотіли б використати симуляцію — оптимізацію, щоб спочатку зрозуміти діапазон потенційного часу, який може знадобитися для переходу від однієї точки до іншої (у цьому випадку представлений розподілом ймовірностей, а не конкретною відстанню), а потім оптимізувати наші рішення про подорожі, щоб визначити найкращий шлях, яким слід слідувати, враховуючи цю невизначеність.

Стохастичне тунелювання

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

Паралельний відпуск

Паралельний відпуск — це метод моделювання, спрямований на покращення динамічних властивостей моделювання фізичних систем методом Монте-Карло та методів Монте-Карло марковських ланцюгів (МКМЛ) загалом. Метод обміну копіями спочатку був розроблений Свендсеном, потім розширений Гейєром і пізніше розроблений Джорджіо Парізі. Сугіта та Окамото сформулювали молекулярно-динамічну версію паралельного відпуска — це зазвичай відомо як молекулярна динаміка обміну репліками.

По суті, запускається N копій системи, випадково ініціалізованих, при різних температурах. Потім на основі критерію Метрополіса відбувається обмін конфігураціями при різних температурах. Ідея цього методу полягає в тому, щоб зробити конфігурації при високих температурах доступними для моделювання при низьких температурах і навпаки. Це призводить до дуже надійного ансамблю, який здатний відбирати як низькоенергетичні, так і високоенергетичні конфігурації. Таким чином, такі термодинамічні властивості, як питома теплоємність, яка, як правило, погано обчислюється в канонічному ансамблі, можуть бути обчислені з високою точністю.

Евристика та метаевристика

Інші підходи включають евристичні стратегії пошуку в просторі пошуку більш-менш інтелектуальним способом, включаючи:

• Мурашиний алгоритм
• Імітація відпалу, загальна імовірнісна метаевристика
• Табу-пошук — розширення локального пошуку, здатне виходити з локальних мінімумів
• Еволюційні алгоритми (наприклад, генетичні алгоритми та еволюційні стратегії)
• Диференціальна еволюція — метод, який оптимізує проблему шляхом повторних спроб покращити простір пошуку з огляду на задану міру якості
• Алгоритми колективного інтелекту (наприклад, оптимізація роїв часток, бджолиний алгоритм, соціальна когнітивна оптимізація і оптимізація мурашиних колоній)
• Меметичні алгоритми, що поєднують глобальні та локальні стратегії пошуку
• Реактивний пошук (тобто інтеграція підсимвольних методів машинного навчання в евристику пошуку)
• Поступова оптимізація — метод, який для розв'язання складної задачі оптимізації спочатку розв'язує значно спрощену задачу та поступово перетворює цю задачу (під час оптимізації), поки вона не стане еквівалентною складній задачі оптимізації.

Підходи, засновані на методології поверхні відгуку

• Непряма оптимізація на основі самоорганізації
• Баєсова оптимізація, стратегія послідовного проектування для глобальної оптимізації функцій чорної скриньки з використанням байєсової статистики

Див. також

• Детермінована глобальна оптимізація
• Міжгалузеве оптимальне проєктування
• Багатокритеріальна оптимізація
• Оптимізація (математика)

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

Детермінована глобальна оптимізація:

• R. Horst, H. Tuy, Global Optimization: Deterministic Approaches, Springer, 1996.
• R. Horst, P.M. Pardalos and N.V. Thoai, Introduction to Global Optimization, Second Edition. Kluwer Academic Publishers, 2000.
• A.Neumaier, Complete Search in Continuous Global Optimization and Constraint Satisfaction, pp. 271—369 in: Acta Numerica 2004 (A. Iserles, ed.), Cambridge University Press 2004.
• M. Mongeau, H. Karsenty, V. Rouzé and J.-B. Hiriart-Urruty, Comparison of public-domain software for black box global optimization. Optimization Methods & Software 13(3), pp. 203–226, 2000.
• J.D. Pintér, Global Optimization in Action — Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications. Kluwer Academic Publishers, Dordrecht, 1996. Now distributed by Springer Science and Business Media, New York. This book also discusses stochastic global optimization methods.
• L. Jaulin, M. Kieffer, O. Didrit, E. Walter (2001). Applied Interval Analysis. Berlin: Springer.
• E.R. Hansen (1992), Global Optimization using Interval Analysis, Marcel Dekker, New York.

Моделювання відпалу:

• Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P. (13 травня 1983). Optimization by Simulated Annealing. Science (American Association for the Advancement of Science (AAAS)) 220 (4598): 671–680. Bibcode:1983Sci...220..671K. ISSN 0036-8075. PMID 17813860. doi:10.1126/science.220.4598.671. 

Реактивна пошукова оптимізація:

• Roberto Battiti, M. Brunato and F. Mascia, Reactive Search and Intelligent Optimization, Operations Research/Computer Science Interfaces Series, Vol. 45, Springer, November 2008. ISBN 978-0-387-09623-0

Стохастичних методи:

• A. Zhigljavsky. Theory of Global Random Search. Mathematics and its applications. Kluwer Academic Publishers. 1991.
• Hamacher, K (2006). Adaptation in stochastic tunneling global optimization of complex potential energy landscapes. Europhysics Letters (EPL) (IOP Publishing) 74 (6): 944–950. Bibcode:2006EL.....74..944H. ISSN 0295-5075. doi:10.1209/epl/i2006-10058-0. 
• Hamacher, K.; Wenzel, W. (1 січня 1999). Scaling behavior of stochastic minimization algorithms in a perfect funnel landscape. Physical Review E 59 (1): 938–941. Bibcode:1999PhRvE..59..938H. ISSN 1063-651X. arXiv:physics/9810035. doi:10.1103/physreve.59.938. 
• Wenzel, W.; Hamacher, K. (12 квітня 1999). Stochastic Tunneling Approach for Global Minimization of Complex Potential Energy Landscapes. Physical Review Letters (American Physical Society (APS)) 82 (15): 3003–3007. Bibcode:1999PhRvL..82.3003W. ISSN 0031-9007. arXiv:physics/9903008. doi:10.1103/physrevlett.82.3003. 

Паралельний відпуск:

• Hansmann, Ulrich H.E. (1997). Parallel tempering algorithm for conformational studies of biological molecules. Chemical Physics Letters (Elsevier BV) 281 (1–3): 140–150. Bibcode:1997CPL...281..140H. ISSN 0009-2614. arXiv:physics/9710041. doi:10.1016/s0009-2614(97)01198-6. 

Методи продовження:

• Zhijun Wu. The effective energy transformation scheme as a special continuation approach to global optimization with application to molecular conformation. Technical Report, Argonne National Lab., IL (United States), November 1996.

Загальні міркування щодо розмірності області визначення цільової функції:

• Hamacher, Kay (2005). On stochastic global optimization of one-dimensional functions. Physica A: Statistical Mechanics and Its Applications (Elsevier BV) 354: 547–557. Bibcode:2005PhyA..354..547H. ISSN 0378-4371. doi:10.1016/j.physa.2005.02.028. 

Посилання

• Сторінка А. Ноймаєра про глобальну оптимізацію
• Вступ до глобальної оптимізації Л. Ліберті
• Безкоштовна електронна книга Томаса Вайзе