机器学习数学原理（5）——广泛拉格朗日乘子法

这一篇博客针对的是有约束的凸优化问题主要是为后面的最优间隔分类器以及其演化的SVM（支持向量机，Support Vector Machine）算法作铺垫Andrew Ng茬讲解最优间隔分类器时运用了广泛拉格朗日乘子法但并没有讲的十分的明细，而是直接使用了结论故笔者专门复习了拉格朗日乘子法並且学习了其在不等式约束情况下的优化（即广泛拉格朗日乘子法）。

这里要感谢博主Poll的博文：笔者写的是以博主Poll的博文为骨架，同时加上了自己对其的补充并且解释了原文中很容易引起误解的或者难理解的公式。当然这里也要感谢MIT的在线数学课程博主Poll的博文正是课程上该内容的笔记。

另外老规矩由于笔者水平有限，若出现不妥或者错误的地方欢迎批评指出。

首先我们先要明确这个算法的目的是優化对于一个连续的函数来说其实就是求全局极值。

现在我们来考虑一下没有约束条件的凸优化问题对高等数学略有了解的人应该都知道对于一个连续的函数求极值点，其实就应该将函数求导然后取导数向量为零向量即可。

例如一个n元函数f(x1,x2,…,xn)记作f(X)，当我们需要求其極值时便分别求f(X)对于xi的偏导（i=1~n），然后令这n个偏导为零便将求极值点的问题转化为n个n元方程构成的方程组求解。

然而往往事情并没有這么简单上述问题的前提往往在规划问题中过于纯粹。在实际问题中这n个自变量往往不是独立的即满足一些约束条件。这样一来上述求导的方法便不再使用因为其求导计算出的极值点X往往并不能满足约束条件。

现在我们细细分析一下导致这种差别的原因不难发现，絀现这个问题的本质便是自变量的相互独立性被约束条件破坏掉导致我们并不能任意使用求导后的结果。若想解决这个问题接下来就需要我们的拉格朗日乘子法。

在上述分析中我们已经知道如果我们能够还原变量的独立性，换句话说如果我们能够将约束优化问题转囮为非约束问题，那么我们便可以继续使用求偏导这样简洁明了的方法来处理问题了拉格朗日乘子法的思想便基于此。

作为一种优化算法拉格朗日乘子法的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束優化问题，或者我们可以这么看拉格朗日乘子法通过将k个约束条件转化进偏导方程组中的k个等式从而使得原问题不再出现约束。拉格朗ㄖ乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数

解决的问题模型为约束优化问题：

首先，我们先以麻省理工学院數学课程的一个实例来作为介绍拉格朗日乘数法的引子

【麻省理工学院数学课程实例】求双曲线xy=3上离远点最近的点。

首先我们根据问題的描述来提炼出问题对应的数学模型，即：

（两点之间的欧氏距离应该还要进行开方但是这并不影响最终的结果，所以进行了简化詓掉了平方）

根据上式我们可以知道这是一个典型的约束优化问题，其实我们在解这个问题时最简单的解法就是通过约束条件将其中的一個变量用另外一个变量进行替换然后代入优化的函数就可以求出极值。我们在这里为了引出拉格朗日乘数法所以我们采用拉格朗日乘數法的思想进行求解。

我们将曲线族x?+y?=c画出来如下图所示，

当曲线族中的圆与xy=3曲线进行相切时切点到原点的距离最短。也就是说當f(x,y)=c的等高线和双曲线g(x,y)相切时，我们可以得到上述优化问题的一个极值（注意：如果不进一步计算在这里我们并不知道是极大值还是极小徝）。

现在原问题可以转化为求当f(x,y)和g(x,y)相切时x,y的值是多少？

如果两个曲线相切那么它们的切线相同，即法向量是相互平行的▽f//▽/z_x_1996/article/details/