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

Глобальна оптимізація — це розділ прикладної математики та числового аналізу, який намагається знайти глобальні мінімуми або максимуми функції чи набору функцій на заданому наборі. Зазвичай це описується як проблема мінімізації, оскільки максимізація дійсної функції $g(x)$ еквівалентна мінімізації функції $f(x):=(-1)\cdot 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$ .

Додатки

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

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

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

Найуспішніші загальні методи:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Методологія аналізу поверхні відгуку

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

Дивіться також

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

Посилання

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

• 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. doi:10.1126/science.220.4598.671. ISSN 0036-8075. PMID 17813860. S2CID 205939.

Для реактивного пошуку:

• 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. doi:10.1209/epl/i2006-10058-0. ISSN 0295-5075.
• Hamacher, K.; Wenzel, W. (1 січня 1999). Scaling behavior of stochastic minimization algorithms in a perfect funnel landscape. Physical Review E. 59 (1): 938—941. arXiv:physics/9810035. Bibcode:1999PhRvE..59..938H. doi:10.1103/physreve.59.938. ISSN 1063-651X. S2CID 119096368.
• 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. arXiv:physics/9903008. Bibcode:1999PhRvL..82.3003W. doi:10.1103/physrevlett.82.3003. ISSN 0031-9007. S2CID 5113626.

Для параллельного отпуска:

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

• 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. doi:10.1016/j.physa.2005.02.028. ISSN 0378-4371.

Для стратегій, що дозволяють порівняти детермінований і стохастичний методи глобальної оптимізації.

Зовнішні посилання

• A. Neumaier про глобальну оптимізацію
• Вступ до глобальної оптимізації Л. Ліберті
• Eлектронна книга Томаса Вайзе