Користувач:Valerii-kram/Глобальна оптимізація

Глобальна оптимізація — це розділ прикладної математики та числового аналізу, який намагається знайти глобальні мінімуми чи максимуми функції або набору функцій на заданому наборі. Зазвичай це описується як проблема мінімізації, оскільки максимізація дійсної функції $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^{*},~~{\textrm {where}}~~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{ where }}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. 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.

Посилання

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