这个是虚坏叔叔的主站。牢记域名: [xuhss.com](拼音首字母)。首页可以搜索或: 虚幻账号

用一个例子理解拉格朗日乘数法解决等式约束优化问题

虚幻大学 虚幻 66℃ 0评论

🚀 优质资源分享 🚀

学习路线指引(点击解锁) 知识定位 人群定位
🧡 Python实战微信订餐小程序 🧡 进阶级 本课程是python flask+微信小程序的完美结合,从项目搭建到腾讯云部署上线,打造一个全栈订餐系统。
💛Python量化交易实战💛 入门级 手把手带你打造一个易扩展、更安全、效率更高的量化交易系统

首先我们来看看一个实例:

minf(x,y)=x2+y2s.t.xy=3\begin{aligned}
&min &f(x,y)&=x^2+y^2\
&s.t. &xy&=3
\end{aligned}
即:在定义域xy=3xy=3内,求f(x,y)f(x,y)的最小值。
两个函数的图像如下:

|

z=x2+y2z=x^2+y^2

|

xy=3xy=3

|

让我们把两个图像融合到一起:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3gc0AuSu-1664771529236)(https://img2022.cnblogs.com/blog/2724624/202210/2724624-20221003092941853-135057178.png%0A)]

z=x2+y2z=x^2+y^2与xy=3xy=3

在z=x2+y2z=x^2+y^2上划过的两个抛物线就是当点(x,y)(x,y)满足xy=3xy=3时的点在zz上的取值。这两条抛物线上的点(x,y,z)(x,y,z)一 一对应着二维平面上的点(x,y)(x,y)。二维平面上的两条双曲线就是当前问题的可行域(满足约束条件的点的集合)的可视化表示。现在让我们来看看对zz从最底部往上开始做水平切割,每次的切口都是一个圆,每个圆都对应着下面的二维平面上的一个圆,即等高线。随着往上攀爬,切口的圆表示的zz值越来越大,对应的等高线圆的也越来越大,当切口到那两条抛物线时,也就是在可行域内,zz取到了值,之前的值虽然都比现在的小,但是不作数,因为当时的值对应的点(x,y)(x,y)不在可行域内。继续往上,我们知道,zz的取值会变大,也就是说,只有在切口圆第一次碰到抛物线的时候,zz便已经取到了最大值,此时的切口圆对应的二维平面上的圆刚好与双曲线相切。

现在让我们回到二维的平面,来看看相切时有什么等式成立:

|

z=x2+y2z=x^2+y^2及其等高线

|

xy=3xy=3

|

|

三维视角下相切时可行域曲线与目标函数等高线

|

二维视角下相切时可行域曲线与目标函数等高线

|

在相切时取最小值,另外在相切时有以下等式成立(下式为自己的理解,没有参考书籍,可能有误):

∇x,yf(x,y)=λ→wg,λ∈R{\nabla}_{x,y} f(x,y) = \lambda \vec{w_g},\lambda \in R
其中,→wg \vec{w_g} 表示函数gg的法向量,∇x,yf(x,y) {\nabla}_{x,y} f(x,y) 为函数f(x,y)f(x,y)在相切点(x,y)(x,y)的梯度。

通过上式,我们可以得到:

(Δf(x,y)Δx,Δf(x,y)Δy)=λ(→wgx,→wgy)\left(\frac{\Delta f(x,y)}{\Delta x} ,\frac{\Delta f(x,y)}{\Delta y}\right) = \lambda \left(\vec{w_gx},\vec{w_gy} \right)
即:

2x=λy2y=λx\begin{aligned}
2x &= \lambda y\
2y &= \lambda x
\end{aligned}
另外,我们有:

xy=3xy=3
综合这三个等式,得到:

(x,y)∈{(√3,√3),(−√3,−√3)}(x,y) \in {(\sqrt{3},\sqrt{3}),(-\sqrt{3},-\sqrt{3})}
所以minf(x,y)=6min f(x,y) = 6。

其实我不是很明白为什么低维的成立后,就可以运用到高维,而且高维的情况基本上都是重复几次低维的情况即可。

另外,我们常见的拉格朗日乘数法的形式为:

minz=f(x,y)s.t.ci(x,y)=0,i=1,2,...,n\begin{aligned}
& min &&z=f(x,y) \
& s.t. &&c_i(x,y)=0, i=1,2,...,n
\end{aligned}
其写成拉格朗日函数的形式为:

min L(x,α,β)=min(f(x,y)+n∑i=1λici(x,y))min \space L(x,\alpha,\beta) = min (f(x,y) + \sum^{n}_{i=1} \lambda_i c_i(x,y))
其实可以理解为:在可行域内,找到能够使f(x,y)f(x,y)的等高线,与所有cc,同时相切的,所有(x,y)(x,y)对应的值。另外, ∑ni=1λici(x,y))\sum^{n}_{i=1} \lambda_i c_i(x,y)) 可以看作是由多个函数组成的,单个函数,让我们记作为ψ\psi。那么就可以套用上面的例子里面的推理过程,即:

(Δf(x,y)Δx,Δf(x,y)Δy)=λ(ΔψΔx,ΔψΔy)=λ1(Δc1(x,y)Δx,Δc1(x,y)Δy)+λ2(Δc2(x,y)Δx,Δc2(x,y)Δy)+⋯+λn(Δcn(x,y)Δx,Δcn(x,y)Δy)\left(\frac{\Delta f(x,y)}{\Delta x} ,\frac{\Delta f(x,y)}{\Delta y}\right) =
\lambda \left(\frac{\Delta \psi}{\Delta x} ,\frac{\Delta \psi}{\Delta y} \right) =
\lambda_1 \left(\frac{\Delta c_1(x,y)}{\Delta x} ,\frac{\Delta c_1(x,y)}{\Delta y} \right) +
\lambda_2 \left(\frac{\Delta c_2(x,y)}{\Delta x} ,\frac{\Delta c_2(x,y)}{\Delta y} \right) +
\cdots+
\lambda_n \left(\frac{\Delta c_n(x,y)}{\Delta x} ,\frac{\Delta c_n(x,y)}{\Delta y} \right)
即(注意,下面的λi\lambda_i与上面的λi\lambda_i不是同一个):

Δf(x,y)Δx=λ1Δc1(x,y)ΔxΔf(x,y)Δy=λ1Δc1(x,y)ΔyΔf(x,y)Δx=λ2Δc2(x,y)ΔxΔf(x,y)Δy=λ2Δc2(x,y)Δy ⋮Δf(x,y)Δx=λnΔcn(x,y)ΔxΔf(x,y)Δy=λnΔcn(x,y)Δy\begin{aligned}
\frac{\Delta f(x,y)}{\Delta x} &= \lambda_1 \frac{\Delta c_1(x,y)}{\Delta x}\
\frac{\Delta f(x,y)}{\Delta y} &= \lambda_1 \frac{\Delta c_1(x,y)}{\Delta y}\
\frac{\Delta f(x,y)}{\Delta x} &= \lambda_2 \frac{\Delta c_2(x,y)}{\Delta x}\
\frac{\Delta f(x,y)}{\Delta y} &= \lambda_2 \frac{\Delta c_2(x,y)}{\Delta y}\
& \space \space \vdots \
\frac{\Delta f(x,y)}{\Delta x} &= \lambda_n \frac{\Delta c_n(x,y)}{\Delta x}\
\frac{\Delta f(x,y)}{\Delta y} &= \lambda_n \frac{\Delta c_n(x,y)}{\Delta y}\
\end{aligned}
对于每组待解变量(x,y,λi)(x,y,\lambda_i),都有三个方程组:

f(x,y)=0,Δf(x,y)Δx=λnΔcn(x,y)Δx,Δf(x,y)Δy=λnΔcn(x,y)Δy\begin{aligned}
&f(x,y)=0, \
&\frac{\Delta f(x,y)}{\Delta x} = \lambda_n \frac{\Delta c_n(x,y)}{\Delta x},\
&\frac{\Delta f(x,y)}{\Delta y} = \lambda_n \frac{\Delta c_n(x,y)}{\Delta y}\
\end{aligned}
所以,是能够解出(x,y)(x,y)的。
参考文献:

拉格朗日乘数法 —— 通俗理解

转载请注明:虚坏叔叔 » 用一个例子理解拉格朗日乘数法解决等式约束优化问题

喜欢 (0)

您必须 登录 才能发表评论!