numpy матричное умножение с переменными целлюлозы, занимающими слишком много времени - PullRequest
Новая
       65

numpy матричное умножение с переменными целлюлозы, занимающими слишком много времени

0 голосов
/ 29 апреля 2020

Я пытаюсь создать решатель линейного программирования, который минимизирует следующую цель:

P1 * E1 x V1 - P2 * E2 x V2

Где '*' - это внутренний продукт и «x» - умножение матриц.

E и V - матрицы с формами 512x2048 и 2048x64 соответственно. E и P - матрицы с действительными значениями, а V - матрица переменных решения целлюлозы.

Проблема в том, что умножение матрицы E x V на numpy занимает слишком много времени. Я могу сказать, что причина в том, что V не числовая матрица.

Вот код, откорректированный для справки: 

 V_pos = [[0] * 2048] * 512
    for i in range(0, 512):
        for j in range(0, 2048):
            V_pos[i][j] = plp.LpVariable("{0}_{1}_pos".format(i, j), lowBound=-0.1, upBound=0.1,
                                     cat='Continuous')
V_neg = [[0] * 2048] * 512
    for i in range(0, 512):
        for j in range(0, 2048):
            V_neg[i][j] = plp.LpVariable("{0}_{1}_neg".format(i, j), lowBound=-0.1, upBound=0.1,
                                     cat='Continuous')

 problem = plp.LpProblem("My Problem", plp.LpMinimize)
 problem += plp.lpDot(P, np.matmul(V_pos, E)) - plp.lpDot(P, np.matmul(V_neg, E))
 problem.solve()

Это своего рода работа, но для выполнения которой требуется около 2 минут. матрица умножения там. В PuLP нет встроенной операции умножения матриц ... Можно ли это ускорить?

Поскольку я собираюсь выполнить все это примерно для 2000 различных P и Es. И каждый раз подавать выходные данные в график тензорного потока ... для дальнейших вычислений.

Обновление текущего прогресса:

Мне удалось изменить матрицы и избежать умножения и замены их сложениями, поэтому моя цель теперь выглядит следующим образом:

P1 * (E1 + V1) - P2 * (E2 + V2)

Где * - внутренняя операция с продуктом. Теперь на вычисление одной итерации решения LP уходит не несколько минут, а на моем ноутбуке около 3,5 секунд. Тем не менее, это все еще слишком долго для меня. Мне нужно уменьшить это до долей секунды, если возможно, до миллисекунд.

Первоначальный подход заключался в нахождении оптимальных V1 и V2 с помощью градиентного спуска, и это занимало ~ 0,05 секунды на итерацию на той же машине.

Я мог бы попытаться вывести проблему на более низкий уровень и составить проблема линейного программирования на cb c (напишите обертку на c ++ специально для моей задачи). Но это проблематично c, так как мне не хватает опыта в линейном программировании и я не пишу код на C ++ около 5 лет.

1 Ответ

0 голосов
/ 04 мая 2020

Слишком долго для комментария, поэтому я опубликую это здесь.

Для каждого экземпляра E и P минимизация P1 * (E1 + V1) - P2 * (E1 - V1) должна совпадать с минимизацией (P1 - P2) * V1, поскольку вы просто добавляя константы с + P1 * E1 и - P2 * E1.

При решении многих линейных задач вы должны знать о стоимости создания проблемы. Например, для создания проблемы может потребоваться 3.4 секунд, а для ее решения передается что-то вроде CPLEX и 0.1 секунд. Если это проблема, вы можете посмотреть, как изменить экземпляр LP на месте, добавив новые значения для P и E, вызывая метод execute. У меня нет опыта работы с PuLP, но я столкнулся с этой проблемой с JuMP в Julia, и это может сильно повлиять на производительность.

Кроме того, возможно, я что-то упускаю, но похоже, единственные ограничения в приведенном выше примере кода говорят о том, что каждый элемент V должен быть между -0.1 и 0.1. Если это единственные ограничения, то проблема имеет решение в «закрытой форме». Если вы хотите свести к минимуму цель, вы устанавливаете V1[i,j] на 0.1 каждый раз, когда (P1[i,j] - P2[i,j]) является отрицательным, а V1[i,j] на -0.1 в противном случае. Это связано с тем, что линейная программа всегда будет допускать решение в крайней точке допустимого набора, а в приведенном примере допустимый набор является по существу блоком измерения 2048 * 512.

...