matlab - MATLAB 中阈值内的最小二乘最小化

Question

cvx MATLAB 套件可以解决下面的(看似无辜的)优化问题，但对于我正在处理的大型全矩阵来说，它的速度相当慢。我希望这是因为使用 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 中解决这个“阈值”最小二乘问题的最快方法是什么？

Answer 1

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

回顾

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

总而言之，x2 最小化了 (1) res(x) 和 (2) norm(x)，它在该优先顺序。事实上，这表征(完全确定)x2。

极限表征

但是，another characterization 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 的值。因此，通过调整 e 很容易达到特定的 gap 值(即阈值)。**

这种类型的修改(将norm(x)添加到res(x)最小化问题)在统计文献中被称为正则化，通常被认为是一个很好的稳定性的想法(在数值上和关于参数值)。

---

*:请注意，x1 和 x2 仅在欠定情况下不同

**:它甚至不需要任何繁重的计算，因为对于 e 的任何(正)值，如果已经计算了 A 的 SVD。