Продолжаем знакомство с методами многомерной оптимизации.
Далее предложена реализация метода наискорейшего спуска с анализом скорости выполнения, а также имплементация метода Нелдера-Мида средствами языка Julia и C++.
Рубрика «многомерная оптимизация»
Julia, Градиентный спуск и симплекс метод
2019-02-12 в 17:46, admin, рубрики: Julia, Алгоритмы, градиентный спуск, машинное обучение, метод Нелдера-Мида, многомерная оптимизация, покоординатный спуск, Программирование, симлекс методJulia и метод покоординатного спуска
2019-02-11 в 19:09, admin, рубрики: Julia, Алгоритмы, метод золотого сечения, метод ньютона, метод параболической интерполяции, многомерная оптимизация, одномерная оптимизация, Программирование
Метод покоординатного спуска является одним из простейших методов многомерной оптимизации и неплохо справляется с поиском локального минимума функций с относительно гладким рельефом, поэтому знакомство с методами оптимизации лучше начинать именно с него.
Поиск экстремума ведется в направлении осей координат, т.е. в процессе поиска изменяется только одна координата. Таким образом, многомерная задача сводится к одномерной.
Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python
2017-08-11 в 16:03, admin, рубрики: dogleg, python, trust-regio, Алгоритмы, безусловная оптимизация, математика, машинное обучение, многомерная оптимизация, оптимизация, Программирование, численные методы
Trust-region метод (TRM) является одним из самых важных численных методов оптимизации в решении проблем нелинейного программирования (nonlinear programming problems). Метод базируется на определении региона вокруг лучшего решения, в котором квадратичная модель аппроксимирует целевую функцию.
Методы линейного поиска (line search) и методы trust-region генерируют шаги с помощью аппроксимации целевой функции квадратичной моделью, но использую они эту модель по-разному. Линейный поиск использует её для получения направления поиска и дальнейшего нахождения оптимального шага вдоль направления. Trust-region метод определяет область (регион) вокруг текущей итерации, в котором модель достаточно аппроксимирует целевую функцию. В целях повышения эффективности направление и длина шага выбираются одновременно.
Trust-region методы надежны и устойчивы, могут быть применены к плохо обусловленным задачам и имеют очень хорошие свойства сходимости. Хорошая сходимость обусловлена тем, что размер области TR (обычно определяется модулем радиус-вектора) на каждой итерации зависит от улучшений сделанных на предыдущих итерациях.
Читать полностью »
Генетический алгоритм — наглядная реализация
2015-04-02 в 14:25, admin, рубрики: Matlab, генетический алгоритм, математика, многомерная оптимизация, Программирование, эволюцияГода четыре назад, в универе услышал о таком методе оптимизации, как генетический алгоритм. О нем везде сообщалось ровно два факта: он клёвый и он не работает. Вернее, работает, но медленно, ненадежно, и нигде его не стоит использовать. Зато он красиво может продемонстрировать механизмы эволюции. В этой статье я покажу красивый способ вживую посмотреть на процессы эволюции на примере работы этого простого метода. Нужно лишь немного математики, программирования и все это приправить воображением.
Кратко об алгоритме
Итак, что же такое генетический алгоритм? Это, прежде всего, метод многомерной оптимизации, т.е. метод поиска минимума многомерной функции. Потенциально этот метод можно использовать для глобальной оптимизации, но с этим возникают сложности, опишу их позднее.
Сама суть метода заключается в том, что мы модулируем эволюционный процесс: у нас есть какая-то популяция (набор векторов), которая размножается, на которую воздействуют мутации и производится естественный отбор на основании минимизации целевой функции. Рассмотрим подробнее эти процессы.
Читать полностью »