我正在尝试解决/优化$Ax=b$在最小二乘意义上受制于

1. 盒子约束；
2. 少数（少于 5 个）平等/不平等约束；和
3. 绝对函数惩罚（或其他一些分段线性凸函数）。

也就是说，分钟$f(\mathbf{x})=|A\mathbf{x}-b|^2+\mathbf{c}\cdot|\mathbf{x}|$在哪里$\mathbf{c}\cdot|\mathbf{x}|=c_1|x_1|+...+c_n|x_n|$

特别是，$A\mathbf{x}=b$严重欠定（即$A$有几千列但有数百行），如果存在很多，任何有效的解决方案都可以。此代码对性能至关重要。我已经用尽了我能想到的一切。有没有什么明显的方法可以有效地解决这个问题（巧妙的公式或适当的算法选择）？

语言不可知的解决方案将不胜感激。

tl; dr - 跳过其余部分。这是我到目前为止尝试过的

方法 1 - 保持简单

使用有界 BFGS 并评估$f(\mathbf{x})$直接地。我正在尝试改进这一点，因为它太慢了。

方法 2 - QP：

$f(\mathbf{x})=\mathbf{x^T}A^TA\mathbf{x}-2\mathbf{x^T}A^Tb+\mathbf{c}\cdot|\mathbf{x}|=\frac{1}{2}\mathbf{x^T}Q\mathbf{x}+\mathbf{d}\cdot\mathbf{x}+\mathbf{c}\cdot|\mathbf{x}|$

所以这基本上是标准的二次形式，但是$Q$现在是巨大的并且是半正定的，因此很难使用。稍微慢一点。

方法 2 - 使用 QR 分解：

这个想法是使用 QR 分解和坐标变换来减小二次矩阵的大小。

$A^T=QR$和$\mathbf{x^T}Q=\mathbf{y^T}$

$f(\mathbf{x})=\mathbf{x^T}A^TA\mathbf{x}-2\mathbf{x^T}A^Tb+\mathbf{c}\cdot|\mathbf{x}|=\mathbf{y^T}RR^T\mathbf{y}+\mathbf{d}\cdot Q\mathbf{y}+\mathbf{c}\cdot|Q\mathbf{y}|$

这使得$A^TA$非常小而且执行速度很快。但是，这种转换会迫使数千个（快速）框约束变为线性不等式约束，这会影响性能。慢了很多。

还有其他想法吗？谢谢。