lagrange dual problem

lagrange dual problem"/>

lagrange dual problem

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

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

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

说到对偶问题，我们先从线性规划谈起，考虑以下简单的线性规划（LP）问题，我们如何求得函数的下界：

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

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

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

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

x+y≥2+2y≥0=x+3y≥2x+y≥2+2y≥0=x+3y≥2

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

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

我们如何求解？按照变换方法，我们可以获得：

a(x+y)≥2a+bx≥0+cy≥0=(a+b)x+(a+c)y≥2aa(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。这里2a2a为px+qypx+qy的下界，即px+qy≥2apx+qy≥2a永远成立，所以，我们应当使得下界最大化，找到满足约束条件a+b=pa+b=p和a+c=qa+c=q的最大值aa，才能求得左式的最小值。

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

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

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

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

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

minx∈RnsubjecttocTxAx=bGx≤hminx∈RncTxsubjecttoAx=bGx≤h

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

maxu∈Rm,v∈Rrsubjectto−bTu−hTv−ATu−GTv=cv≤0maxu∈Rm,v∈Rr−bTu−hTvsubjectto−ATu−GTv=cv≤0

因为：

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

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

3. 拉格朗日函数

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

如果我们假设集合CC为原问题的解集合，f⋆f⋆为最优解，那么对于任意uu和v≥0v≥0，我们可以获得：

f⋆=minx∈CcTx≥minx∈CL(x,u,v)≥minxL(x,u,v)=minx(c+uTA+vTG)Tx−uTb−vTh:=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)=−bTu−hTvg(u,v)=minxL(x,u,v)=−bTu−hTv。

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

g(u,v)={−bTu−hTv−∞ifc=−uTA−vTGotherwiseg(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)

其中，u≥0u≥0，同时，定义朗格朗日函数L(x,u,v)=−∞foru<0L(x,u,v)=−∞foru<0。意味着对于任意可行解xx，且u≥0u≥0，f(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为原问题的解集合，f⋆f⋆为最优解，那么对于任意xx，最小化函数L(x,u,v)L(x,u,v)可以获得函数下界：

f⋆=minx∈CcTx≥minx∈CL(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，它给定了f⋆f⋆的下界（其中u≥0u≥0），我们最大化g(u,v)g(u,v)，即可获得f⋆f⋆的逼近解。如下图，虚线表示原问题最优解f⋆f⋆，实线表征不同uu下g(u)g(u)的值，可以看出，最大化g(u)g(u)可以逼近f⋆f⋆，（图中的λλ为uu）：

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

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

minxsubjectto12xTQx+cTxAx=bx≥0minx12xTQx+cTxsubjecttoAx=bx≥0

其中，Q≻0Q≻0。

因此，拉格朗日函数为L(x,u,v)=12xTQx+cTx−uTx+vT(Ax−b)=12xTQx+(c+vTA−u)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=(c−u+ATv)Q−1x=(c−u+ATv)Q−1，函数L(x,u,v)L(x,u,v)的最小值为−12(c−u+ATv)TQ−1(c−u+ATv)−bTv−12(c−u+ATv)TQ−1(c−u+ATv)−bTv。

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

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)u≥0maxu,vg(u,v)subjecttou≥0

对于原问题的对偶问题，它有两个重要性质：

• 弱对偶性（weak duality）：无论是凸优化或非凸优化原问题，f⋆≥g⋆f⋆≥g⋆（因为f(x)≥g(u,v)f(x)≥g(u,v)）；

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

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

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

对于对偶问题，弱对偶性永远成立，更进一步，如果我们可以获得f⋆=g⋆f⋆=g⋆，那么我们就可以保证求解对偶问题获得的最优解可以变换为原问题的最优解。我们将f⋆=g⋆f⋆=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⋆=g⋆f⋆=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)−f⋆≤f(x)−g(u,v)f(x)−f⋆≤f(x)−g(u,v)，因此，如果对偶间隙为0，那么f(x)−f⋆=f(x)−g⋆f(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+C∑inξ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,w≥0v,w≥0，我们可以构建拉格朗日函数：

L(β,β0,ξ,v,w)=12∥β∥22+C∑i=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=1nc−vi−wi=CI−v−w∂L∂ξi=−∑i=1nc−vi−wi=CI−v−w。因为拉格朗日函数LL是关于ξiξi的仿射函数，所以需要CI−v−w=0CI−v−w=0，否则，min(L)=−∞min(L)=−∞，即获得约束w=CI−vw=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+ITw−∞ifwTy=0,w=CI−votherwiseg(v,w)={−12wT(diag(Y)X)(diag(Y)X)Tw+ITwifwTy=0,w=CI−v−∞otherwise

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

maxwsubjectto−12wT(diag(y)X)(diag(Y)X)Tw+ITw0≤w≤CI,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。