Question

假设我们希望找到最小化下式的x值

存在专门的线性代数算法能够高效地解决这个问题，但是我们也可以探索如何使用基于梯度的优化来解决这个问题，这可以作为这些技术是如何工作的一个简单例子。

首先，我们计算梯度

然后，我们可以采用小的步长，并按照这个梯度下降，见算法4.1中的详细信息。

算法4.1　从任意点x开始，使用梯度下降关于x最小化的算法。

将步长（）和容差（δ）设为小的正数。

end while

我们也可以使用牛顿法解决这个问题。因为在这个情况下，真实函数是二次的，牛顿法所用的二次近似是精确的，该算法会在一步后收敛到全局最小点。

现在假设我们希望最小化同样的函数，但受的约束。要做到这一点，我们引入Lagrangian

现在，我们解决以下问题

我们可以用Moore-Penrose伪逆：找到无约束最小二乘问题的最小范数解。如果这一点是可行的，那么这也是约束问题的解。否则，我们必须找到约束是活跃的解。关于x对Lagrangian微分，我们得到方程

这就告诉我们，该解的形式将会是

λ的选择必须使结果服从约束。我们可以关于λ进行梯度上升找到这个值。为了做到这一点，观察

当x的范数超过1时，该导数是正的，所以为了跟随导数上坡并相对λ增加Lagrangian，我们需要增加λ。因为的惩罚系数增加了，求解关于x的线性方程现在将得到具有较小范数的解。求解线性方程和调整λ的过程将一直持续到x具有正确的范数，并且关于λ的导数是0。

本章总结了开发机器学习算法所需的数学基础。现在，我们已经为建立和分析一些成熟的学习系统做好了准备。

————————————————————

(1) 译者注：与通常的条件数定义有所不同。

(2) KKT方法是Lagrange乘子法（只允许等式约束）的推广。