Я знаком с алгоритмом градиентного спуска, который может найти локальный минимум (максимум) данной функции.
Есть ли какая-либо модификация градиентного спуска, которая позволяет найти абсолютный минимум (максимум), где функция имеет несколько локальных экстремумов?
Существуют ли общие методы, как улучшить алгоритм, который может найти локальный экстремум, для нахождения абсолютного экстремума?
Ответы:
Я полагаю, вы говорите о безусловной минимизации. Ваш вопрос должен указать, рассматриваете ли вы конкретную структуру проблемы. В противном случае ответ - нет.
Сначала я должен развеять миф. Классический метод градиентного спуска (также называемый методом наискорейшего спуска ) даже не гарантирует нахождение локального минимизатора. Он останавливается, когда находит критическую точку первого порядка, т. Е. Точку, в которой градиент исчезает. В зависимости от минимизируемой функции и начальной точки, вы вполне можете оказаться в седловой точке или даже в глобальном максимизаторе!
Теперь практически все методы оптимизации на основе градиента страдают от этого из-за замысла. Ваш вопрос действительно о глобальной оптимизации . Опять же, ответ - нет, нет общих рецептов для изменения метода, чтобы гарантировать, что глобальный минимизатор идентифицирован. Просто спросите себя: если алгоритм возвращает значение и говорит, что это глобальный минимизатор, как бы вы проверили, что это правда?
Есть классы методов в глобальной оптимизации. Некоторые вводят рандомизацию. Некоторые используют мультистартовые стратегии. Некоторые используют структуру проблемы, но это для особых случаев. Подберите книгу по глобальной оптимизации. Вам понравится.
источник
Вероятно, нет единого универсального ответа на ваш вопрос. Но вы можете захотеть изучить алгоритмы имитации отжига или другие подходы, основанные на методах цепей Маркова Монте-Карло (MCMC). Их также можно комбинировать с локальными методами, такими как градиентный спуск.
источник
есть много ссылок на «глобальную оптимизацию нейронных сетей». методы аналогичны имитации отжига [см. другой ответ]. Основная идея состоит в том, чтобы возобновить спуск по градиенту сети, начиная со множества различных начальных точек веса, выбранных случайным или систематическим образом. каждый результат градиентного спуска тогда похож на «образец». чем больше выборок, тем выше вероятность того, что одна из выборок является глобальным оптимумом, особенно если целевая функция «хорошо себя ведет» в смысле непрерывного, дифференцируемого и т. д.
онлайн ссылки
[1] Глобальная оптимизация весов нейронных сетей. Автор Hamm et al.
[2] Глобальный оптимизационный подход к обучению нейронных сетей Фоглис / Лагарис
[3] Калибровка искусственных нейронных сетей с помощью глобальной оптимизации Pinter
[4] глобальной оптимизации нейронных сетей с использованием детерминированной Гибридный подход Беляков
[5] Глобальная оптимизация для обучения нейронной сети Шан / Ва
источник
В общем случае вычислительно сложно оптимизировать многовариантные невыпуклые функции. Твердость бывает разных вкусов (криптографическая, NP-хард). Один из способов увидеть это состоит в том, что смешанные модели (такие как смесь гассов или HMM) трудно выучить, но было бы легко (*), если бы было возможно эффективно максимизировать вероятность. Результаты о сложности изучения HMM см. По адресу http://alex.smola.org/journalclub/AbeWar92.pdf http://link.springer.com/chapter/10.1007%2F3-540-45678-3_36 http: // www.math.ru.nl/~terwijn/publications/icgiFinal.pdf
(*) по модулю обычные условия невырожденности и идентифицируемости
источник
я должен не согласиться с Домиником. в середине 1980-х годов Хайеком было показано, что отжиг невыпуклой задачи при определенных строгих условиях гарантированно достигнет глобального минимума: http://dx.doi.org/10.1287/moor.13.2.311
источник