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

Почему решатель не находит наименьший минимум

В общем случае решатели возвращают локальный минимум (или оптимум). Результатом может быть глобальный минимум (или оптимум), но этот результат не гарантируется.

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

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

Следующее является исключениями к этому общему правилу.

Задачи линейного программирования и положительные определенные проблемы квадратичного программирования выпуклы с выпуклыми выполнимыми областями, таким образом, у них есть только одна область притяжения. В зависимости от заданных опций, linprog игнорирует любую предоставленную пользователями начальную точку и quadprog не требует один, даже при том, что можно иногда ускорять минимизацию путем предоставления начальной точки.
Функции Global Optimization Toolbox, такие как simulannealbnd, попытайтесь искать больше чем одну область притяжения.

Поиск меньшего минимума

Если вам нужен глобальный минимум, необходимо найти начальное значение для решателя в области притяжения глобального минимума.

Можно установить начальные значения, чтобы искать глобальный минимум этими способами:

Используйте регулярную сетку начальных точек.
Используйте случайные точки, полученные из равномерного распределения, если все координаты задачи ограничены. Используйте точки, полученные из нормальных, экспоненциальных, или других случайных распределений, если некоторые компоненты неограниченны. Чем меньше вы знаете о местоположении глобального минимума, тем более распространено ваше случайное распределение должно быть. Например, нормальные распределения редко производят больше чем три стандартных отклонения далеко от их средних значений, но распределение Коши (плотность 1 / (π (1 + x ²))) делает значительно разрозненные выборки.
Используйте идентичные начальные точки с добавленными случайными возмущениями на каждой координате — ограниченный, нормальный, экспоненциальный, или другой.
Если у вас есть лицензия Global Optimization Toolbox, используйте GlobalSearch или MultiStart решатели. Эти решатели автоматически генерируют случайные стартовые точки внутри границ.

Чем больше вы знаете о возможных начальных точках, тем более сфокусирован и успешен ваш поиск будет.

Области притяжения

Если целевая функция, которой 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.

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