- 周志华《机器学习》
- 如何理解拉格朗日乘子法？
1. 介绍
拉格朗日乘子法 (Lagrange multipliers)
是一种寻找多元函数在一组约束下的极值的方法。通过引入拉格朗日乘子，可将有
ddd 个变量与kkk 个约束条件的最优化问题转化为具有d+kd + kd+k 个变量的无约束优化问题求解。
2. 相关知识
2.1 与原点的最短距离
假如有方程
x2y=3x^2y=3x2y=3，它的图像如下(左一)所示。现在我们想求其上点与原点的最短距离(中图)。这里介绍一种解题思路。首先，与原点距离为aaa 的点全部在半径为aaa 的圆上(右一)：
那么，我们逐渐扩大圆的半径(左一)。显然，第一次与
x2y=3x^2y=3x2y=3 相交的点就是距离原点最近的点(中图)，此时，圆和曲线相切，也就是在该点切线相同(右一)：
至此，我们分析出了：在极值点，圆与曲线相切。
2.2 等高线/等值线
这里引入等高线的概念。这些同心圆(左一)，可以看作函数
f(x,y)=x2+y2f(x,y)=x^2+y^2f(x,y)=x2+y2 (如广泛使用的二范数，普遍会被作为约束条件)的等高线(中图)，根据梯度的性质，梯度向量：∇f=(∂f∂x∂f∂y)=(2x2y)\nabla f=\left(\begin{array}{l} \frac{\partial f}{\partial x} \\ \frac{\partial f}{\partial y} \end{array}\right)=\left(\begin{array}{l} 2 x \\ 2 y \end{array}\right)∇f=(∂x∂f∂y∂f)=(2x2y)
是等高线的法线(右一)：
另外一个函数
g(x,y)=x2yg(x,y)=x^2yg(x,y)=x2y 的等高线为左一，之前的曲线x2y=3x^2y=3x2y=3 就是其中值为333 的等高线(中图)，因此梯度向量：∇g=(∂g∂x∂g∂y)=(2xyx2)\nabla g=\left(\begin{array}{c} \frac{\partial g}{\partial x} \\ \frac{\partial g}{\partial y} \end{array}\right)=\left(\begin{array}{c} 2 x y \\ x^{2} \end{array}\right)∇g=(∂x∂g∂y∂g)=(2xyx2)
也垂直于等高线
x2y=3x^2y=3x2y=3(右一)：
梯度向量是等高线的法线，更准确地表述是：梯度与等高线的切线垂直。
2.3 小结
综上，得到两个结论：
- 在极值点，圆与曲线相切
- 梯度与等高线的切线垂直
综合可知，在相切点，圆的梯度向量和曲线的梯度向量平行。也就是梯度向量平行，用数学符号表示为
∇f=λ∇g\nabla f=\lambda \nabla g∇f=λ∇g：
3. 约束
3.1 等式约束
先考虑一个等式约束的优化问题：假定
x\boldsymbol{x}x 为ddd 维向量，欲寻找x\boldsymbol{x}x 的某个取值x∗\boldsymbol{x}^*x∗，**使目标函数f(x)f(x)f(x) 最小且同时满足g(x)=0g(x) = 0g(x)=0 的约束**。从几何角度看，该问题的目标是在由方程g(x)=0g(x) = 0g(x)=0 确定的d−1d-1d−1 维曲面上寻找能使目标函数f(x)f(x)f(x) 最小化的点此时不难得到如下结论：
- 对于约束曲面上的任意点 x \boldsymbol{x} x ， 该点的梯度 ∇ g ( x ) \nabla g(\boldsymbol{x}) ∇g(x) 正交于约束曲面(梯度与等高线切线垂直);
- 在最优点 x ∗ \boldsymbol{x}^* x∗，目标函数在该点的梯度 ∇ f ( x ∗ ) \nabla f(\boldsymbol{x}^*) ∇f(x∗) 正交于约束曲面(若梯度 ∇ f ( x ∗ ) \nabla f(\boldsymbol{x}^*) ∇f(x∗) 与约束曲面不正交，则仍可在约束曲面上移动该点使函数值进一步下降)。
由此可知，在最优点
x∗\boldsymbol{x}^*x∗，如附图B.1 所示，梯度∇g(x)\nabla g(\boldsymbol{x})∇g(x) 和∇f(x∗)\nabla f(\boldsymbol{x}^*)∇f(x∗) 的方向必相同或相反，即存在λ≠0\lambda \neq 0λ=0 使得：∇f(x∗)+λ∇g(x∗)=0\nabla f\left(\boldsymbol{x}^{*}\right)+\lambda \nabla g\left(\boldsymbol{x}^{*}\right)=0∇f(x∗)+λ∇g(x∗)=0λ\lambdaλ 称为
拉格朗日乘子
(对等式约束，
λ\lambdaλ 可能为正也可能为负)。定义
拉格朗日函数
：
L(x,λ)=f(x)+λg(x)L(\boldsymbol{x}, \lambda)=f(\boldsymbol{x})+\lambda g(\boldsymbol{x})L(x,λ)=f(x)+λg(x)
不难发现，将其对
x\boldsymbol{x}x 的偏导数∇xL(x,λ)\nabla_{\boldsymbol{x}} L(\boldsymbol{x}, \lambda)∇xL(x,λ) 置零(=0)即得式∇f(x∗)+λ∇g(x∗)=0\nabla f\left(\boldsymbol{x}^{*}\right)+\lambda \nabla g\left(\boldsymbol{x}^{*}\right)=0∇f(x∗)+λ∇g(x∗)=0，同时，将其对 λ 的偏导数∇xL(x,λ)\nabla_{\boldsymbol{x}} L(\boldsymbol{x}, \lambda)∇xL(x,λ) 置零即得约束条件g(x)=0g(\boldsymbol{x}) = 0g(x)=0。于是，原约束优化问题可转化为对拉格朗日函数L(x,λ)L(\boldsymbol{x}, \lambda)L(x,λ) 的无约束优化问题。
3.1.1 示例
这里继续使用第二节中的示例，这里引入
x2y=3x^2y=3x2y=3 这个约束条件，否则那么多等高线，不知道是哪一根，即g(x)=x2y−3g(x)=x^2y-3g(x)=x2y−3，而f(x)=x2+y2f(x)=x^2+y^2f(x)=x2+y2，联立方程：{∇f=λ∇gx2y=3\left\{\begin{array}{l} \nabla f=\lambda \nabla g \\ x^{2} y=3 \end{array}\right.{∇f=λ∇gx2y=3
解得：
{(2x2y)=λ(2xyx2)x2y=3⟹{x≈±1.61y≈1.1λ≈0.87\left\{\begin{array} { l } { ( \begin{array} { l } { 2 x } \\ { 2 y } \end{array} ) = \lambda ( \begin{array} { c } { 2 x y } \\ { x ^ { 2 } } \end{array} ) } \\ { x ^ { 2 } y = 3 } \end{array} \Longrightarrow \left\{\begin{array}{l} x \approx \pm 1.61 \\ y \approx 1.1 \\ \lambda \approx 0.87 \end{array}\right.\right.⎩⎨⎧(2x2y)=λ(2xyx2)x2y=3⟹⎩⎨⎧x≈±1.61y≈1.1λ≈0.87
3.1.2 多个等式约束
将上面的示例添加一个约束条件，如
x−y−3=0x-y-3=0x−y−3=0，则变为了求解：minx2+y2s.t.{x2y−3=0x−y−3=0\begin{array}{c} \min x^{2}+y^{2} \\ \text { s.t. }\left\{\begin{array}{l} x^{2} y-3=0 \\ x-y-3=0 \end{array}\right. \end{array}minx2+y2 s.t. {x2y−3=0x−y−3=0
从图上看约束条件是(左一)这样的，而很显然所求的距离如(中间)图片所示。那这三者的法线又有什么关系呢？
x2+y2x^2+y^2x2+y2 的法线是x2y−3x^2y-3x2y−3 和x−y−3x-y-3x−y−3 的法线的线性组合(右一蓝色法线画的有点问题？)：
假设：
{f(x,y)=x2+y2g1(x,y)=x2y−3g2(x,y)=x−y−3\left\{\begin{array}{l} f(x, y)=x^{2}+y^{2} \\ g_1(x, y)=x^{2} y-3 \\ g_2(x, y)=x-y-3 \end{array}\right.⎩⎨⎧f(x,y)=x2+y2g1(x,y)=x2y−3g2(x,y)=x−y−3
那么线性组合就表示为：
∇f=λ1∇g1+λ2∇g2\nabla f=\lambda_1 \nabla g_1+\lambda_2 \nabla g_2∇f=λ1∇g1+λ2∇g2
联立方程:
{∇f=λ1∇g1+λ2∇g2g1(x,y)=0g2(x,y)=0\left\{\begin{array}{l} \nabla f=\lambda_1 \nabla g_1+\lambda_2 \nabla g_2 \\ g_1(x, y)=0 \\ g_2(x, y)=0 \end{array}\right.⎩⎨⎧∇f=λ1∇g1+λ2∇g2g1(x,y)=0g2(x,y)=0
即可求解。
3.2 不等式约束
现在考虑不等式约束
g(x)⩽0g(\boldsymbol{x}) \leqslant 0g(x)⩽0，如附图B.1 所示，**此时最优点x∗\boldsymbol{x}^*x∗ 或在g(x)<0g(\boldsymbol{x}) < 0g(x)<0 的区域中，或在边界g(x)=0g(\boldsymbol{x}) = 0g(x)=0 上**。
- 对于 g ( x ) < 0 g(\boldsymbol{x}) < 0 g(x)<0 的情形， 约束 g ( x ) ⩽ 0 g(\boldsymbol{x}) \leqslant 0 g(x)⩽0 不起作用，可直接通过条件 ∇ f ( x ) = 0 \nabla f(x)=0 ∇f(x)=0 来获得最优点；这等价于将 λ \lambda λ 置零然后对 ∇ x L ( x , λ ) \nabla_{\boldsymbol{x}} L(\boldsymbol{x}, \lambda) ∇xL(x,λ) 置零得到最优点。
g ( x ) = 0 g(x) = 0 g(x)=0 的情形类似于上面等式约束的分析，但需注意的是，**此时 ∇ f ( x ∗ ) \nabla f(\boldsymbol{x}^*) ∇f(x∗) 的方向必与 ∇ g ( x ∗ ) \nabla g(\boldsymbol{x}^*) ∇g(x∗) 相反(下面小节会说明原因)，即存在常数 λ > 0 \lambda>0 λ>0 使得 ∇ f ( x ∗ ) + λ ∇ g ( x ∗ ) = 0 \nabla f\left(\boldsymbol{x}^{*}\right)+\lambda \nabla g\left(\boldsymbol{x}^{*}\right)=0 ∇f(x∗)+λ∇g(x∗)=0**。
3.2.1 上述两种情况示例
我们要求以下同心圆的最小值：
那肯定就是原点了，半径为
000 能得到最小值。
3.2.1.1 情况一
我们给它添加一个不等式约束，也就是求：
minimizef(x,y)subject toh(x,y)=x+y≤1\begin{aligned} & \text{minimize} & & f(x,y) \\ & \text{subject to} & & h(x,y)=x+y \le 1 \end{aligned}minimizesubject tof(x,y)h(x,y)=x+y≤1
可以看到，这个不等式约束实际上包含了原点：
所以这个约束等于没有，依然求解：
∇f=0⟹(x,y)=(0,0)\nabla f=0\implies (x,y)=(0,0)∇f=0⟹(x,y)=(0,0)
3.2.1.2 情况二
换一个不等式约束：
minimizef(x,y)subject toh(x,y)=x+y≤−2\begin{aligned} & \text{minimize} & & f(x,y) \\ & \text{subject to} & & h(x,y)=x+y \le -2 \end{aligned}minimizesubject tof(x,y)h(x,y)=x+y≤−2
不等式约束看起来如左一这样。因为同心圆是凸函数的等高线，所以等高线的值是(中图)这么排列的，在不等式约束下，最小值是在边缘相切的地方取得。这里和用等式
h(x,y)=x+y=−2h(x,y)=x+y=-2h(x,y)=x+y=−2 进行约束效果是一样的：
因此还是可以通过解方程组求出答案：
{∇f+μ∇h=0h(x,y)=x+y=−2\begin{cases} \nabla f+\mu\nabla h=0 \\ h(x,y)=x+y=-2 \end{cases}{∇f+μ∇h=0h(x,y)=x+y=−2
可以发现不等式实际上带来了新的条件：同心圆是凸函数的等高线，等高线的值如下排列，所以在相切处，法线也就是
∇f\nabla f∇f 的方向如下(法线也就是梯度，指向增长最快的方向，也就是等高线的值变大的方向)。而凸函数h(x,y)h(x,y)h(x,y) 的法线∇h\nabla h∇h 也一样指向h(x,y)h(x,y)h(x,y) 增长的方向，这个方向正好和∇f\nabla f∇f 相反：
因此
∇f+μ∇h=0,μ≥0\nabla f+\mu\nabla h=0,\mu \ge 0∇f+μ∇h=0,μ≥0 其中，μ≥0\mu \ge 0μ≥0 就表明∇f\nabla f∇f，∇h\nabla h∇h 方向相反。
因此刚才的方程组可以再增加一个条件：
{∇f+μ∇h=0h(x,y)=x+y=−2μ≥0\begin{cases} \nabla f+\mu\nabla h=0 \\ h(x,y)=x+y=-2 \\ \mu \ge 0 \end{cases}⎩⎨⎧∇f+μ∇h=0h(x,y)=x+y=−2μ≥0
整合上面两种情形，必满足
λg(x)=0\lambda g(\boldsymbol{x})=0λg(x)=0。因此，在约束g(x)⩽0g(\boldsymbol{x}) \leqslant 0g(x)⩽0 下最小化f(x)f(\boldsymbol{x})f(x) ，**可转化为在如下约束下**最小化式L(x,λ)=f(x)+λg(x)L(\boldsymbol{x}, \lambda)=f(\boldsymbol{x})+\lambda g(\boldsymbol{x})L(x,λ)=f(x)+λg(x) 的拉格朗日函数：{g(x)⩽0;λ⩾0;λjgj(x)=0.\left\{\begin{array}{l} g(\boldsymbol{x}) \leqslant 0 ; \\ \lambda \geqslant 0 ; \\ \lambda_{j} g_{j}(\boldsymbol{x})=0 . \end{array}\right.⎩⎨⎧g(x)⩽0;λ⩾0;λjgj(x)=0.
该式被称为
Karush-Kuhn-Tucker(KKT)条件
。
3.2.2 多个约束
上述做法可推广到多个约束。考虑具有
mmm 个**等式约束**和nnn 个**不等式约束**，且可行域D⊂Rd\mathbb{D} \subset \mathbb{R}^{d}D⊂Rd 非空的优化问题：
Eq.1：
minxf(x)s.t.hi(x)=0(i=1,…,m),gj(x)⩽0(j=1,…,n).\begin{array}{ll} \min _{\boldsymbol{x}} & f(\boldsymbol{x}) \\ \text { s.t. } & h_{i}(\boldsymbol{x})=0 \quad(i=1, \ldots, m), \\ & g_{j}(\boldsymbol{x}) \leqslant 0 \quad(j=1, \ldots, n) . \end{array}minx s.t. f(x)hi(x)=0(i=1,…,m),gj(x)⩽0(j=1,…,n).
引入拉格朗日乘子
λ=(λ1,λ2,…,λm)T\boldsymbol{\lambda}=\left(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{m}\right)^{\mathrm{T}}λ=(λ1,λ2,…,λm)T 和μ=(μ1,μ2,…,μn)T\boldsymbol{\mu}=\left(\mu_{1}, \mu_{2}, \ldots, \mu_{n}\right)^{\mathrm{T}}μ=(μ1,μ2,…,μn)T，相应的拉格朗日函数为：
Eq.2：
L(x,λ,μ)=f(x)+∑i=1mλihi(x)+∑j=1nμjgj(x)L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu})=f(\boldsymbol{x})+\sum_{i=1}^{m} \lambda_{i} h_{i}(\boldsymbol{x})+\sum_{j=1}^{n} \mu_{j} g_{j}(\boldsymbol{x})L(x,λ,μ)=f(x)+i=1∑mλihi(x)+j=1∑nμjgj(x)
由不等式约束引入的
KKT 条件
(
j=1,2,...,nj=1,2,...,nj=1,2,...,n)为：{∇f+∑i=1mλi∇hi(x)+∑j=1nμj∇gj(x)=0hi(x)=0,i=1,2,...,mgj(x)⩽0,j=1,2,...,nμj⩾0μjgj(x)=0.\left\{\begin{array}{l} \nabla f+ \sum_{i=1}^{m} \lambda_{i} \nabla h_{i}(\boldsymbol{x})+\sum_{j=1}^{n} \mu_{j} \nabla g_{j}(\boldsymbol{x}) =0\\ h_{i}(\boldsymbol{x}) = 0, i=1,2,...,m \\ g_{j}(\boldsymbol{x}) \leqslant 0, j=1,2,...,n \\ \mu_{j} \geqslant 0 \\ \mu_{j} g_{j}(\boldsymbol{x})=0 . \end{array}\right.⎩⎨⎧∇f+∑i=1mλi∇hi(x)+∑j=1nμj∇gj(x)=0hi(x)=0,i=1,2,...,mgj(x)⩽0,j=1,2,...,nμj⩾0μjgj(x)=0.
一个优化问题可以从两个角度来考察，即
主问题(primal problem)
和
对偶问题(dual proble)
。对主问题 Eq.1，基于式 Eq.2，其拉格朗日
对偶函数(dual function)
Γ:Rm×Rn↦R\Gamma: \mathbb{R}^{m} \times \mathbb{R}^{n} \mapsto \mathbb{R}Γ:Rm×Rn↦R 定义为：Γ(λ,μ)=infx∈DL(x,λ,μ)=infx∈D(f(x)+∑i=1mλihi(x)+∑j=1nμjgj(x))\begin{aligned} \Gamma(\boldsymbol{\lambda}, \boldsymbol{\mu}) &=\inf _{\boldsymbol{x} \in \mathbb{D}} L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) \\ &=\inf _{\boldsymbol{x} \in \mathbb{D}}\left(f(\boldsymbol{x})+\sum_{i=1}^{m} \lambda_{i} h_{i}(\boldsymbol{x})+\sum_{j=1}^{n} \mu_{j} g_{j}(\boldsymbol{x})\right) \end{aligned}Γ(λ,μ)=x∈DinfL(x,λ,μ)=x∈Dinf(f(x)+i=1∑mλihi(x)+j=1∑nμjgj(x))
在推导对偶问题时，常通过将拉格朗日乘子
L(x,λ,μ)L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu})L(x,λ,μ) 对x\boldsymbol{x}x 求导并令导数为000，来获得对偶函数的表达形式(是不是可以理解成，主问题是不带λ\lambdaλ 和μ\muμ 的，将主问题转换成带拉格朗日乘子的对偶问题，以方便求解)。
若
x~∈D\tilde{\boldsymbol{x}} \in \mathbb{D}x~∈D 为主问题 Eq.1 可行域中的点，则对任意μ⪰0\boldsymbol{\mu} \succeq 0μ⪰0 (μ⪰0\boldsymbol{\mu} \succeq 0μ⪰0 表示μ\boldsymbol{\mu}μ 的分量均为非负)和λ\boldsymbol{\lambda}λ 都有：∑i=1mλihi(x)+∑j=1nμjgj(x)⩽0\sum_{i=1}^{m} \lambda_{i} h_{i}(\boldsymbol{x})+\sum_{j=1}^{n} \mu_{j} g_{j}(\boldsymbol{x}) \leqslant 0i=1∑mλihi(x)+j=1∑nμjgj(x)⩽0
进而有：
Γ(λ,μ)=infx∈DL(x,λ,μ)⩽L(x~,λ,μ)⩽f(x~).\Gamma(\boldsymbol{\lambda}, \boldsymbol{\mu})=\inf _{\boldsymbol{x} \in \mathbb{D}} L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) \leqslant L(\tilde{\boldsymbol{x}}, \boldsymbol{\lambda}, \boldsymbol{\mu}) \leqslant f(\tilde{\boldsymbol{x}}) .Γ(λ,μ)=x∈DinfL(x,λ,μ)⩽L(x~,λ,μ)⩽f(x~).
若主问题 Eq.1 的最优值为
p∗p^{*}p∗, 则对任意μ⪰0\boldsymbol{\mu} \succeq 0μ⪰0 和λ\boldsymbol{\lambda}λ 都有Γ(λ,μ)⩽p∗,\Gamma(\boldsymbol{\lambda}, \boldsymbol{\mu}) \leqslant p^{*},Γ(λ,μ)⩽p∗,
即对偶函数给出了主问题最优值的下界(
inf\infinf).显然，这个下界取决于μ\boldsymbol{\mu}μ 和λ\boldsymbol{\lambda}λ 的值。于是，一个很自然的问题是：基于对偶函数能获得的最好下界是什么？这就引出了优化问题：
Eq.3：
maxλ,μΓ(λ,μ)s.t.μ⪰0\max _{\boldsymbol{\lambda}, \boldsymbol{\mu}} \Gamma(\boldsymbol{\lambda}, \boldsymbol{\mu}) \text { s.t. } \boldsymbol{\mu} \succeq 0λ,μmaxΓ(λ,μ) s.t. μ⪰0
Eq.3 就是主问题 Eq.1 的对偶问题，其中
λ\boldsymbol{\lambda}λ 和μ\boldsymbol{\mu}μ 称为
对偶变量(dual variable)
。无论主问题 Eq.1 的凸性如何，对偶问题 Eq.3 始终是凸优化问题。
考虑式 Eq.3 的最优值
d∗d^{*}d∗, 显然有d∗⩽p∗d^{*} \leqslant p^{*}d∗⩽p∗, 这称为
弱对偶性(weak duality)
成立；若
d∗=p∗d^{*}=p^{*}d∗=p∗，则称为
强对偶性(strong duality)
成立，此时由对偶问题能获得主问题的最优下界。Eq.1。但是，若主问题为凸优化问题，如式 Eq.1 中
f(x)f(\boldsymbol{x})f(x) 和gj(x)g_{j}(\boldsymbol{x})gj(x) 均为凸函数，hi(x)h_{i}(\boldsymbol{x})hi(x) 为仿射函数，且其可行域中至少有一点使不等式约束严格成立，**则此时强对偶性成立**。值得注意的是，在强对偶性成立时，将拉格朗日函数分别对原变量和对偶变量求导，再并令导数等于零，即可得到原变量与对偶变量的数值关系。于是，对偶问题解决了，主问题也就解决了。
本文转载自: https://blog.csdn.net/qq_28087491/article/details/126134823
版权归原作者 泠山 所有， 如有侵权，请联系我们删除。
版权归原作者 泠山 所有， 如有侵权，请联系我们删除。