В общем случае решатели возвращают локальный минимум (или оптимум). Результатом может быть глобальный минимум (или оптимум), но этот результат не гарантирован.
Локальный минимум функции - это точка, где значение функции меньше, чем в соседних точках, но, возможно, больше, чем в удаленной точке.
Глобальный минимум - это точка, в которой значение функции меньше, чем во всех других возможных точках.
Вычислители Toolbox™ оптимизации обычно находят локальный минимум. (Этот локальный минимум может быть глобальным минимумом.) Они находят минимум в бассейне притяжения отправной точки. Дополнительные сведения о бассейнах притяжения см. в разделе Бассейны притяжения.
Ниже приведены исключения из этого общего правила.
Линейные задачи программирования и положительные определенные задачи квадратичного программирования являются выпуклыми, с выпуклыми выполнимыми областями, поэтому они имеют только один бассейн притяжения. В зависимости от заданных параметров, linprog игнорирует любую исходную точку, предоставленную пользователем, и quadprog не требует, хотя иногда можно ускорить минимизацию, указав начальную точку.
Функции инструментария глобальной оптимизации, такие как simulannealbnd, попытаться найти несколько бассейнов притяжения.
Если требуется глобальный минимум, необходимо найти начальное значение для решателя в бассейне притяжения глобального минимума.
Можно задать начальные значения для поиска глобального минимума следующими способами:
Используйте обычную сетку начальных точек.
Используйте случайные точки, полученные из равномерного распределения, если все координаты задачи ограничены. Используйте точки, полученные из нормального, экспоненциального или другого случайного распределения, если некоторые компоненты являются неограниченными. Чем меньше вы знаете о местоположении глобального минимума, тем более распределенным должно быть ваше случайное распределение. Например, нормальные распределения редко отсчитывают более трех стандартных отклонений от своих средств, но распределение Коши (плотность 1/( δ (1 + x2))) делает сильно разрозненные выборки.
Используйте идентичные начальные точки с добавленными случайными возмущениями на каждой координате - ограниченной, нормальной, экспоненциальной или другой.
При наличии лицензии Global Optimization Toolbox используйте GlobalSearch(Панель инструментов глобальной оптимизации) или MultiStart(Панель инструментов глобальной оптимизации) решатели. Эти решатели автоматически генерируют случайные начальные точки в пределах границ.
Чем больше вы знаете о возможных начальных точках, тем более целенаправленным и успешным будет ваш поиск.
Если целевая функция f (x) является гладкой, вектор - ∇f (x) указывает в направлении, где f (x) уменьшается наиболее быстро. Уравнение самого крутого спуска, а именно
t)),
вырабатывает путь x (t), который переходит к локальному минимуму с увеличением t. Как правило, начальные значения x (0), которые находятся рядом друг с другом, дают наиболее крутые пути спуска, которые стремятся к одной и той же минимальной точке. Бассейн притяжения для самого крутого спуска представляет собой набор исходных значений, которые приводят к такому же локальному минимуму.
На этом рисунке показаны два одномерных минимума. На рисунке показаны разные бассейны притяжения с разными стилями линий, и обозначены направления наиболее крутого спуска со стрелками. Для этой и последующих фигур чёрные точки представляют локальные минимумы. Каждый самый крутой путь спуска, начиная с точки x (0), переходит к черной точке в бассейне, содержащем x (0).
Одномерные бассейны
На этом рисунке показано, как самые крутые пути спуска могут быть сложнее в большем количестве габаритов.
Один бассейн притяжения, показывающий самые крутые пути спуска с различных стартовых точек
На этом рисунке показаны еще более сложные пути и бассейны притяжения.
Несколько бассейнов притяжения
Ограничения могут разбить один бассейн притяжения на несколько частей. Например, рассмотрите возможность минимизации y при следующих условиях:
y ≥ | x |
y ≥ 5 - 4 (x-2) 2.
На этом рисунке показаны два бассейна притяжения с конечными точками.
Самые крутые пути спуска - это прямые до границ зависимости. От границ зависимости самые крутые траектории спуска перемещаются вниз вдоль границ. Конечной точкой является либо (0,0), либо (11/4,11/4), в зависимости от того, является ли начальное значение x выше или ниже 2.
