Geo*_*off 8 optimization matlab linear-algebra least-squares cvx
用于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中解决这个"阈值化"最小二乘问题的最快方法是 什么？
有趣的问题。我不知道您的确切问题的答案，但下面提供了一个可行的解决方案。
定义res(x) := norm(Ax - b)。正如你所说，x2最小化res(x). 在超定情况下（通常A行数多于列数），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，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