Введение
Глобальная оптимизация — это раздел прикладной математики и численного анализа, который направлен на поиск глобальных минимумов или максимумов функции или набора функций на заданном множестве. Обычно это рассматривается как задача минимизации, поскольку максимизация вещественнозначной функции эквивалентна минимизации её отрицания. Для возможной нелинейной и невыпуклой непрерывной функции с глобальными минимумами и множеством всех глобальных минимизаторов в , стандартная задача минимизации может быть сформулирована следующим образом:
Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real valued function is equivalent to the minimization of the function
Given a possibly nonlinear and non convex continuous function with the global minima and the set of all global minimizers in , the standard minimization problem can be given as
that is, finding and a global minimizer in ; where is a (not necessarily convex) compact set defined by inequalities
Global optimization is distinguished from local optimization by its focus on finding the minimum or maximum over the given set, as opposed to finding local minima or maxima. Finding an arbitrary local minimum is relatively straightforward by using classical local optimization methods. Finding the global minimum of a function is far more difficult: analytical methods are frequently not applicable, and the use of numerical solution strategies often leads to very hard challenges.
то есть, поиск и глобального минимизатора в , где — компактное множество (не обязательно выпуклое), заданное неравенствами. Глобальная оптимизация отличается от локальной оптимизации тем, что фокусируется на поиске минимума или максимума по всему заданному множеству, а не только локальных минимумов или максимумов. Найти произвольный локальный минимум относительно просто, используя классические методы локальной оптимизации. Поиск глобального минимума функции гораздо сложнее: аналитические методы часто неприменимы, а применение стратегий численного решения часто сопряжено с серьезными трудностями.
Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real valued function is equivalent to the minimization of the function
Given a possibly nonlinear and non convex continuous function with the global minima and the set of all global minimizers in , the standard minimization problem can be given as
that is, finding and a global minimizer in ; where is a (not necessarily convex) compact set defined by inequalities
Global optimization is distinguished from local optimization by its focus on finding the minimum or maximum over the given set, as opposed to finding local minima or maxima. Finding an arbitrary local minimum is relatively straightforward by using classical local optimization methods. Finding the global minimum of a function is far more difficult: analytical methods are frequently not applicable, and the use of numerical solution strategies often leads to very hard challenges.
Внутреннее и внешнее приближение
В обеих этих стратегиях область, над которой оптимизируется функция, аппроксимируется многогранниками. При внутренней аппроксимации многогранники содержатся внутри области, а при внешней аппроксимации – охватывают область.
Методы резки плоскости
Метод секущих плоскостей — это общий термин для методов оптимизации, которые итеративно улучшают допустимое множество или целевую функцию посредством линейных неравенств, называемых секущими плоскостями. Эти процедуры широко используются для нахождения целочисленных решений задач смешанного целочисленного линейного программирования (MILP), а также для решения общих, не обязательно дифференцируемых, выпуклых задач оптимизации. Использование секущих плоскостей для решения MILP было предложено Ральфом Э. Гомори и Вацлавом Хваталом.
Разделительные и связанные методы
Branch and bound (BB или B&B) — это парадигма разработки алгоритмов для задач дискретной и комбинаторной оптимизации. Алгоритм ветвей и границ состоит из систематического перебора кандидатных решений посредством поиска в пространстве состояний: множество кандидатных решений представляется в виде корневого дерева, где корень содержит полное множество решений. Алгоритм исследует ветви этого дерева, представляющие подмножества множества решений. Прежде чем перебирать кандидатные решения для ветви, она проверяется на соответствие верхним и нижним оценочным границам оптимального решения и отбрасывается, если не может привести к лучшему решению, чем наилучшее, найденное алгоритмом на данный момент.
Интервальные методы
Интервальная арифметика, интервальная математика, интервальный анализ или интервальные вычисления – это метод, разработанный математиками начиная с 1950-х и 1960-х годов как способ установления границ для ошибок округления и погрешностей измерений в математических вычислениях, что позволяет разрабатывать численные методы, дающие достоверные результаты. Интервальная арифметика помогает находить надежные и гарантированные решения уравнений и задач оптимизации.
Методы, основанные на реальной алгебраической геометрии
Реальная алгебра — это часть алгебры, имеющая отношение к реальной алгебраической (и полуалгебраической) геометрии. Она в основном посвящена изучению упорядоченных полей и упорядоченных колец (в частности, реально замкнутых полей) и их применению к исследованию положительных многочленов и сумм квадратов многочленов. Её можно использовать в выпуклой оптимизации.
Прямая выборка в Монте-Карло
В этом методе для нахождения приближенного решения используются случайные моделирования. Пример: задача коммивояжера – это классическая задача оптимизации. То есть, все данные (расстояния между каждой точкой назначения), необходимые для определения оптимального маршрута, известны точно, и цель состоит в том, чтобы перебрать возможные варианты маршрутов и найти тот, который имеет наименьшее суммарное расстояние. Однако, предположим, что вместо минимизации общего расстояния, необходимого для посещения всех желаемых пунктов назначения, мы хотим минимизировать общее время, необходимое для достижения каждого пункта назначения. Это выходит за рамки классической оптимизации, поскольку время в пути по своей природе неопределенно (пробки, время суток и т.д.). Следовательно, для определения оптимального маршрута нам следует использовать имитационную оптимизацию, чтобы сначала оценить диапазон возможных времен, которые могут потребоваться для перемещения между двумя точками (в данном случае представленный распределением вероятностей, а не конкретным расстоянием), а затем оптимизировать наши решения о маршруте, учитывая эту неопределенность, чтобы выбрать наилучший путь.
Стохастическое туннелирование
Стохастическое туннелирование (STUN) — это метод глобальной оптимизации, основанный на использовании метода Монте-Карло для выборки функции, которую требуется минимизировать. Функция нелинейно преобразуется для облегчения перехода между областями, содержащими минимумы. Облегченный переход позволяет быстрее исследовать пространство поиска и быстрее сходиться к хорошему решению.
Параллельное закаливание
Параллельное отжигание, также известное как обмен репликами в методе Монте-Карло (MCMC), – это метод моделирования, направленный на улучшение динамических свойств симуляций методом Монте-Карло физических систем, и методов выборки цепей Маркова Монте-Карло (MCMC) в целом. Метод обмена репликами был первоначально разработан Свендсеном, затем расширен Гейером и впоследствии развит, в частности, Джорджио Паризи. Сугита и Окамото сформулировали версию параллельного отжигания на основе молекулярной динамики: она обычно известна как молекулярная динамика с обменом репликами или REMD. По сути, запускается N копий системы, случайно инициализированных, при различных температурах. Затем, на основе критерия Метрополиса, происходит обмен конфигурациями при разных температурах. Идея этого метода состоит в том, чтобы сделать конфигурации, полученные при высоких температурах, доступными для симуляций при низких температурах и наоборот. Это приводит к созданию устойчивого ансамбля, способного исследовать как низкоэнергетические, так и высокоэнергетические конфигурации. Таким образом, термодинамические свойства, такие как удельная теплоемкость, которые обычно плохо вычисляются в каноническом ансамбле, могут быть рассчитаны с высокой точностью.
Sugita and Okamoto formulated a molecular dynamics version of parallel tempering: this is usually known as replica exchange molecular dynamics or REMD. Essentially, one runs N copies of the system, randomly initialized, at different temperatures. Then, based on the Metropolis criterion one exchanges configurations at different temperatures. The idea of this method
is to make configurations at high temperatures available to the simulations at low temperatures and vice versa. This results in a very robust ensemble which is able to sample both low and high energy configurations. In this way, thermodynamical properties such as the specific heat, which is in general not well computed in the canonical ensemble, can be computed with great precision.