二次规划与拟牛顿法

Question

昨天，我发布了一个关于SVM Primal Form实现的一般概念的问题：

Support Vector Machine Primal Form Implementation

"lejlot“帮助我理解了我正在解决的是一个QP问题。

但是我仍然不明白我的目标函数是如何表示为QP问题的

(http://en.wikipedia.org/wiki/Support_vector_machine#Primal_form)

我也不明白QP和拟牛顿法有什么关系

我所知道的是，拟牛顿方法将解决我的QP问题，这个问题应该是由

我的目标函数(我看不出其中的联系)

有人能给我讲讲这个吗？？

Answer 1

对于支持向量机，目标是找到一个分类器。这个问题可以用你想要最小化的函数来表示。让我们首先考虑牛顿迭代。牛顿迭代是一种求解形式为f(x) = 0的问题的数值方法。我们可以通过以下迭代，对它进行数值求解，而不是解析地求解它：，，，，，，。

x^k+1 = x^k - DF(x)^-1 * F(x)

这里x^k+1是k+1th迭代，DF(x)^-1是F(x)的雅可比矩阵的逆，x是迭代中的第k个x。

只要我们在步长(增量x)方面取得进展，或者如果我们的函数值接近0到一个好的程度，这个更新就会运行。可以相应地选择终止标准。

现在考虑解决问题f'(x)=0。如果我们给出牛顿迭代公式，我们就会得到

x^k+1 = x - HF(x)^-1 * DF(x)

其中HF(x)^-1是海森矩阵的逆，DF(x)是函数F的梯度。请注意，我们讨论的是n维分析，不能只取商。我们必须求矩阵的逆。

现在我们面临一些问题:在每一步中，我们必须计算更新后的x的Hessian矩阵，这是非常低效的。我们还必须解一个线性方程组，即y = HF(x)^-1 * DF(x)或HF(x)*y = DF(x)。因此，我们不是在每次迭代中计算Hessian，而是从Hessian (可能是单位矩阵)的初始猜测开始，并在每次迭代后执行秩1更新。有关确切的公式，请查看here。

那么，这个链接与SVM有什么关系呢？

当你看着你试图最小化的函数时，你可以表述一个原始问题，你可以将其重新表述为对偶拉格朗日问题，它是凸的，可以用数值方法求解。这一切都在文章中有很好的记录，所以我不会试图用不太好的质量来表达这些公式。

但是这个想法是这样的:如果你有一个对偶问题，你可以用数值来解决它。有多个解算器可用。在你发布的链接中，他们建议坐标下降，这可以一次解决一个坐标的优化问题。或者你可以使用次梯度下降。另一种方法是使用L-BFGS。这在this论文中得到了很好的解释。

另一种解决此类问题的流行算法是ADMM (交替方向乘法法)。为了使用ADMM，您必须将给定的问题重新表述为一个相等的问题，该问题将提供相同的解决方案，但具有正确的ADMM格式。为此，我建议阅读ADMM上的Boyds脚本。

一般而言:首先，了解您试图最小化的函数，然后选择最适合的数值方法。在这种情况下，次梯度下降和坐标下降是最合适的，正如维基百科链接中所述。