Прежде чем указать на возможную простую реализацию процедуры квазиньютоновской оптимизации в CUDA, несколько слов о том, как работает квазиньютоновский оптимизатор.
Рассмотрим функцию f от N вещественных переменных x и произведем разложение второго порядка вокруг определенной точки xi:
где A — матрица Гессе.
Чтобы найти минимум, начиная с точки xi, метод Ньютона состоит в том, чтобы заставить
что влечет за собой
и что, в свою очередь, подразумевает знание обратного гессиана. Кроме того, чтобы обеспечить снижение функции, направление обновления
должно быть таким, чтобы
что подразумевает, что
Согласно приведенному выше неравенству матрица Гессе должна быть определенно положительной. К сожалению, матрица Гессе не обязательно определенно положительна, особенно далеко от минимума f, поэтому использование обратной матрицы Гессе, кроме вычислительной нагрузки, может быть также вредным, продвигая процедуру еще дальше от минимум в сторону областей с возрастающими значениями f. Вообще говоря, удобнее использовать квазиньютоновский метод, т. е. аппроксимацию обратного гессиана, который сохраняет определенное положительное значение и обновляет итерацию после итераций, сходящихся к обратному самому гессиану. Грубое обоснование квазиньютоновского метода состоит в следующем. Рассмотреть возможность
а также
Вычитая два уравнения, мы получаем правило обновления для процедуры Ньютона
Правило обновления для квазиньютоновской процедуры следующее:
где Hi+1 — упомянутая матрица, аппроксимирующая обратную матрицу Гессе и обновляемая шаг за шагом.
Существует несколько правил обновления Hi+1, и я не буду вдаваться в подробности этого пункта. Очень распространенный алгоритм предоставляется Бройден-Флетчер-Гольдфарб-Шанно, но во многих случаях Полак-Рибьер схема достаточно эффективна.
Реализация CUDA может следовать тем же шагам, что и классический подход Числовые рецепты, но принимая во внимание следующее:
1) Векторные и матричные операции можно эффективно выполнять с помощью CUDA Thrust или cuBLAS; 2) Логика управления может выполняться ЦП; 3) Минимизация линий, включая брекетинг корней и поиск корней, может выполняться на ЦП, ускоряя только оценку функционала стоимости и градиента графического процессора.
По приведенной выше схеме неизвестные, градиенты и гессианы могут храниться на устройстве без необходимости перемещать их туда и обратно с хоста на устройство.
Обратите также внимание на то, что в литературе имеются некоторые подходы, в которых также предлагаются попытки распараллелить минимизацию строк, см.
Ю. Фей, Г. Ронг, Б. Ван, В. Ван, "Параллельный алгоритм L-BFGS-B на графическом процессоре", Computers & Graphics, vol. 40, 2014, стр. 1-9.
На этой странице github доступна полная реализация CUDA, обобщающая подход числовых рецептов, использующий linmin, mkbrak и dbrent для случая параллельного GPU. Этот подход реализует схему Полака-Рибьера, но его можно легко обобщить на другие квазиньютоновские задачи оптимизации.
person
Vitality
schedule
31.01.2015
