首页 > 其他分享 >用一个例子理解拉格朗日乘数法解决等式约束优化问题

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

时间:2022-10-03 09:57:05浏览次数:75  
标签:拉格朗 right frac 相切 等式 Delta 乘数 aligned lambda

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

\[\begin{aligned} &min &f(x,y)&=x^2+y^2\\ &s.t. &xy&=3 \end{aligned} \]

即:在定义域\(xy=3\)内,求\(f(x,y)\)的最小值。
两个函数的图像如下:


$z=x^2+y^2$

$xy=3$
让我们把两个图像融合到一起:

$z=x^2+y^2$与$xy=3$

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

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


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

$xy=3$

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

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

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

\[{\nabla}_{x,y} f(x,y) = \lambda \vec{w_g},\lambda \in R \]

其中,$ \vec{w_g} $ 表示函数\(g\)的法向量,$ {\nabla}_{x,y} f(x,y) $ 为函数\(f(x,y)\)在相切点\((x,y)\)的梯度。

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

\[\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) \]

即:

\[\begin{aligned} 2x &= \lambda y\\ 2y &= \lambda x \end{aligned} \]

另外,我们有:

\[xy=3 \]

综合这三个等式,得到:

\[(x,y) \in \{(\sqrt{3},\sqrt{3}),(-\sqrt{3},-\sqrt{3})\} \]

所以\(min f(x,y) = 6\)。

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

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

\[\begin{aligned} & min &&z=f(x,y) \\ & s.t. &&c_i(x,y)=0, i=1,2,...,n \end{aligned} \]

其写成拉格朗日函数的形式为:

\[min \space L(x,\alpha,\beta) = min (f(x,y) + \sum^{n}_{i=1} \lambda_i c_i(x,y)) \]

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

\[\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) \]

即(注意,下面的\(\lambda_i\)与上面的\(\lambda_i\)不是同一个):

\[\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,\lambda_i)\),都有三个方程组:

\[\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)\)的。
参考文献:

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

标签:拉格朗,right,frac,相切,等式,Delta,乘数,aligned,lambda
From: https://www.cnblogs.com/hisi-tech/p/16733341.html

相关文章

  • 用实例并可视化去理解拉格朗日对偶函数的凹性质
    考虑约束最优化问题:\[\begin{aligned}&min&&f(x)\\&s.t.&&c_i(x)\leq0,i=1,2,...,l,\\&&&h_i(x)=0,i=l+1,l+2,...,n\end{aligned}\]拉格朗日化后为:\[\begin{......
  • 拉格朗日插值优化 $dp$
    拉格朗日插值优化\(dp\)目录拉格朗日插值优化\(dp\)拉格朗日插值CF995FCowmpanyCowmpensation重要结论P4463calc拉格朗日插值对于一个\(n+1\)次多项式\(f(x)\),......
  • 拉格朗日插值原理及实现(Python)
    拉格朗日插值原理及实现(Python)目录拉格朗日插值原理及实现(Python)一.前言二.3种形式的Lagrange插值函数推导1.原始形态的Lagrange插值2.第一形式Lagrange插值3.第二形......
  • 实例87 拉格朗日插值
    #include<stdio.h>#include<stdlib.h>#include<malloc.h>doubleLAG(int,double*,double*,double);voidmain(){intn;double*x,*y,t,lag;......
  • 统计学习方法学习笔记-附录-拉格朗日对偶性
    原始问题假设\(f(x),c_i(x),h_j(x)\)是定义在\(R^n\)上的连续可微函数,考虑约束最优化问题\[\begin{aligned}\mathop{min}\limits_{x\inR^n}\&f(x)\\s.t.\&c_i(x)......
  • 四边形不等式证明简单推导
    前提条件对于\(a\leb\lec\led\),有\(f[a][c]+f[b][d]\lef[a][d]+f[b][c]\),证明内容对于\(l,r,opt\in(l,r)\),若已知:\(\forallopt'\neqopt,opt'\in(l,r),f[l][opt]+......
  • 2.2 基本不等式
    \({\color{Red}{欢迎到学科网下载资料学习}}\)【基础过关系列】2022-2023学年高一数学上学期同步知识点剖析精品讲义(人教A版2019)\({\color{Red}{跟贵哥学数学,so\qua......
  • 「学习笔记」浅谈满足四边形不等式的序列划分问题的答案凸性
    参考了Itst的博客。所以你的学习笔记就是把原文抄一遍吗首先定义“满足四边形不等式的序列划分问题”:给出\(n,k\)和一个\((n+1)×(n+1)\)的矩阵\(c_{i,j}\),你需......
  • 科力信息:智能交通“新基建”借CRM搭乘数字化快车
     当智能交通基础设施入选新基建,交通数字化转型的升级又往前迈了一大步。致力于提供智能交通整体方案的科力信息也颇具前瞻视野,在2019年年初决定深化企业数字化转型,利用......
  • 不等式视角下的策略梯度算法
    不等式视角下的策略梯度算法作者:Xingzhe.AI来自:行者AI引言强化学习(ReinforcementLearning,RL),也叫增强学习,是指一类从(与环境)交互中不断学习的问题以及解决这类问题的......