拉格朗日乘子法的来历与直观解释-低调大师

拉格朗日乘子法的来历与直观解释

2020-10-18 455

在开始挖历史考古之前，我们先来看一个简单的例子热热身。假设要我们求解函数在约束下的极值。

在使用拉格朗日乘子（或乘数）法时，引入约束函数，

g(x, y)=x^{2}+y^{2}-1=0.

构造拉格朗日函数，

\begin{aligned} \mathcal{L}(x, y, \lambda) &=f(x, y)+\lambda \cdot g(x, y) \\[0.5em] &=x+y+\lambda\left(x^{2}+y^{2}-1\right). \end{aligned}

然后，计算拉格朗日函数的梯度，

\begin{aligned} \nabla_{x, y, \lambda} \mathcal{L}(x, y, \lambda) &= \left[\frac{\partial \mathcal{L}}{\partial x}, \frac{\partial \mathcal{L}}{\partial y}, \frac{\partial \mathcal{L}}{\partial \lambda}\right]^{\top}\\[1.0em] &= \begin{bmatrix} 1+2 \lambda x\\ 1+2 \lambda y\\ x^{2}+y^{2}-1 \end{bmatrix} \end{aligned}

根据极值点梯度为，得

\begin{array}{c} \nabla_{x, y, \lambda} \mathcal{L}(x, y, \lambda)=0 \\ \qquad \\ \Updownarrow \\ \qquad \\ \left\{\begin{array}{l} 1+2 \lambda x=0 \\ 1+2 \lambda y=0 \\ x^{2}+y^{2}-1=0 \end{array}\right. \end{array}

注意，最后一个方程就是约束。

由前两个方程得，

x=y=-\frac{1}{2 \lambda}, \quad \lambda \neq 0

代入最后一个等式，得，

\lambda=\pm \frac{\sqrt{2}}{2}

从而得到的两个驻点，

\left[\frac{\sqrt{2}}{2}, \frac{\sqrt{2}}{2},-\frac{\sqrt{2}}{2}\right], \quad\left[-\frac{\sqrt{2}}{2},-\frac{\sqrt{2}}{2}, \frac{\sqrt{2}}{2}\right]

代入目标函数得，

f\left[\frac{\sqrt{2}}{2}, \frac{\sqrt{2}}{2}\right]=\sqrt{2}, \quad f\left[-\frac{\sqrt{2}}{2},-\frac{\sqrt{2}}{2}\right]=-\sqrt{2}

因此，在该约束下函数的最大值为，最小值为。对照下图，可以看到最大值出现在处，而最小值出现在处。

拉格朗日乘子法

本文只看针对单个等式约束的优化问题的拉格朗日乘子法，由目标函数和一个乘子乘以约束函数来构造如下拉格朗日函数，

\mathcal{L}(x, y, \lambda)=f(x, y)+\lambda \cdot g(x, y)

其中，前面可正可负。如果是原始约束问题的极值，则存在，使得是拉格朗日函数的驻点。

疑问

看上面的乘子法的使用过程，一气呵成，非常流畅吧。那么问题来了，为什么通过一个乘子将目标函数和约束函数一连组成新的目标函数就能搞定原问题呢。

1直观解释

在回顾拉格朗日乘子法的来历之前，先从几何或力学上来直观地解释一下它的原理。

单个函数的情况

首先，不妨来打个比喻，把函数看成一个正能量场，当质点或人处于这个正能量场中时，会受到周围值高处的吸引。假设人是好同志，受到正能量的驱使会往函数值大的地方移动，所谓人往高处走嘛。不过怎么吸引呢？周围各个方向上都要考虑啊。

这么说或许不够清晰，改一下，函数值在这里其实并不重要，重要的是跟周围值的差异。如果你所处点的值不是局部最大，自然会收到周围的吸引。那么，我们把这种差异和吸引用一个向量来表示非常合适，因为向量既有方向又有大小。这样的话，受到多大的吸引，往哪里走都明确了。那这个向量怎么确定呢？

有个很好的候选者，就是大家都知道的梯度向量。梯度表示函数在该点处的方向导数（有无穷多个）沿着该方向取得最大值，即函数在该点处沿着梯度方向变化最快，所谓差异最大。

如下图所示的一个 2D 函数极其梯度场。上方蓝色框线图是函数值，下方红色箭头表示函数的梯度场，我们可以把每个点上的梯度向量想象成力（有大小、有方向）。

上图是

f(x,y) = -(\cos^2x + \cos^2y)^2

对应的函数值以及梯度示意图。

这里我们不妨假设: 把某点的梯度向量看成该点受到的周围外力的合力。也就是在每点处，这个梯度不为 0 的话，放在该点处的质点就会运动。

再设想一下，让无数质点充满 2D 定义域平面，然后判断它们在力场的作用下是否能够保持不动？那些保持不动的点就是我们要找的极值点。

但注意，我们这里不是像梯度下降法那样让质点在梯度场的驱动下作运动，然后迭代式找到最优值，而是让质点静态地充满整个世界（定义域），然后判断每个质点是否处于一个平衡态。只在乎那些处于平衡态的质点，即在周围力场的合力作用下保持静止的那些质点，而忽略那些有移动趋势的不安定分子。

加上约束函数

上面是单个函数的情况，但是假设你所处在两个函数的梯度场中会如何呢？那么每一点都有两个力，分别对应两个函数在该点处的梯度。

但是，此时第二个函数是起到约束的作用，而现在的问题是要找到第一个函数在约束区域中的极值。

那么这种情况下，是否也有处于平衡态的质点呢？现在问题变了，这个所谓平衡态应该也有所不同了。

这个时候，在约束区域内不一定存在目标函数（第一个函数）梯度向量（合力）为 0 的情况。那质点如何处于静止状态呢？

将约束函数的梯度向量看成虚力，通过放大或缩小后与目标函数的梯度向量（力）达成一种平衡。

合力为 0，或者
合力不为 0，但力的方向与质点能移动的方向正交。

这两者合为一种，就是目标函数的梯度向量与约束函数的梯度向量平行！看下图，蓝色代表目标函数，绿色代表约束函数。如果方向不平行，质点就会沿着垂直于绿色箭头的方向（即绿线的切线方向），使得质点沿着这个方向（即往函数值更高/低处）移动。

这里重要的是力的方向，而力的大小可以通过引入一个缩放因子来平衡，这个因子就是所谓的乘子。

好了，直观解释已经讲完了，那么这个方法是因为什么背景问题提出来的呢？让我们来看看拉格朗日当初提出乘子法求解带约束的最优化问题时的背景。

2乘子法的动机

拉格朗日在 1764 年的回忆录中提出了他的这一新概念，该回忆录旨在回答巴黎学院 1762 年提出的有关月球天平动问题。1780 年，他概述了该方法的更为详尽的通用版本，并最终在 1788 年发表了这个方法。在 1811 年出版的第二版中，拉格朗日强调了乘子对约束优化的重要性。

约瑟夫·拉格朗日（Joseph-Louis Lagrange，1736~1813）

拉格朗日的想法有两个明确的来源，

第一个是伯努利（Bernoulli）虚速度原理，适用于由中心力驱动的质点系统平衡问题。
第二个来源是达朗贝尔（d'Alembert）的动力学原理。

拉格朗日是在所谓静力学的框架内引入了这种数学方法，以便确定约束问题的一般平衡态方程。

拉格朗日在《Mécanique Analytique》一书中论述了静力学，并提出了三项原理作为该主题的基础，

杠杆原理；
力的合成原理；
虚速度原理。

所谓虚速度，指的是处于平衡态的物体在平衡被中断时所获得的速度；是为了建立方程而假设的速度，不是真实速度。

如果我们仅考虑两个力和施加到质点上，并且如果和是物体受到的分别来自和的虚速度，那么如果满足如下等式，则说明质点达到平衡态。

P \frac{d p}{d t}+Q \frac{d q}{d t}=0

这个公式表示如果所有力的虚功率之和为 0，那么质点将处于平衡状态。量表示力对应的功率（单位时间内力做的功）。

在从数学角度处理该物理问题时，拉格朗日用乘以两边，即用代替。

因此，例如质点受到三个力时的平衡态对应的一般方程为，

Pdp+Qdq+Rdr=0

这样，拉格朗日能够以更一般、更简单的方式解决问题。特别是，他详细研究了约束条件下的平衡。他首先检查了带约束的质点的平衡态，如考虑两个约束。从物理角度来看，和被视为力，而和表示由这些力做的虚功。

此时，这个微分方程的一般形式是

P d p+Q d q+\cdots+\lambda d L+\mu d M \cdots=0.

这样的方程是描述平衡态的一般方程。

如果考虑正交参考系，那么每个变量将对应一个平衡态方程。例如，在方向上，有

P \frac{d p}{d x}+Q \frac{d q}{d x}+\cdots+\lambda \frac{d L}{d x}+\mu \frac{d M}{d x} \cdots=0.

该方法的优点是，它允许以与无约束问题相同的方式来处理带约束的优化问题。这种方法的第一个极其重要的结果是，对于约束的分析和数值处理被转化到平衡条件上。

拉格朗日从数学的角度指出，困难在于确定、等的值。实际上，这点不难搞定，因为加上约束本身，方程数和变量数是相同的。

举个例子，如果有两个力和以及由等式表示的约束。假设在三维空间中，将具有三个未知量和未知乘子，我们将得到四个方程，

\begin{aligned} P \frac{d p}{d x}+Q \frac{d q}{d x}+\lambda \frac{d L}{d x} &=0 \\ P \frac{d p}{d y}+Q \frac{d q}{d y}+\lambda \frac{d L}{d y} &=0 \\ P \frac{d p}{d z}+Q \frac{d q}{d z}+\lambda \frac{d L}{d z} &=0 \\ L &=0 \end{aligned}

这样，从数学的观点来看，质点的平衡问题的解似乎类似于在约束条件下求解函数的极值问题。

好了，回到上面，将函数梯度看成力是不是正是从物理的角度来解释这个数学最优值问题呢。

把上面前面几个式子中的第三项移位一下，

\begin{aligned} P \frac{d p}{d x}+Q \frac{d q}{d x} &= \hat{\lambda} \frac{d L}{d x} \\ P \frac{d p}{d y}+Q \frac{d q}{d y} &= \hat{\lambda} \frac{d L}{d y} \\ P \frac{d p}{d z}+Q \frac{d q}{d z} &= \hat{\lambda} \frac{d L}{d z} \\ L &=0 \end{aligned}

前几个方程理解为质点处于平衡状态的条件，最后一个式子（约束函数本身）看成对位子的约束，即相当于将带约束的优化问题转化为限制在一定区域内寻找处于平衡状态的质点。

3实例解读

这里借用国外某个网站讲解 SVM 的例子中的图片来可视化本文一开始的例子，但仔细看目标函数和约束函数刚好对调了。

考虑如下优化问题，

\begin{array}{ll} \underset{x, y}{\operatorname{minimize}} & f(x, y)=x^{2}+y^{2} \\ \text { subject to } & g(x, y)=x+y-1=0 \end{array}

目标函数和约束函数的等值线图如下所示，

值得注意的是，可以在一个图上同时展示这两个等值线图来可视化这两个函数。下图中，可以看到由蓝色线条描述的约束函数。这里画了目标函数的几个梯度向量（黑色箭头）以及约束函数的两个梯度向量（白色箭头）加以对比。

假定考虑的范围为。下图中，在目标函数上叠加画出了的蓝色直线，这条线也被称为可行集。

按照拉格朗日乘子法的动机分析，当两个函数的梯度向量平行时，将获得在约束下的目标函数的最小值。

在下图中，可以看到目标函数的等值线与可行集相切的点。另外，为了对比，还添加了目标函数在可行集上其他地方的梯度向量（黑色箭头）以及对应的约束梯度向量（白色箭头）。

可以看到，这个问题中，在可行集上只有在一个点处两个函数的梯度向量平行（指向相同方向），该点处的函数值正是在该约束下目标函数的最小值。

小结与下期预告

本文针对求解带单个等式约束条件的函数最优化问题的拉格朗日乘子法，探讨了它诞生的背景、大概动机以及直观解释。也许有些地方有待改进，欢迎提出纰漏或者更好的想法。

下期将送上关于矩阵与拉格朗日乘子法的一段经典联袂演出。

什么才是程序员的内功心法？

一、读大学不如上技校？在大学时代，我一度有个想法，读一个垃圾大学还不如读技校！！！而且差点退学，去读技校……幸亏我爸骂了我一顿…… 因为到了大三，除了背会了些基本概念，学校什么都没教会。教点java、C++也都是基本语法。选修的网页设计课，报的人趋之若鹜，守着时间点抢名额。到最后，也就是做一个简单的html页面，连jquery都没教会。这样的大学真的有用吗？？？耶鲁大学校长：如果一名耶鲁毕业生拥有某种很专业的技能，那就是我们教育的失败…… 我甚是不能理解。毕业了，什么都没学会，怎么找工作？？？准备喝西北风吗？？？随着年龄的增长以及经验的增加，慢慢能理解这种教育的高深之处。现在的大学教育其实是通识教育。所谓通识教育，就是让你具有往各个方向发展的潜能。而不是带着你向那个方向发展。所以，在这个基础上，大学会让你具有自学JAVA的能力，而不会带着你从java入门到精通。而大学的愿景更为宏大，他培养的是根据你自己的爱好，能够自学成才的精英，而不是像短期培训一样，单纯学会工具的使用。而这个愿景是建立在每位大学生都能够好好学习基础知识，并且业余自学某项技能的基础上的。 “再加把劲...

2020-10-20

501

多年来，我们一直在使用RNN，LSTM和GRU解决顺序问题，您突然希望我们将其全部丢弃吗？嗯，是！！所有这三种架构的最大问题是它们进行顺序处理。而且它们也不擅长处理长期依赖关系（即使使用LSTM和GRU的网络）。Transformers 提供了一种可并行处理顺序数据的方式，因此，它不仅比以前的体系结构快得多，而且在处理长期依赖性方面也非常出色。那么什么是 Transformers？这看起来很恐怖，不是吗？如果我告诉您所有这些都可以归结为一个公式，是不是就简单一些了？ Attention(Q, K, V) = ∑ᵢ (Similarity (Q, Kᵢ) * Vᵢ) 是的，上图的复杂体系结构所做的一切，都是为了确保此公式正常运行。那么这些Q，K和V是什么？这些不同类型的注意力是什么？让我们深入研究！我们将采用自下而上的方法。输入/输出的嵌入这些可以是Word2Vec，GloVe，Fastext或任何类型的词嵌入，我们可以在其中将文本转换为某种形式的有意义的向量。（PS-单词嵌入没有上下文。每个单词只有一个固定的嵌入）位置编码（PE）：在RNN（LSTM，GRU）中，时间步长...

2020-10-20

692

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。