lagrange dual problem

2023-11-29 04:40
文章标签 lagrange problem dual

本文主要是介绍lagrange dual problem,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

很高兴阿森纳能在欧冠上战胜拜仁,在虎扑上看到这样的一句话,颇有感触,借来作为这篇博文的开始,生活中我们需要一些勇气去追寻自己的理想。回到本篇内容上,对偶是个神奇的东西,从文学角度而言,对偶和对仗属于一种修辞手法,即用字数相等,语义对称的方法来表征想法或抒发情感。“凡心所向,素履所往,生如逆旅,一苇以航”或者“棋逢对手,将遇良才”都可看成是一种对偶。

但是,本文是要阐述在数学问题上的对偶问题,它是优化问题中非常重要的方法,类似于文学的对偶,也是一种配对方式,只不过是将某种数学结构AA转换为另一种对等的数学结构BB。在优化问题中,可以将非凸问题转化为凸优化问题进行求解。虽然文学上和数学上表达对偶的意思相差甚远,但是我觉得二者在各自领域的重要性是可以比拟的。

update: 在完成本篇博文时,拜仁5:1战胜阿森纳,小组出线堪忧。

说到对偶问题,我们先从线性规划谈起,考虑以下简单的线性规划(LP)问题,我们如何求得函数的下界:

minx,ysubjecttox+3yx+y2x,y0minx,yx+3ysubjecttox+y≥2x,y≥0

实际上,我们可以从两个角度求解这个问题:首先,我们可以采用图解法找寻问题的解。下图中蓝线代表x+3y=0x+3y=0的直线,黑线表示约束x+y=2x+y=2,我们可以通过移动蓝线的位置,使得蓝线右上方的所有点xxyy满足约束,因此,直至蓝线移至红线位置才能满足上述LP问题的约束,而黄线代表的x+3y=0.6x+3y=0.6则不能满足约束,因为点(x,y)=(0,0.2)(x,y)=(0,0.2)不满足x+y2x+y≥2的条件。

因此,通过作图,移动目标函数直线的位置,我们都能获得上述LP问题的最小值,即为2。

同样,我们也可以利用以下变换获得目标函数的最小值:

x+y2+2y0=x+3y2x+y≥2+2y≥0=x+3y≥2

很明显,x+3yx+3y的最小值为2。如果我们泛化上述LP问题为:

minx,ysubjecttopx+qyx+y2x,y0minx,ypx+qysubjecttox+y≥2x,y≥0

我们如何求解?按照变换方法,我们可以获得:

a(x+y)2a+bx0+cy0=(a+b)x+(a+c)y2aa(x+y)≥2a+bx≥0+cy≥0=(a+b)x+(a+c)y≥2a

因此,我们只要使得a+b=pa+b=p,同时a+c=qa+c=q,那么上述问题的最优解为2a2a。这里2a2apx+qypx+qy的下界,即px+qy2apx+qy≥2a永远成立,所以,我们应当使得下界最大化,找到满足约束条件a+b=pa+b=pa+c=qa+c=q的最大值aa,才能求得左式的最小值。

综上所述,上述LP问题就转换为求下面形式的最大值:

maxa,b,csubjectto2aa+b=pa+c=qa,b,c0maxa,b,c2asubjecttoa+b=pa+c=qa,b,c≥0

我们即称上述变换为原问题(Primal)的对偶(dual)问题。

2. 线性规划问题的对偶问题

对于一般形式的线性规划问题:

minxRnsubjecttocTxAx=bGxhminx∈RncTxsubjecttoAx=bGx≤h

我们可以获得其对偶问题:

maxuRm,vRrsubjecttobTuhTvATuGTv=cv0maxu∈Rm,v∈Rr−bTu−hTvsubjectto−ATu−GTv=cv≤0

因为:

uTAx=bTu+vTGxhTv=(ATuGTv)TxbTuhTv−uTAx=−bTu+−vTGx≥−hTv=(−ATu−GTv)Tx≥−bTu−hTv

如果cc满足c=ATuGTvc=−ATu−GTv,那么我们可以获得LP问题解得下界bTuhTv−bTu−hTv

3. 拉格朗日函数

根据LP对偶问题的构建方法,我们可以令L(x,u,v):=cTx+uT(Axb)+vT(Gxh)L(x,u,v):=cTx+uT(Ax−b)+vT(Gx−h),其中v0v≥0。因为,Axb=0Ax−b=0且对于v,vt(Gxh)0∀v,vt(Gx−h)≤0,因此,L(x,u,v)cTxL(x,u,v)≤cTx

如果我们假设集合CC为原问题的解集合,ff⋆为最优解,那么对于任意uuv0v≥0,我们可以获得:

f=minxCcTxminxCL(x,u,v)minxL(x,u,v)=minx(c+uTA+vTG)TxuTbvTh:=g(u,v)f⋆=minx∈CcTx≥minx∈CL(x,u,v)≥minxL(x,u,v)=minx(c+uTA+vTG)Tx−uTb−vTh:=g(u,v)

对于上式,minxL(x,u,v)minxL(x,u,v)为关于xx的线性函数,因此,如果c+uTA+vTGc+uTA+vTG不等于0,那么对于所有xx,函数L(x,u,v)L(x,u,v)最小值为−∞,所以,想要保证求得原问题的最小值,我们必须保证c+uTA+vTG=0c+uTA+vTG=0,此时,g(u,v)=minxL(x,u,v)=bTuhTvg(u,v)=minxL(x,u,v)=−bTu−hTv

综上所述,我们可以获得函数g(u,v)g(u,v)的一般形式:

g(u,v)={bTuhTvifc=uTAvTGotherwiseg(u,v)={−bTu−hTvifc=−uTA−vTG−∞otherwise

现在我们最大化函数g(u,v)g(u,v),获得原问题的紧致下界(tightest bound),这与上面之前定义的对偶问题完全一致。同时,这种变换或者解释方法可以适用于任意优化问题上,甚至是非凸优化问题。我们可以根据有约束的优化问题获得函数L(x,u,v)L(x,u,v),然后求解minxL(x,u,v)minxL(x,u,v)得到函数g(u,v)g(u,v),即为原问题的对偶问题。

综上所述,对于一般有约束的优化问题,如下:

minxsubjecttof(x)hi(x)0,i=1,,mli(x)=0,j=1,,rminxf(x)subjecttohi(x)≤0,i=1,…,mli(x)=0,j=1,…,r

无论f(x)f(x)是否为凸函数,我们都可以定义拉格朗日函数(Lagrangian)为:

L(x,u,v)=f(x)+i=1muihi(x)+j=1rvjlj(x)L(x,u,v)=f(x)+∑i=1muihi(x)+∑j=1rvjlj(x)

其中,u0u≥0,同时,定义朗格朗日函数L(x,u,v)=foru<0L(x,u,v)=−∞foru<0。意味着对于任意可行解xx,且u0u≥0f(x)L(x,u,v)f(x)≥L(x,u,v)。下图是Boyd凸优化一书中给出拉格朗日函数的实例图:

图中,实线表示函数f(x)f(x),虚线表示函数h(x)h(x),为约束,点线表示不同u,vu,v下的函数L(x,u,v)L(x,u,v)。根据约束信息,我们可以获得函数可行解域为[-0.46,0.46],在该区域下f(x)L(x,u,v)f(x)≥L(x,u,v)

同样,如果我们假设集合CC为原问题的解集合,ff⋆为最优解,那么对于任意xx,最小化函数L(x,u,v)L(x,u,v)可以获得函数下界:

f=minxCcTxminxCL(x,u,v)minxL(x,u,v):=g(u,v)f⋆=minx∈CcTx≥minx∈CL(x,u,v)≥minxL(x,u,v):=g(u,v)

我们称函数g(u,v)g(u,v)拉格朗日对偶函数(Lagrange dual function),对于对偶可行解u,vu,v,它给定了ff⋆的下界(其中u0u≥0),我们最大化g(u,v)g(u,v),即可获得ff⋆的逼近解。如下图,虚线表示原问题最优解ff⋆,实线表征不同uug(u)g(u)的值,可以看出,最大化g(u)g(u)可以逼近ff⋆,(图中的λλuu):

3. 对偶函数实例:二次规划

这里,我们用二次函数的优化问题作为一个例子来说明如何获得拉格朗日对偶函数,我们定义二次规划为:

minxsubjectto12xTQx+cTxAx=bx0minx12xTQx+cTxsubjecttoAx=bx≥0

其中,Q0Q≻0

因此,拉格朗日函数L(x,u,v)=12xTQx+cTxuTx+vT(Axb)=12xTQx+(c+vTAu)Tx+vTbL(x,u,v)=12xTQx+cTx−uTx+vT(Ax−b)=12xTQx+(c+vTA−u)Tx+vTb,对于形如ax2+bx+cax2+bx+c的二次函数,我们可以获得函数的根为x=b2ax=−b2a,即x=(cu+ATv)Q1x=(c−u+ATv)Q−1,函数L(x,u,v)L(x,u,v)的最小值为12(cu+ATv)TQ1(cu+ATv)bTv−12(c−u+ATv)TQ−1(c−u+ATv)−bTv

所以,我们可以获得拉格朗日对偶函数g(u,v)=minxRnL(x,u,v)=12(cu+ATv)TQ1(cu+ATv)bTvg(u,v)=minx∈RnL(x,u,v)=−12(c−u+ATv)TQ−1(c−u+ATv)−bTv,其中u0u≥0vv为任意值。

4. 拉格朗日对偶问题

拉格朗日对偶问题是指对于原问题:

minxsubjecttof(x)hi(x)0,i=1,,mli(x)=0,j=1,,rminxf(x)subjecttohi(x)≤0,i=1,…,mli(x)=0,j=1,…,r

我们通过构造对偶函数g(u,v)g(u,v),然后最大化该对偶函数的优化问题,即:

maxu,vsubjecttog(u,v)u0maxu,vg(u,v)subjecttou≥0

对于原问题的对偶问题,它有两个重要性质:

  • 弱对偶性(weak duality):无论是凸优化或非凸优化原问题,fgf⋆≥g⋆(因为f(x)g(u,v)f(x)≥g(u,v));

  • 对偶问题是凸优化问题:无论原问题是凸优化还是非凸,因为lj(x)lj(x)为凸函数

这里需要指出的是,是不是我们可以获得任意原问题的对偶问题,这样就可以采用之前提到过的下降算法等来求解该凸优化问题?

答案是否定的,虽然无论原问题为何种形式,其对偶问题永远是凸优化问题,但是这里的关键并不是说不能用下降算法求解,而是我们对于非凸问题一般无法获得或者较难获得其对偶问题的表达式g(u,v)g(u,v),这就限制了我们对于非凸优化问题的求解方法。

对于对偶问题,弱对偶性永远成立,更进一步,如果我们可以获得f=gf⋆=g⋆,那么我们就可以保证求解对偶问题获得的最优解可以变换为原问题的最优解。我们将f=gf⋆=g⋆形式成为强对偶性(strong duality)

Slater’s condition:如果原(primal)问题为凸优化问题(即:f,h1,,hmf,h1,…,hm为凸函数,l1,,lrl1,…,lr是仿射函数),同时存在至少一个可行解满足h1(x)<0,,hm(x)<0,l1(x)==lr(x)=0h1(x)<0,…,hm(x)<0,l1(x)=…=lr(x)=0,那么该问题的强对偶性成立,即f=gf⋆=g⋆

因此,根据强对偶性的定义和成立条件,我们可以获得以下性质:

  • LP问题对偶问题的对偶问题为原问题(the dual of the dual LP is the primal LP);

  • 如果LP问题存在可行解,那么LP问题满足具有强对偶性;

根据强对偶性定义,我们可以衍伸出对偶间隙(duality gap)的定义,对偶间隙是指f(x)g(u,v)f(x)−g(u,v),很明显,f(x)ff(x)g(u,v)f(x)−f⋆≤f(x)−g(u,v),因此,如果对偶间隙为0,那么f(x)f=f(x)gf(x)−f⋆=f(x)−g⋆,这时,u,vu,v和对应获得的xx分别为对偶问题和原问题的最优解。

对偶间隙的最大用途是作为算法停止迭代的条件,即如果我们想要保证f(x)fϵf(x)−f⋆≤ϵ,那么需要f(x)g(u,v)ϵf(x)−g(u,v)≤ϵ

5. 对偶问题实例:SVM对偶问题

之前我们提到过,SVM问题是:

minβ,β0,ξsubjectto12β22+Cinξiξ0,i=1,,nyi(xTiβ+β0)1ξi,i=1,,nminβ,β0,ξ12∥β∥22+C∑inξisubjecttoξ≥0,i=1,…,nyi(xiTβ+β0)≥1−ξi,i=1,…,n

引入对偶变量(dual variables),v,w0v,w≥0,我们可以构建拉格朗日函数:

L(β,β0,ξ,v,w)=12β22+Ci=1nξi=1nviξ+i=1nwi(1ξyi(xTiβ+β0))L(β,β0,ξ,v,w)=12∥β∥22+C∑i=1nξ−∑i=1nviξ+∑i=1nwi(1−ξ−yi(xiTβ+β0))

如想获得拉格朗日对偶函数,我们需要对β,β0,ξβ,β0,ξ求导。

(1)对β0β0求导,我们获得:Lβ0=i=1nyiwi=wTy∂L∂β0=−∑i=1nyiwi=wTy。因为拉格朗日函数LL是关于β0β0的仿射函数,所以wTy=0wTy=0,否则,min(L)=min(L)=−∞,即获得约束wTy=0wTy=0

(2)对ξiξi求导,我们获得:Lξi=i=1ncviwi=CIvw∂L∂ξi=−∑i=1nc−vi−wi=CI−v−w。因为拉格朗日函数LL是关于ξiξi的仿射函数,所以需要CIvw=0CI−v−w=0,否则,min(L)=min(L)=−∞,即获得约束w=CIvw=CI−v

(3)对ββ求导,我们获得:Lβ=(12βTβwT(diag(Y)X)β)∂L∂β=(12βTβ−wT(diag(Y)X)β)′,因此,β=wT(diag(Y)X)β=wT(diag(Y)X)。因为,拉格朗日函数LL是关于ββ的二次函数,所以存在最小值12wT(diag(y)X)(diag(Y)X)Tw+ITw−12wT(diag(y)X)(diag(Y)X)Tw+ITw

综上所述,通过最小化β,β0,ξβ,β0,ξ,我们获得拉格朗日函数L(β,β0,ξ,v,w)L(β,β0,ξ,v,w)的拉格朗日对偶函数g(v,w)g(v,w)

g(v,w)={12wT(diag(Y)X)(diag(Y)X)Tw+ITwifwTy=0,w=CIvotherwiseg(v,w)={−12wT(diag(Y)X)(diag(Y)X)Tw+ITwifwTy=0,w=CI−v−∞otherwise

又因为ξξ为原问题的松弛因子,且v0v≥0,因此我们可以消除对偶问题中的松弛因子vv(slack variable),SVM对偶优化问题就变为:

maxwsubjectto12wT(diag(y)X)(diag(Y)X)Tw+ITw0wCI,wTy=0maxw−12wT(diag(y)X)(diag(Y)X)Tw+ITwsubjectto0≤w≤CI,wTy=0

如果SVM原问题满足Slater’s Condition,那么SVM具有强对偶性(事实上SVM具有强对偶性),我们可以通过求解对偶问题的最优解,进而获得原问题最优解β=(diag(Y)X)Twβ=(diag(Y)X)Tw

这篇关于lagrange dual problem的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/431486

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

11991 - Easy Problem from Rujia Liu?

题意: 输入一串整型数列,再输入两个数k,v,输出第k个v的序号。不存在则输出0,如第一个样例 8 41 3 2 2 4 3 2 11 3 //第1个3,序号为2,输出22 4 //第2个4,不存在,输出03 2 //第3个2,序号为7,输出74 2 思路: struct num {

HDU 1016 Prime Ring Problem (深搜)

OJ题目 : click here ~~ 大概题意:n个数,形成一个环,使得相邻两个数的和为素数。以1开始,按字典序输出序列。 很简单的深搜。 AC_CODE int n;int visit[22];int num[22];int len;bool Is_prime(int x){for(int i = 2;i*i <= x;i++)if(x%i == 0) return

ModuleNotFoundError: No module named ‘diffusers.models.dual_transformer_2d‘解决方法

Python应用运行报错,部分错误信息如下: Traceback (most recent call last): File “\pipelines_ootd\unet_vton_2d_blocks.py”, line 29, in from diffusers.models.dual_transformer_2d import DualTransformer2DModel ModuleNotF

LVM 'Can’t open /dev/sdb1 exclusively. Mounted filesystem?' Problem

在将几块盘做LVM时,遇到一个之前都没遇到过的问题: root@ubuntu:~# pvcreate /dev/sdc1Can't open /dev/sdc1 exclusively. Mounted filesystem? 首先第一反应就是查看这个分区是否已经在使用了,但是没有。 查看硬盘的一些信息: root@ubuntu:~# cat /proc/partitionsmajo

【HDU】3861 The King’s Problem 强连通缩点+有向图最小路径覆盖

传送门:【HDU】3861 The King’s Problem 题目分析:首先强连通缩点,因为形成一个环的王国肯定在一条路径中,这样才能保证拆的少。 然后缩点后就是DAG图了,由于题目要求的是最小路径覆盖,那么二分匹配即可。 代码如下: #include <cstdio>#include <cstring>#include <algorithm>#includ

【ZOJ】3362 Beer Problem 最小费用流

传送门:【ZOJ】3362 Beer Problem 题目分析:这道题本来应该很快就AC的,但是!因为我以前犯的一个致命错误导致我这题一天了到现在才调出来!唉。。失策。。貌似给的模板也有这个错误。。。马上就去改。。但是这个错误竟然还能过掉那么多的题。。害我还要一题一题的改回去。。 本题就是赤裸裸的最小费用流。 新建汇点t(源点即1),将所有的n-1个城市和汇点建边,容量为无穷大,

【HDU】4975 A simple Gaussian elimination problem. 网络流——行列建边

传送门:【HDU】4975 A simple Gaussian elimination problem. 题目分析:这题和某一场的多校的题目出奇的像啊!重要的是我一开始还以为不可能会出一样的题。。结果迟迟没写啊。。。后来觉得实在想不出什么对策了,虽然觉得给的是0~9很特殊,但是利用不起来,果断还是敲了网络流了。。首先建图很简单,源点向行建边,容量为行和,列向汇点建边,容量为列和,然后所有的

Splay树(区间更新)—— POJ 3468 A Simple Problem with Integers

对应POJ 题目:点击打开链接 A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072KTotal Submissions: 72765 Accepted: 22465Case Time Limit: 2000MS Description You have N integers, A1