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

Локальный и глобальный оптимумы

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

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

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

В отличие от этого, решатели Global Optimization Toolbox предназначены для поиска через несколько областей притяжения. Они ищут различными способами:

GlobalSearch и MultiStart сгенерировать ряд начальных точек. Затем они используют локальный решатель, чтобы найти оптимум в областях притяжения начальных точек.
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, подверженных:

<reservedrangesplaceholder1> ≥ | x |
<reservedrangesplaceholder1> ≥ 5 – 4 (x –2)².

Рисунок показывает две области притяжения с конечными точками.

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

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

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