Локальный оптимум - Local optimum

Бассейны с аттракционами вокруг локально оптимальных точек
Полином степени 4: впадина справа является локальным минимумом, а левая - глобальным минимумом. Пик в центре - это локальный максимум.

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

Непрерывный домен

Когда оптимизируемая функция является непрерывной , можно использовать исчисление для поиска локальных оптимумов. Если первая производная существует везде, ее можно приравнять к нулю; если функция имеет неограниченную область определения , для того чтобы точка была локальным оптимумом, необходимо, чтобы она удовлетворяла этому уравнению. Затем проверка второй производной обеспечивает достаточное условие для того, чтобы точка была локальным максимумом или локальным минимумом.

Методы поиска

Методы локального поиска или подъема на холм для решения проблем оптимизации начинаются с начальной конфигурации и многократно переходят к улучшающейся соседней конфигурации . В пространстве поиска генерируется траектория, которая отображает начальную точку в локальный оптимум, где локальный поиск застревает (нет доступных улучшающих соседей). Таким образом, пространство поиска подразделяется на бассейны притяжения , каждый из которых состоит из всех начальных точек, которые имеют данный локальный оптимум в качестве конечной точки траектории локального поиска. Локальный оптимум может быть изолирован (окружен нелокально-оптимальными точками) или частью плато , локально оптимальной области с более чем одной точкой равного значения.

Если в решаемой задаче есть все локально оптимальные точки с одинаковым значением оптимизируемой функции, локальный поиск эффективно решает глобальную проблему: поиск локального оптимума дает глобально оптимальное решение.

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

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

Смотрите также