拉格朗日乘子法

莫斯

发布于 2020-09-10 10:58:41

1K0

发布于 2020-09-10 10:58:41

文章被收录于专栏：备份

0. 前言

可直接跳过本小节 以支持向量积(Support Vector Machine, SVM) 的基本型引入拉格朗日乘子法(Lagrange Multipliers).

这式子本身是一个凸二次规划问题，能直接用现成的优化计算包求解，但是我们可以有更加高效的办法，那就是使用拉格朗日乘子法，其拉格朗日函数就可以写为：

1. 最优化问题

拉格朗日乘子法是求解最优化问题中最常见的方法，一般情况下，最优化问题会碰到一下三种情况：

无约束条件
有等式约束条件
有不等式约束条件，像上文中的SVM基本型一样

情况1是最简单的情况，解决方法通常是函数对变量求导，令求导函数等于0的点可能是极值点，将结果带回原函数进行验证即可。

拉格朗日主要处理2、3两种情况，在第3种情况上需要加上KKT条件(Karush-Kuhn-Tucker)，本文将主要对拉格朗日进行详细讲述，KKT条件将在另外一篇博文进行讲解。

2. 拉格朗日乘子法

s.t. 指的是subject to ，“受限于”的意思 m 表示有m 个约束条件

则解决方法是消元法或者拉格朗日法。消元法比较简单不在赘述，这里主要讲拉格朗日法。下面主要结合实例从最短距离、等高线一一介绍：

2.1 最短距离

加入有方程, 其示意图如图所示

x^{2}y = 3

现在想要求其上的点到原点的最短距离，这里提供一条思路，那就是以原点为圆心，画半径为a 的圆

所以我们可以得知在相切点，圆的梯度向量和曲线的梯度向量平行

2.2 拉格朗日乘子法

因此由上文我们可以联立方程：

\begin{cases}\nabla f = \lambda \nabla g \\x^{2}y =3\end{cases}

可将其进行求解：

\begin{cases}\begin{pmatrix}2x \\2y\end{pmatrix} =\lambda \begin{pmatrix}2xy \\x^2\end{pmatrix} \\x^2y=3\end{cases}

这就是拉格朗日乘子法。

回到第二小节开始的地方，我们下面给出其解法：可列出方程组进行求解：

\begin{cases}\nabla f &=\lambda_{m} \nabla g_m \\g_1&=0\\g_2&=0\\g_3&=0\\\dots \\g_m&=0\end{cases}

对其进行求解也可以变形为等式进行求解：

F = f + \sum_{i=1}^{m} \lambda_{i} g_{i}

对其进行求偏导

\begin{pmatrix}\frac{F}{\partial x_1} \\\frac{F}{\partial x_2}\\\dots \\\frac{F}{\partial x_j} \\\frac{F}{\partial \lambda_{1}} \\ \frac{F}{\partial \lambda_{2}} \\ \dots \\\frac{F}{\partial \lambda_{m}} \\ \end{pmatrix}=\begin{pmatrix}0\\0\\\dots \\0\\0\\0\\\dots \\0\\\end{pmatrix}

将其结果算出就和上面的结果一样了

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/03/13 ，如有侵权请联系 cloudcommunity@tencent.com 删除

serverless