拉格朗日乘子法

作者: 高木秋人 | 来源:发表于2019-03-11 13:10 被阅读0次

拉格朗日乘子法
拉格朗日乘子法
拉格朗日乘子法
拉格朗日乘子法
拉格朗日乘子法和KKT条件
拉格朗日乘数法
02 SVM - 拉格朗日乘子法
最优化--拉格朗日乘子法
拉格朗日乘子法、对偶、KTT
拉格朗日乘子法与KKT条件

拉格朗日乘子法

这一节主要描述约束条件下的函数极值，涉及拉格朗日乘子法及等高线相关知识。

问题引出

求双曲线 $xy=3$ 上离原点最近的点
我们根据问题的描述来提炼出问题对应的数学模型，即：
min $f(x,y) = x^2 + y^2$ （两点之间的欧氏距离应该还要进行开方，但是这并不影响最终的结果，所以进行了简化，去掉了平方）
s.t. $xy=3$ （s.t.表示约束条件）
根据上式我们可以知道这是一个典型的约束优化问题，其实我们在解这个问题时最简单的解法就是通过约束条件将其中的一个变量用另外一个变量进行替换，然后代入优化的函数就可以求出极值。（即将 $y=\frac{3}{x}$ 待会原式，求解原式一阶导等于0的 $x$ 值，再代入）。在这里，引出拉格朗日乘子法，并利用其思想进行求解。
将 $x^2+y^2=C$ 的曲线族画出来，如下图所示，当曲线族中的圆与 $xy=3$ 曲线进行相切时，切点到原点的距离最短。也就是说，当 $f(x,y)=C$ 的等高线（这里先暂时用一下等高线的概念，后面会再进行解释）和双曲线 $g(x,y)$ 相切时，我们可以得到上述优化问题的一个极值。（有可能是极大值，也有可能是极小值）。

Contour.png
现在原问题可以转化为求当

Pair.jpg
通过求解右边的方程组我们可以获取原问题的解，即：

GradientParallel.png
绿线标出的是约束

Intuition.png
<font color=##ff0000>把拉格朗日乘子法的数学化抽象表达直观化，那就是，当函数上某点的梯度在约束曲线切向没有分量时，你就到达局部最高点了；换句话说，如果函数的梯度在约束曲线切向有分量，那么你就可以继续顺着这个分量移动以达到一个更高的高度。我们知道，约束曲线的切向是垂直于法向量的，所以这实际就是说函数的梯度要和曲线的法向量平行。</font>
约束曲线的法向是什么？假如一个约束曲线表达为 $g(x,y) = 0$ ，那么所谓曲线的法向量，其实就是曲面G在等高线 $g(x,y) = 0$ 处的梯度！
为什么梯度的方向与等高线的切线方向垂直，或者就是曲线的法向量？
假设我们的函数为

f(x,y)

，在几何上表示是一个曲面，该曲面被平面

c

（

c

为常数）所截得的曲线l方程为：

\begin{align} z &= f(x,y),\\ z &= c. \end{align}

这条曲线

l

在

xy

轴面上的投影是一条平面曲线 $Q$ ，它在

xy

平面中的方程为：

f(x,y) = c

则我们称平面曲线

Q

为函数

f(x,y)

的等高线。
由于等高线

f(x,y) = c

上任一一点的切线斜率用

\frac{dy}{dx}

来求。
则等高线

f(x,y) = c

上任一一点

(x,y)

处的法线的斜率为：

-\frac{1}{\frac{dy}{dx}} = -\frac{1}{-\frac{f_x}{f_y}} = \frac{f_y}{f_x}

，
（ $\frac{dy}{dx} = -\frac{f_x}{f_y}$ 的由来如下：
假设函数 $y = f(x)$ 由方程 $F(x,y) = 0$ 所确定，那么两边对 $x$ 求导，即得：
$\frac{\partial F}{\partial x} + (\frac{\partial F}{\partial y})(\frac{dy}{dx}) = 0$
所以 $\frac{dy}{dx} = -\frac{\frac{\partial F}{\partial x}}{\frac{\partial F}{\partial y}} = - \frac{f_x}{f_y}$ 。）
又因为梯度的计算式子为：