Оптимизация многомерной функции с начальным решением, близким к оптимальному

Question

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

Answer 1

Если у вас уже есть итеративный оптимизатор (например, на основе метода установки направления Пауэлла или CG), почему бы вам не использовать исходное решение в качестве отправной точки для следующего запуска вашего оптимизатора?

РЕДАКТИРОВАТЬ: из-за вашего комментария: если вычисление матрицы Якобиана или Гессе вызывает проблемы с производительностью, попробуйте BFGS (http://en.wikipedia.org/wiki/BFGS_method),, это полностью исключает вычисление Гессиана; здесь http://www.alglib.net/optimization/lbfgs.php вы найдете (бесплатную некоммерческую) реализацию BFGS. Хорошее описание деталей вы будете здесь .

И не ожидайте получить что-либо от поиска исходного решения с менее сложным алгоритмом.

Так что это все о неограниченной оптимизации. Если вам нужна информация об оптимизации с ограничениями , я предлагаю вам поискать в Google "SQP".

Answer 2

Нам, вероятно, нужно немного больше информации о вашей проблеме; но поскольку вы знаете, что вы близки к правильному решению, и если производные легко вычислить, Ньютон-Рафсон - разумный выбор, а если нет, то Конъюгат-Градиен t может сделать чувство.

Answer 3

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

Затем вы должны указать свои требования: вы хотите скорость.Какую точность вы хотите?Имеет ли значение космическая эффективность?Самое главное: какая у вас информация: только значение функции или у вас также есть производные (возможно, вторые производные)?

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

Глобальная информация (т. Е. Является ли функция выпуклой, существует ли гарантированный глобальный минимум или много локальных и т. Д.)можно оставить в стороне на данный момент.Если у вас возникли проблемы с нахождением минимальной точки возмущенной проблемы, вам придется это исследовать.

Ответы на эти вопросы позволят нам выбрать конкретный алгоритм.Есть много вариантов (и компромиссов) для многомерной оптимизации.

Кроме того, что быстрее будет очень сильно зависеть от проблемы (а не от алгоритма), и должно быть определено экспериментально.

Answer 4

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

Один - это метод Ньютона

другой метод - - разделение пополам

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

Answer 5

Хотя я не очень разбираюсь в использовании компьютеров в этом качестве, я помню статью, в которой использовались нейроэволюционные методы для нахождения сравнительно оптимальных уравнений с учетом известной сложности функций (линейная, N-полиномиальная, экспоненциальная,логарифмический и т. д.) и набор точечных графиков.Насколько я помню, это было одно из самых ранних применений того, что мы теперь знаем как вычислительную нейроэволюцию;Поскольку функциональная сложность (и, следовательно, количество терминов) уравнения известна и фиксирована, можно использовать статическую нейронную сеть и засекать ее с ближайшими значениями, а затем «мутировать» и проверить на пригодность, с помощью эвристики, чтобы сделать новые сети ближек существующим сетям с высокой физической подготовкой.Используя многопоточность, можно создавать, тестировать и оценивать множество сетей параллельно.