我如何向量化矩阵/输入以便 scipy.optimize.minimize 可以使用它？

Question

我运行在为 scipy.optimize.minimize 转换无约束问题时遇到了问题。我想要运行 L-BFGS 方法。

基本问题如下所示：

分钟|| A - XY||

s.t。 X,Y

而 A 是给定的矩阵，X $\in \R^{nxl}$ 和 Y $\in \R^{lxm} 由于 scipy 只接受 Vector 输入，我试图将 XY 解释为一个更大的变量：Z=(X,Y)，其中我已经将 X 和 Y 的列放在彼此之下。

首先，我尝试编写函数来转换我的输入向量。对于一个基本示例，它运行良好（可能是因为矩阵很密集？idk）

这是我的代码：

import numpy as np
from scipy.optimize import minimize
R=np.array(np.arange(12)).reshape(3, 4)
Z0 = np.array(np.random.random(14))
#X=3x2 = 6
#Y=2x4 = 8
def whatineed (Z):
    return np.linalg.norm(R - np.dot(Z[:6].reshape(3,2),Z[6:].reshape(2,4)))

A = minimize(fun=whatineed, x0=Z0, method='L-BFGS-B', options={'disp': 1})

#print A

以上只是一个（看似？）有效的伪代码。它给了我 the/a 结果：

x: array([ 1.55308851, -0.50000733,  1.89812395,  1.44382572,  2.24315938, 3.38765876,  0.62668062,  1.23575295,  1.8448253 ,  2.45389762, 1.94655245,  1.83844053,  1.73032859,  1.62221667])

如果我运行它有一个大的它根本不起作用。

RUNNING THE L-BFGS-B CODE

           * * *

Machine precision = 2.220D-16
 N =       377400     M =           10
 This problem is unconstrained.

At X0         0 variables are exactly at the bounds

没有进一步移动。 R 实际上是一个或多或少稀疏的矩阵。但我真的不知道从哪里开始。是我的功能代码吗？是R的稀疏性吗？两个都？解决方法是什么？

更新：求解器适用于非常小的维度。如果我再大一点，就会出现这个错误：

ABNORMAL_TERMINATION_IN_LNSRCH                              

 Line search cannot locate an adequate point after 20 function
  and gradient evaluations.  Previous x, f and g restored.
 Possible causes: 1 error in function or gradient evaluation;
                  2 rounding error dominate computation.

 Cauchy                time 0.000E+00 seconds.
 Subspace minimization time 0.000E+00 seconds.
 Line search           time 0.000E+00 seconds.

 Total User time 0.000E+00 seconds.

正如您在用户时看到的那样，问题很小并且停止工作。运行它手写 (L-BFGS) 结果根本没有 steps/descents。

Answer 1

如果我们要解决

min_{B is rank <= k} ‖ A - B ‖_2

solution 是众所周知的 k 截断 SVD of A.

相反，我们正在努力解决

min_{X,Y} ‖ A - XY ‖_2

其中 X 的形状为 n × k 并且 Y 的形状为 k × n（我用的是k因为它比l更易读）

声明：这些是等价的问题。要看到这一点，我们需要证明：

XY 是等级 <= k（具有上述形状）。
任何秩 k 矩阵都可以写成 XY 的乘积（具有上述形状）。

证明：

第一个是从 Y 是等级 <= k 的事实得出的=38=]XY包含在Y
第二个是写出秩 <= k 矩阵的 SVD B = U D V* 并观察(UD) 的形状为 n × k 并且 V 的形状为 k × n除了第一个 k 分解的奇异值之外的所有奇异值，因为它们保证为零。

实施要解决 OP 所述的问题，我们只需要计算 A 的 SVD 并将其截断以排名 k。您可以使用 np.linalg.svd 或 sp.sparse.linalg.svds，具体取决于您的矩阵是否稀疏。对于 numpy 版本，rank k svd 可以计算为：

m,n = 10,20
A = np.random.randn(m,n)

k = 6
u,s,vt = np.linalg.svd(A)

X = u[:,:k]*s[:k]
Y = vt[:k]

print(X.shape, Y.shape)
print(np.linalg.norm(A-X@Y,2))

sp.sparse.linalg.svds 的语法几乎相同，只是您可以提前指定您想要的排名。

我如何向量化矩阵/输入以便 scipy.optimize.minimize 可以使用它？

How can i vectorize a matrix/ the input so that scipy.optimize.minimize can work with it?

python

scipy

sparse-matrix