Алгоритмы параллельной оптимизации для задачи с очень дорогой целевой функцией

15

Я оптимизирую функцию из 10-20 переменных. Плохая новость заключается в том, что оценка каждой функции обходится дорого, примерно 30 минут последовательного вычисления. Хорошей новостью является то, что в моем распоряжении кластер с несколькими десятками вычислительных узлов.

Таким образом, вопрос: существуют ли алгоритмы оптимизации, которые позволили бы мне эффективно использовать всю эту вычислительную мощность?

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

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

Квадратичные алгоритмы, кажется, находятся где-то посередине: можно построить начальную «суррогатную модель», рассчитав кучу значений параллельно, но я не знаю, являются ли остальные итерации параллелизуемыми.

Любые предложения о том, какие методы оптимизации без градиента будут хорошо работать на кластере? Кроме того, есть ли в настоящее время какие-либо параллельные реализации алгоритмов оптимизации?

Майкл
источник
1
Вы всегда можете рассчитать градиент параллельно (для квазиньютоновских методов, использующих конечные разности) и получить ускорение, пропорциональное количеству параметров, т.е. 10x-20x.
Стали
@stali: вам нужен гессиан для квазиньютоновских методов оптимизации. Вычисление гессиана с помощью конечных различий в оценках функций на самом деле не очень хорошая идея. Вычисление конечно-разностных приближений градиента для оптимизации также, как правило, не очень хорошая идея.
Джефф Оксберри
Многие квазиньютоновские методы, такие как BFGS, не требуют явного гессиана. Я думаю, что используя градиенты, в сочетании с L-BFGS ОП может быстро достичь того, чего хочет.
Стали
@stali: я указал, почему использование приближения конечной разности к градиенту было бы плохой идеей в моем ответе. Это ухудшит сходимость, введя ошибку в правую часть квазиньютоновской итерации. Кроме того, он тратит впустую оценки функций, потому что нет возможности для повторного использования старых оценок (в отличие от суррогатных методов). Использование BFGS решает только половину проблем, связанных с предложенным вами подходом.
Джефф Оксберри
Это, скорее, комментарий, а не ответ. Но у меня нет выбора, так как у меня недостаточно представителей, чтобы оставить комментарий. Майкл, у меня очень похожий тип проблемы: дорогостоящие оценки функций, которые включают в себя сложные симуляции, работающие в кластере. Вы когда-нибудь находили код, подходящий для выполнения оптимизации, когда оценка функции включает в себя симуляцию в кластере?
MoonMan

Ответы:

16

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

С 10-20 переменными и дорогими оценками функций, тенденция состоит в том, чтобы рекомендовать алгоритмы оптимизации без производных. Я собираюсь категорически не согласиться с советом Пола: вам обычно нужен градиент машинной точности, если вы не используете какой-то особый метод (например, стохастический градиентный спуск в машинном обучении будет использовать форму цели, чтобы прийти к разумному градиентные оценки).

Каждый квазиньютоновский шаг будет иметь вид:

ЧАС~(ИксК)dКзнак равно-е(ИксК),

где - некоторая аппроксимация матрицы Гессе, d k - направление поиска, x k - значение переменных решения на текущей итерации, f - ваша целевая функция, а f - градиент вашей цели, а переменные решения обновляются как x k + 1 = x k + α k d k , где α kЧАС~dКИксКееИксК+1знак равноИксК+αКdКαКразмер шага, определенный некоторым образом (например, поиск строки). Вы можете избежать аппроксимации гессиана определенными способами, и ваши итерации будут сходиться, хотя, если вы используете что-то вроде приближения гессиана с конечными разностями с помощью точных градиентов, вы можете столкнуться с проблемами из-за плохой обусловленности. Обычно гессиан аппроксимируется с использованием градиента (например, методы типа BFGS с обновлениями ранга 1 до гессиана).

Приближение гессиана и градиента с помощью конечных разностей является плохой идеей по ряду причин:

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

Таким образом, чтобы получить одну итерацию квазиньютона, вы выполняете что-то вроде 420 оценок функций за 30 минут на оценку, что означает, что вы либо будете ждать некоторое время для каждой итерации, либо нужен большой кластер только для оценки функций. Фактические линейные решения будут состоять из 20 на 20 матриц (самое большее!), Поэтому нет смысла распараллеливать их. Если вы можете получить информацию о градиенте, например, путем решения сопряженной задачи, то это может оказаться более целесообразным, и в этом случае, возможно, стоит взглянуть на такую ​​книгу, как Nocedal & Wright.

Если вы собираетесь выполнять много оценок функций параллельно, вам следует вместо этого взглянуть на подходы суррогатного моделирования или на генерацию методов поиска, прежде чем рассматривать квазиньютоновские подходы. Классические обзорные статьи - это статья Риоса и Сахинидиса о методах без производных , которая была опубликована в 2012 году и дает действительно хорошее, широкое сравнение; сравнительная статья More и Wild от 2009 г .; учебник 2009 года «Введение в оптимизацию без деривативов» Конна, Шейнберга и Висенте; и обзорная статья о генерации методов поиска по множествам Колды, Льюиса и Торцона из 2003 года.

Как указано выше, программный пакет DAKOTA будет реализовывать некоторые из этих методов, как и NLOPT , который реализует DIRECT, и некоторые из суррогатных методов моделирования Powell. Вы также можете взглянуть на MCS ; он написан на MATLAB, но, возможно, вы можете перенести реализацию MATLAB на язык по вашему выбору. DAKOTA, по сути, представляет собой набор сценариев, которые вы можете использовать для запуска дорогостоящего моделирования и сбора данных для алгоритмов оптимизации, а NLOPT имеет интерфейсы на большом количестве языков, поэтому выбор языка программирования не должен быть большой проблемой при использовании любого программного пакета; Тем не менее, DAKOTA требует некоторого времени для изучения, и у нее есть огромное количество документации, которую нужно проанализировать.

Джефф Оксберри
источник
2
Мне приятно быть полностью неправым и узнавать что-то новое и полезное в процессе :).
Павел
Благодарность! Еще одно уточнение: какие из этих алгоритмов способны выполнять оценку функций параллельно? Например, для k-way grid, выполняющих итерации n + 1, ..., n + k, основываясь только на информации, полученной из итераций 1, ..., n?
Майкл
К
3

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

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

Ссылка

Wang L., Shan S. & Wang GG (2004). Метод выборки с отслеживанием мод для глобальной оптимизации дорогостоящих функций черного ящика. Техническая оптимизация, 36 (4), 419-438.

Жан Давэй
источник
2

Я не уверен, что параллельный алгоритм действительно то, что вы ищете. Это ваши функциональные оценки, которые очень дороги. Вы хотите распараллелить саму функцию, а не алгоритм оптимизации.

Если вы не можете этого сделать, значит, между исчерпывающим поиском и алгоритмом Ньютона есть середина, это методы Монте-Карло. На множестве разных ядер / узлов вы можете запустить один и тот же алгоритм, который склонен падать на локальные оптимумы (скажем, квазиньютоновские алгоритмы), но все со случайными начальными условиями. Лучшее предположение для истинного оптимума - минимум минимумов. Это тривиально для распараллеливания и может использоваться для расширения любого метода. Хотя это и не совсем эффективно, но если у вас есть достаточно вычислительной мощности, это может определенно выиграть битву между производительностью программирования и производительностью алгоритма (если у вас много вычислительной мощности, это может закончиться до того, как вы закончите делать более изящный алгоритм).

Крис Ракауцкас
источник
0

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

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

Для получения дополнительной информации прочитайте «Числовая оптимизация» компании Nocedal & Wright, глава 7 . Есть много пакетов программного обеспечения для оптимизации, которые реализуют это параллельно. Среди наиболее распространенных бесплатных программ - пакет программного обеспечения DAKOTA (Sandia National Labs) .

Пол
источник
5
N
-2

Вот решение вашей проблемы.

Описание математического метода приведено в данной статье .

Павел
источник
3
Добро пожаловать в SciComp.SE. Можете ли вы предоставить подробную информацию о подходе, описанном в документе и реализованном в программном обеспечении? Какой метод используется? Почему это хорошо? Что предусмотрено в этом подходе, что другие ответы не охватывают?
Никогуаро
2
Также кажется, что это твоя собственная работа. Если это правда, пожалуйста, укажите это в своем ответе.
Никогуаро
@nicoguaro: спасибо, но я знаю, как нажимать на ссылки.
Майкл
2
@ Майкл, это не для тебя. Философия этого сайта - сборник ответов. Вы получаете ответ сегодня, но в будущем кому-то еще может понадобиться такая же помощь. Вот почему существуют стандарты того, что является хорошим ответом.
Никогуаро