Что такое глобальная оптимизация?

Локальный по сравнению с глобальными оптимумами

Оптимизация является процессом нахождения точки, которая минимизирует функцию. Более в частности:

Минимум local функции является точкой, где значение функции меньше, чем или равно значению в соседних точках, но возможно больше, чем в удаленной точке.
Минимум global является точкой, где значение функции меньше, чем или равно значению во всех других допустимых точках.

Обычно решатели Optimization Toolbox™ находят локальный оптимум. (Этот локальный оптимум может быть глобальным оптимумом.) Они находят оптимум в basin of attraction отправной точки. Для получения дополнительной информации смотрите Бассейны Привлекательности.

Напротив, решатели Global Optimization Toolbox разработаны, чтобы перерыть больше чем один бассейн привлекательности. Они ищут в различных способах:

GlobalSearch и MultiStart генерируют много отправных точек. Они затем используют локальный решатель, чтобы найти optima в бассейнах привлекательности отправных точек.
ga использует набор отправных точек (названный генеральной совокупностью) и итеративно генерирует лучшие точки от генеральной совокупности. Пока начальная генеральная совокупность покрывает несколько бассейнов, ga может исследовать несколько бассейнов.
particleswarm, как ga, использует набор отправных точек. particleswarm может исследовать несколько бассейнов целиком из-за его разнообразного населения.
simulannealbnd выполняет случайный поиск. Обычно simulannealbnd принимает точку, если это лучше, чем предыдущая точка. simulannealbnd иногда принимает худшую точку в порядке достигнуть различного бассейна.
patternsearch смотрит на многие соседние точки прежде, чем принять один из них. Если некоторые соседние точки принадлежат различным бассейнам, patternsearch в сущности смотрит во многих бассейнах целиком.
surrogateopt начинается квазислучайной выборкой в границах, ища маленькое значение целевой функции. surrogateopt использует merit function, который, частично, дает настройку точкам, которые далеки от оцененных точек, который является попыткой достигнуть глобального решения. После того, как это не может улучшить текущую точку, сброс surrogateopt, вызвав его к выборке широко в границах снова. Сброс является другим способом, которым surrogateopt ищет глобальное решение.

Бассейны привлекательности

Если целевая функция, f (x) сглажен, вектор – ∇f (x) точки в направлении, где f (x) уменьшается наиболее быстро. Уравнение быстрейшего спуска, а именно,

$\frac{d}{d t} x (t) = - \nabla f (x (t)),$

приводит к пути x (t), который переходит к локальному минимуму, когда t становится большим. Обычно x начальных значений (0), которые являются друг близко к другу, дает пути к быстрейшему спуску, которые склоняются к той же минимальной точке. basin of attraction для быстрейшего спуска является набором продвижения начальных значений к тому же локальному минимуму.

Следующие данные показывают два одномерных минимума. Данные показывают различные бассейны привлекательности с различными стилями линии, и она показывает направления быстрейшего спуска со стрелками. Для этого и последующих фигур, черные точки представляют локальные минимумы. Каждый путь к быстрейшему спуску, запускающийся в точке x (0), переходит к черной точке в бассейне, содержащем x (0).

Следующие данные показывают, как пути к быстрейшему спуску могут быть более сложными в большем количестве размерностей.

Следующие данные показывают еще более сложные пути и бассейны привлекательности.

Ограничения могут разбить один бассейн привлекательности в несколько частей. Например, считайте минимизацию y подвергающийся:

y ≥ |x |
y ≥ 5 – 4 (x –2) ².

Данные показывают два бассейна привлекательности с конечными пунктами.

Код для генерации фигуры

Пути к быстрейшему спуску являются прямыми линиями вниз к ограничительным контурам. От ограничительных контуров пути к быстрейшему спуску перемещаются вниз вдоль контуров. Конечный пункт или (0,0) или (11/4,11/4), в зависимости от того, является ли начальный x - значение выше или ниже 2.

Документация