计算科学 - 用于大绝对值优化的 Python 包 - 吾爱随笔录 - 问答

用于大绝对值优化的 Python 包

计算科学 Python 凸优化

2021-12-26 00:33:59

我有一个绝对值优化问题

min_{x} \sum | r - C x |

$\min_x \sum |r-Cx|$

其中 $x$ 在 200 维左右很小。但是 $C$ 有很多行， $C_{30000\times200}$ 和 $r$ 是 $30000\times1$ 。所以这会为绝对值引入大量的帮助变量。

有人可以推荐一个可以有效解决它的 Python 包吗？我尝试了 CVXOPT，但花了 3 个小时才解决了 5000 x 200 的精简版本。

解决这类问题通常很慢吗？

谢谢。

事实证明，CVXOPT 求解一点也不差！在 GLPK 中求解时间仅为 12 秒！

需要很长时间的是 CVX 建模。我使用了他们的集成建模模块

from cvxopt.modeling import variable, op, dot, matrix

和

y = abs(r-C*x) # quick
objfun = sum(y) # this line takes ages

我想最后一行很慢的原因是它正在检查凸性。

通过自己转换问题

min \sum v s . t . - v \leq r - C x \leq v

$\min \sum v\quad s.t.\,-v\leq r-Cx\leq v$

现在好了

1个回答

这个问题很容易转换成一个线性规划问题，它将有 60,000 个约束和 60,000 个（松弛变量）+ 200（x 个变量）。我假设矩阵是完全密集的，但问题是稀疏的。这应该可以通过一个相当好的 LP 求解器来解决。CVXOPT 在这方面遇到了这样的麻烦，我有点惊讶。 $C$

您的问题不清楚您是如何在 CVXOPT 中解决这个问题的。您是否在 MOSEK 求解器中使用了自己的 LP 公式？GLPK？您是否在 CVXOPT 中使用了 l1() 或 l1blas() 函数（这些在内部解决了 LP 公式）？

无论如何，因为你只是在解决

$\min \| r-Cx \|_{1}$

而不是更一般的LP，确实没有必要将这个问题表述为LP。还有许多其他算法可以解决这个 1 范数最小化问题，包括迭代重加权最小二乘法 (IRLS) 和次梯度下降法。求解 LP 公式通常不是最有效的方法。

其它你可能感兴趣的问题

上一篇最小二乘模型的参数约简算法下一篇使用紧支撑径向基函数进行插值