9

MATLAB的cvx套件可以解决下面的（看似无辜的）优化问题，但对于我正在使用的大型完整矩阵来说它相当慢。我希望这是因为使用 cvx 是多余的，而且问题实际上有一个解析解决方案，或者巧妙地使用一些内置的 MATLAB 函数可以更快地完成这项工作。

背景：众所周知，两者都x1=A\b解决x2=pinv(A)*b了最小二乘问题：

minimize norm(A*x-b)

区别在于norm(x2)<=norm(x1). 实际上x2是问题的最小范数解，所以norm(x2)<=norm(x)对于所有可能的解x。

定义D=norm(A*x2-b),（等价D=norm(A*x1-b)），然后x2解决问题

minimize norm(x)
subject to
norm(A*x-b) == D

问题：我想找到解决方案：

minimize norm(x)
subject to
norm(A*x-b) <= D+threshold

换句话说，我不需要norm(A*x-b)尽可能小，只要在一定的容忍度内。x我想要得到A*x的最小范数解决D+threshold方案b。

我无法在网络上或手动找到该问题的解析解决方案（例如在经典最小二乘问题中使用伪逆）。我一直在搜索诸如“具有非线性约束的最小二乘”和“具有阈值的最小二乘”之类的东西。

任何见解将不胜感激，但我想我真正的问题是： 在 MATLAB 中解决这个“阈值”最小二乘问题的最快方法是什么？

4

1 回答 1

2

有趣的问题。我不知道您的确切问题的答案，但下面提供了一个可行的解决方案。

回顾

定义res(x) := norm(Ax - b). 正如您所说，x2最小化res(x). 在超定的情况下（通常A比 col 的行多），x2是唯一的最小值。在未确定的情况下，它被无限多的其他人加入*。然而，在所有这些x2中，唯一的一个是最小化norm(x).

总而言之，x2最小化 (1)res(x)和 (2) norm(x)，并且按照优先级顺序进行。事实上，这表征（完全确定）x2。

极限表征

但是，另一个x2特征是

x2 := limit_{e-->0} x_e

在哪里

x_e := argmin_{x} J(x;e)

在哪里

J(x;e) := res(x) + e * norm(x)

可以证明

x_e = (A A' + e I)^{-1} A' b      (eqn a)

应该理解的是，这种表征x2是相当神奇的。即使(A A')^{-1}不存在限制也存在。并且限制以某种方式保留了上面的优先级（2）。

使用 e>0

当然，对于有限（但很小）e，x_e不会最小化res(x)（而是最小化J(x;e)）。用您的术语来说，差异就是阈值。我将其重命名为

gap := res(x_e) - min_{x} res(x).

减小 的值e可以保证减小 的值gap。gap因此，通过调整很容易达到特定值（即阈值） e。**

这种类型的修改（添加norm(x)到res(x)最小化问题）在统计文献中被称为正则化，并且通常被认为是稳定性（数值和参数值方面）的好主意。

*：请注意x1和x2仅在未确定的情况下有所不同

**：它甚至不需要任何繁重的计算，因为如果已经计算了 A 的 SVD，(eqn a)则可以很容易地为任何（正）值计算逆。e

于 2016-02-16T16:51:13.980 回答