Если у меня есть N независимых задач оптимизации, в общем, было бы быстрее решить каждый самостоятельно или объединить проблемы? Метод Ньютона имеет временную сложность log (p) * (время вычисления отношения производных) для заданной точности p, предполагая разумные семена. Если многомерная временная сложность Ньютона Рафсона не масштабируется с числом измерений, то сложность при заданном p будет по-прежнему зависеть от градиентных/гессианных вычислений и линейного решателя. Я прошу в основном ради эффективности кода: я хочу подстраивать функции правдоподобия подмножеств данных либо с помощью регуляции подмножества, либо с помощью глобальной регуляризации. Если они одинаковы по стоимости, я мог бы реализовать один оптимизатор Ньютона, который мог бы использовать различные регуляризационные штрафы в качестве функциональных аргументов, переключаясь между разреженными и плотными решателями, когда это необходимо.Одновременная оптимизация/временная сложность многомерного Newton Raphson
Ниже, разреженный решатель бьет человека через цикл, но мне интересно, просто ли это накладные расходы на основе python (можно ли улучшить результаты цикла с помощью Cython)? Преобразование из стека матрицы в блок диагонали является дорогостоящим, но не имеет отношения к моей реализации; Я заполняю ранее существовавшие градиентные/hessian массивы на каждой итерации, поэтому время вычисления должно быть одинаковым. Моя IDE замерла, когда я использовал np.linalg.solve
с плотной матрицей для bigA
, что открывает еще одну проблему, которая, вероятно, мне понадобится, чтобы найти более эффективный способ решения плотных проблем, которые могут возникнуть в результате глобальной регуляризации.
import timeit
setup = '''
import numpy as np; import scipy as sp
import scipy.sparse; import scipy.sparse.linalg
A = np.random.random((1000,10,10))
b = np.random.random((1000,10))
bigA = sp.sparse.block_diag(A, format = "csr")
bigb = b.flatten()
'''
expr1 = 'for i in range(1000): np.linalg.solve(A[i,...], b[i,...])'
expr2 = 'sp.sparse.linalg.spsolve(bigA, bigb)'
timeit.timeit(expr1, setup, number = 100)
# 1.2879039069994178
timeit.timeit(expr2, setup, number = 100)
# 0.45410968599753687
# with setup
imports = '''
import numpy as np
import scipy as sp
import scipy.sparse
import scipy.sparse.linalg
'''
setup1 = '''
A = np.random.random((1000,10,10))
b = np.random.random((1000,10))
for i in range(1000):
np.linalg.solve(A[i,...], b[i,...])
'''
setup2 = '''
A = np.random.random((1000,10,10))
b = np.random.random((1000,10))
bigA = sp.sparse.block_diag(A, format = "csr")
bigb = b.flatten()
sp.sparse.linalg.spsolve(bigA, bigb)
'''
timeit.timeit(setup1, imports, number = 100)
# 1.355804075999913
timeit.timeit(setup2, imports, number = 100)
# 24.209087412000372
sol1 = np.empty(1e4)
u = 0
for i in range(1000):
sol1[u:u+10] = np.linalg.solve(A[i,...], b[i,...])
u += 10
sol2 = sp.sparse.linalg.spsolve(bigA, bigb)
np.sum((sol1 - sol2)**2)
# 2.49782849627e-14
Спасибо за ответ. Хотя я в конце концов понял ваши первые два момента, я никогда не рассматривал более поздние 4. Ожидаемые подзадачи, вероятно,> 1000 переменных, причем как внутри, так и между регуляцией проблем, которые обычно приводят к плотной матрице. Первоначально я задавал этот вопрос, когда думал о одном оптимистере для различных размеров проблем и структур регуляризации. Подумав больше о ожидаемых наборах данных, я в настоящее время пишу стохастический оптимизатор квази-Ньютона, который использует приближение к хезианскому BFGS в Python/Cython, поэтому память больше не является проблемой. –