Processing math: 0%

带约束的优化(KKT、对偶、ADMM)

带约束的优化问题,KKT条件

微积分的教程里已经可以接触到一些用Lagrange乘数法解条件极值的知识和实例。这里我们考虑更一般的带约束优化问题
minf(x)s.t. h(x)=0,  g(x)0,xΩ.\begin{aligned} \min &\quad f(\boldsymbol x)\\ \text{s.t. }&\quad \boldsymbol h(\boldsymbol x)=\boldsymbol 0,\; \boldsymbol g(\boldsymbol x)\geqslant\boldsymbol 0,\\ &\quad \boldsymbol x\in\Omega. \end{aligned}其中h,g\boldsymbol h,\boldsymbol g分别是m(n),pm(\leqslant n),p维映射(并假设f,h,gf,\boldsymbol h,\boldsymbol g光滑),它们的两个约束称作是函数约束,而xΩ\boldsymbol x\in\Omega称作是集合约束。我们一般淡化集合约束的考虑,着重考虑函数约束。这里面有个概念十分重要——active constraint,以后翻译为“积极约束”,指的是函数约束取等时的那些约束(等式约束也就都看作积极约束)。积极约束能够使我们在很多情况下能够把问题划归为更简单的只带等式约束的优化问题:若x\boldsymbol x^\ast是局部最优解,那么它当然也是只留下积极约束的优化问题的局部解,这是因为对非积极约束gi(x)>0g _ i(\boldsymbol x^\ast)>0,那么在x\boldsymbol x^\ast的邻域也有gi(x)>0g _ i(\boldsymbol x)>0,所以去掉非积极约束不影响邻域的可行性(feasibility)。进而,如果去掉非积极约束、且将积极约束全部改为等式约束,那么x\boldsymbol x^\ast也仍是局部最优解。

带约束优化问题中有知名的Karush-Kuhn-Tucker(KKT)条件:

Karush-Kuhn-Tucker条件:令x\boldsymbol x^\ast是上述带约束的优化问题的极小值点,且在该点LICQ (linear independence constraint qualification) 成立,那么存在mm维向量λ\boldsymbol \lambdapp维非负向量μ0\boldsymbol \mu\geqslant 0使得
f(x)h(x)λg(x)μ=0,μTg(x)=0.\begin{gathered} \nabla f(\boldsymbol x^\ast)-\nabla \boldsymbol h(\boldsymbol x^\ast)\boldsymbol \lambda-\nabla \boldsymbol g(\boldsymbol x^\ast)\boldsymbol \mu=\boldsymbol 0,\\ \boldsymbol \mu^\mathsf T\boldsymbol g(\boldsymbol x^\ast)=0. \end{gathered}
后面再给出解释与证明,首先做一些准备工作。

切平面

设曲面S:h(x)=0S:\boldsymbol h(\boldsymbol x)=\boldsymbol 0,我们定义在x\boldsymbol x^\ast上其切平面(tangent plane)为:SS上过点x\boldsymbol x^\ast的所有曲线的关于该点的切向量全体。我们知道在微积分中,曲线x=x(t)\boldsymbol x=\boldsymbol x(t)tt的切向量已定义为x(t)\boldsymbol x'(t),与此同时也常接触子空间M={dJh(x)d=0}M=\{\boldsymbol d\mid J\boldsymbol h(\boldsymbol x^\ast)\boldsymbol d=\boldsymbol 0\}(这里JhJ\boldsymbol h是指h\boldsymbol h的Jacobi矩阵),下面将证明在一定条件下这个可以作为切平面的等价刻画。

x\boldsymbol x^\ast满足h(x)=0\boldsymbol h(\boldsymbol x^\ast)=\boldsymbol 0,如果Jh(x)J\boldsymbol h(\boldsymbol x^\ast)行满秩,即h1(x),,hm(x)\nabla h _ 1(\boldsymbol x ^ \ast),\dots,\nabla h _ m(\boldsymbol x^\ast)线性独立,那么我们称x\boldsymbol x^\ast是一个正则点(regular point)、满足正则条件。如果h\boldsymbol h是一个仿射函数,即h(x)=Ax+b\boldsymbol h(\boldsymbol x)=A\boldsymbol x+\boldsymbol b,那么正则条件即为AA满秩,其判定与x\boldsymbol x无关。

定理:对于曲面S:h(x)=0S:\boldsymbol h(\boldsymbol x)=\boldsymbol 0上的正则点x\boldsymbol x^\ast,切平面等于
M={dJh(x)d=0}.M=\{\boldsymbol d\mid J\boldsymbol h(\boldsymbol x^\ast)\boldsymbol d=\boldsymbol 0\}.
考虑其证明。记切平面为TT,则TMT\subseteq M,因为只需要在h(x(t))=0\boldsymbol h(\boldsymbol x(t))=\boldsymbol 0两边对tt求导并令t=0t=0就得到Jh(x)x(0)=0J\boldsymbol h(\boldsymbol x^\ast)\boldsymbol x'(0)=\boldsymbol 0,故只需证MTM\subseteq T,即证对任何dM\boldsymbol d\in M,存在SS上过点x\boldsymbol x^\ast的曲线x(t)\boldsymbol x(t)使得x(0)=d\boldsymbol x'(0)=\boldsymbol d。下面的构造略具技巧性,令F(t,u)=h[x+td+Jh(x)Tu]\boldsymbol F(t,\boldsymbol u)=\boldsymbol h[\boldsymbol x^\ast+t\boldsymbol d+J\boldsymbol h(\boldsymbol x^\ast)^\mathsf T\boldsymbol u],其中uRm\boldsymbol u\in\mathbb R^{m},要考虑方程F(t,u)=0\boldsymbol F(t,\boldsymbol u)=\boldsymbol 0。我们可以看到F(0,0)=0\boldsymbol F(0,\boldsymbol 0)=\boldsymbol 0;对F\boldsymbol F关于u\boldsymbol u求偏导,得Jh[x+td+Jh(x)Tu]Jh(x)TJ\boldsymbol h[\boldsymbol x^\ast+t\boldsymbol d+J\boldsymbol h(\boldsymbol x^\ast)^\mathsf T\boldsymbol u]J\boldsymbol h(\boldsymbol x^\ast)^\mathsf T,在(t,u)=(0,0)(t,\boldsymbol u)=(0,\boldsymbol 0)JuF(0,0)=Jh(x)Jh(x)TJ _ {\boldsymbol u}\boldsymbol F(0,\boldsymbol 0)=J\boldsymbol h(\boldsymbol x^\ast)J\boldsymbol h(\boldsymbol x^\ast)^\mathsf T。注意到正则条件已假设Jh(x)J\boldsymbol h(\boldsymbol x^\ast)行满秩,所以这个偏导是可逆的,由隐函数定理,存在t=0t=0附近定义的连续可微u(t)\boldsymbol u(t)使得F(t,u(t))=0\boldsymbol F(t,\boldsymbol u(t))=\boldsymbol 0u(0)=0\boldsymbol u(0)=\boldsymbol 0。现在就可以考察SS上的曲线x(t)=x+td+Jh(x)Tu(t)\boldsymbol x(t)=\boldsymbol x^\ast+t\boldsymbol d+J\boldsymbol h(\boldsymbol x^\ast)^\mathsf T\boldsymbol u(t),对h(x(t))=0\boldsymbol h(\boldsymbol x(t))=\boldsymbol 0两边对tt求导并令t=0t=0,得Jh(x)[y+Jh(x)Tu(0)]=0J\boldsymbol h(\boldsymbol x^\ast)[\boldsymbol y+J\boldsymbol h(\boldsymbol x^\ast)^\mathsf T\boldsymbol u'(0)]=\boldsymbol 0,由dM\boldsymbol d\in M可知u(0)=0\boldsymbol u'(0)=\boldsymbol 0,于是x(0)=d+Jh(x)Tu(0)=d\boldsymbol x'(0)=\boldsymbol d+J\boldsymbol h(\boldsymbol x^\ast)^\mathsf T\boldsymbol u'(0)=\boldsymbol d,从而dT\boldsymbol d\in T。故T=MT=M即证。

很多时候,TMT\subsetneqq MTT是不依赖曲面的表示的,而MM则可能随h\boldsymbol h的变动而变动。我们考虑h(x1,x2)=x1h(x _ 1,x _ 2)=x _ 1,那么h(x1,x2)=0h(x _ 1,x _ 2)=0表示x2x _ 2轴,此时其上任意一点均正则;而若令h(x1,x2)=x12h(x _ 1,x _ 2)=x _ 1^2,那么h(x1,x2)=0h(x _ 1,x _ 2)=0仍表示x2x _ 2轴:x1=0x _ 1=0,但Jh(0,x2)=(2x1,0)=0Jh(0,x _ 2)=(2x _ 1,0)=\boldsymbol 0,故没有点满足正则条件,且此时M=R2M=\mathbb R^2

一阶条件的准备工作

命题:设曲面S:h(x)=0S:\boldsymbol h(\boldsymbol x)=\boldsymbol 0x\boldsymbol x^\astSSff的极值点,且满足正则条件,那么对任何y\boldsymbol y
Jh(x)d=0    Jf(x)d=0.J\boldsymbol h(\boldsymbol x^\ast)\boldsymbol d=\boldsymbol 0\implies Jf(\boldsymbol x^\ast)\boldsymbol d=0.就是说极值点处切平面和ff的Jacobian正交。

证明是简单的。设SS上的曲线x(t)\boldsymbol x(t)满足x(0)=x\boldsymbol x(0)=\boldsymbol x^\astx(0)=d\boldsymbol x'(0)=\boldsymbol d,那么t=0t=0是函数f(x(t))f(\boldsymbol x(t))的极值点,此即Jf(x)d=0Jf(\boldsymbol x^\ast)\boldsymbol d=0

接下来,我们断言:f(x)\nabla f(\boldsymbol x^\ast)可被h\boldsymbol hx\boldsymbol x^\ast的梯度线性表示,此即

定理:设x\boldsymbol x^\ast是在约束h(x)=0\boldsymbol h(\boldsymbol x)=\boldsymbol 0ff的极值点,且满足正则条件,那么存在λRm\boldsymbol \lambda\in\mathbb R^m使得
f(x)h(x)λ=0.\nabla f(\boldsymbol x^\ast)-\nabla \boldsymbol h(\boldsymbol x^\ast)\boldsymbol \lambda=\boldsymbol 0.其中(2h)λ=λ12h1++λm2hm(\nabla^2\boldsymbol h)\boldsymbol \lambda=\lambda _ 1\nabla^2 h _ 1+\dots+\lambda _ m\nabla^2 h _ m

考虑其证明。在线性规划的理论的基础上,证明是十分简单的。上面的命题表明,线性规划问题
maxf(x)Ty,s.t. h(x)Ty=0\begin{aligned}\max &\quad \nabla f(\boldsymbol x^\ast)^\mathsf T\boldsymbol y,\\\text{s.t. }&\quad \nabla\boldsymbol h(\boldsymbol x^\ast)^\mathsf T\boldsymbol y=\boldsymbol 0\end{aligned}有最大值00,所以该问题的对偶问题可行,这表明此定理成立。

Lagrangian

如果用Lagrange乘数的语言来表述,引入Lagrange函数
L(x,λ)=f(x)λTh(x),L(\boldsymbol x,\boldsymbol \lambda)=f(\boldsymbol x)-\boldsymbol \lambda^\mathsf T\boldsymbol h(\boldsymbol x),这个一阶必要条件就是
xL(x,λ)=0,λL(x,λ)=0.\begin{gathered} \nabla _ \boldsymbol x L(\boldsymbol x,\boldsymbol \lambda)=\boldsymbol 0,\\ \nabla _ \boldsymbol \lambda L(\boldsymbol x,\boldsymbol \lambda)=\boldsymbol 0. \end{gathered}(第二个等式只是约束的等价表述)

Lagrange函数可以看作是目标函数加上一个惩罚违背约束的惩罚项,而诸λi\lambda _ i就是关于hi(x)=0h _ i(\boldsymbol x)=0的惩罚权重了。取适当的λi\lambda _ i时,一个带约束的优化问题可被视作一个无约束的优化问题来解决。考虑特殊情况,当ff是凸函数、h\boldsymbol h是仿射函数AxbA\boldsymbol x-\boldsymbol b,那么L(x,λ)L(\boldsymbol x,\boldsymbol \lambda)也是关于x\boldsymbol x的凸函数(对每个给定的λ\boldsymbol \lambda),因而若x\boldsymbol x^\ast满足xL=0\nabla _ \boldsymbol x L=\boldsymbol 0,那么对同一个λ\boldsymbol \lambda它是不带约束地最小化L(x,λ)L(\boldsymbol x,\boldsymbol \lambda)的最小值点;若进一步还有h(x)=0\boldsymbol h(\boldsymbol x^\ast)=\boldsymbol 0,那么x\boldsymbol x^\ast也是带约束h(x)=0\boldsymbol h(\boldsymbol x)=\boldsymbol 0的最小化f(x)f(\boldsymbol x)的最小值点。

定理:对等式约束,一阶必要条件也是充分的,当ff是凸函数且h\boldsymbol h是仿射函数时。

二阶条件的准备工作

f,hC2f,\boldsymbol h\in C^2,则有

定理(必要条件):设x\boldsymbol x^\ast是在约束h(x)=0\boldsymbol h(\boldsymbol x)=\boldsymbol 0ff的极值点,且满足正则条件,那么存在λRm\boldsymbol \lambda\in\mathbb R^m使得
f(x)h(x)λ=0,\nabla f(\boldsymbol x^\ast)-\nabla \boldsymbol h(\boldsymbol x^\ast)\boldsymbol \lambda=\boldsymbol 0,又设切平面M={dJh(x)d=0}M=\{\boldsymbol d\mid J\boldsymbol h(\boldsymbol x^\ast)\boldsymbol d=\boldsymbol 0\},那么在MM2f(x)2h(x)λ\nabla^2 f(\boldsymbol x^\ast)-\nabla^2\boldsymbol h(x^\ast)\boldsymbol \lambda半正定,其中(2h)λ=λ12h1++λm2hm(\nabla^2\boldsymbol h)\boldsymbol \lambda=\lambda _ 1\nabla^2 h _ 1+\dots+\lambda _ m\nabla^2 h _ m,简而言之,对任何dM\boldsymbol d\in M
dTxx2L(x,λ)d0.\boldsymbol d^\mathsf T\nabla^2 _ {\boldsymbol {xx}} L(\boldsymbol x^\ast,\boldsymbol \lambda)\,\boldsymbol d\geqslant0.

.
考虑其证明。考虑S:h(x)=0S:\boldsymbol h(\boldsymbol x)=\boldsymbol 0上过点x\boldsymbol x^\ast的曲线x=x(t)\boldsymbol x=\boldsymbol x(t),满足x(0)=x\boldsymbol x(0)=\boldsymbol x^\ast,那么t=0t=0是函数f(x(t))f(\boldsymbol x(t))的极小值点,二阶导在00必非负,一阶导是Jf(x(t))x(t)Jf(\boldsymbol x(t))\boldsymbol x'(t),再对tt求导就是Jf(x(t))x(t)+x(t)T2f(x(t))x(t)Jf(\boldsymbol x(t))\boldsymbol x''(t)+\boldsymbol x'(t)^\mathsf T\nabla^2 f(\boldsymbol x(t))\boldsymbol x'(t),二阶导非负即这个数当t=0t=0非负;另一方面,对等式λTh(x(t))=0\boldsymbol \lambda^\mathsf T\boldsymbol h(\boldsymbol x(t))=0两边对tt求导,得λTJh(x(t))x(t)=0\boldsymbol \lambda^\mathsf TJ\boldsymbol h(\boldsymbol x(t))\boldsymbol x'(t)=0,再对tt求导,得λTJh(x(t))x(t)+x(t)T[2h(x(t))λ]x(t)=0\boldsymbol \lambda^\mathsf TJ\boldsymbol h(\boldsymbol x(t))\boldsymbol x''(t)+\boldsymbol x'(t)^\mathsf T[\nabla^2\boldsymbol h(\boldsymbol x(t))\boldsymbol \lambda]\boldsymbol x'(t)=0,将此式取反加进f(x(t))f(\boldsymbol x(t))二阶导非负的式子,并利用一阶条件,得到x(0)Txx2L(x,λ)x(0)0\boldsymbol x'(0)^\mathsf T\nabla^2 _ {\boldsymbol x\boldsymbol x}\mathcal L(\boldsymbol x^\ast,\boldsymbol \lambda)\boldsymbol x'(0)\geqslant0,而x(0)\boldsymbol x'(0)可取MM中的任何向量,故定理得证。

.

定理(充分条件):设x,λ\boldsymbol x^\ast,\boldsymbol \lambda满足h(x)=0\boldsymbol h(\boldsymbol x^\ast)=\boldsymbol 0f(x)h(x)λ=0\nabla f(\boldsymbol x^\ast)-\nabla \boldsymbol h(\boldsymbol x^\ast)\boldsymbol \lambda=\boldsymbol 0,矩阵xx2L(x,λ)\nabla^2 _ {\boldsymbol {xx}} L(\boldsymbol x^\ast,\boldsymbol \lambda)M={dJh(x)d=0}M=\{\boldsymbol d\mid J\boldsymbol h(\boldsymbol x^\ast)\boldsymbol d=\boldsymbol 0\}上正定,即对任何MM上的非零向量d\boldsymbol d
dTxx2L(x,λ)d>0,\boldsymbol d^\mathsf T\nabla^2 _ {\boldsymbol {xx}} L(\boldsymbol x^\ast,\boldsymbol \lambda)\boldsymbol d>0,那么,x\boldsymbol x^\ast是满足h(x)=0\boldsymbol h(\boldsymbol x)=\boldsymbol 0约束的ff的严格极小值点。

.
考虑其证明,反证之。若不然,存在可行域上的{yk}\{\boldsymbol y _ k\}使得ykx\boldsymbol y _ k\to\boldsymbol x^\astf(yk)f(x)f(\boldsymbol y _ k)\leqslant f(\boldsymbol x^\ast)。设δk=ykx\boldsymbol \delta _ k=\boldsymbol y _ k-\boldsymbol x^\astδk=ykx\delta _ k=\|\boldsymbol y _ k-\boldsymbol x^\ast\|,那么{(ykx)/δk}\{(\boldsymbol y _ k-\boldsymbol x^\ast)\mathbin/\delta _ k\}作为有界点列存在收敛子列,不妨就设这个点列收敛到s\boldsymbol s^\ast,则(ykx)/δk=s+rk(\boldsymbol y _ k-\boldsymbol x^\ast)\mathbin/\delta _ k=\boldsymbol s^\ast+\boldsymbol r _ k,其中rk0\boldsymbol r _ k\to\boldsymbol 0;由定义,0=h(yk)h(x)=Jh(x)(ykx)+r(ykx)\boldsymbol 0=\boldsymbol h(\boldsymbol y _ k)-\boldsymbol h(\boldsymbol x^\ast)=J\boldsymbol h(\boldsymbol x^\ast)(\boldsymbol y _ k-\boldsymbol x^\ast)+\boldsymbol r(\boldsymbol y _ k-\boldsymbol x^\ast),其中r(x)=o(x)(x0)\boldsymbol \|r(\boldsymbol x)\|=o(\|\boldsymbol x\|)\, (\boldsymbol x\to\boldsymbol 0),故r(δk)=o(δk)\|\boldsymbol r(\boldsymbol \delta _ k)\|=o(\delta _ k)0=Jh(x)(s+rk)+r(δk)/δk\boldsymbol 0=J\boldsymbol h(\boldsymbol x^\ast)(\boldsymbol s^\ast+\boldsymbol r _ k)+\boldsymbol r(\boldsymbol \delta _ k)\mathbin/\delta _ k,再令kk\to\inftyJh(x)s=0J\boldsymbol h(\boldsymbol x^\ast)\boldsymbol s^\ast=\boldsymbol 0

现在考虑二阶展开,对h\boldsymbol h0=hi(yk)=hi(x)+δkJhi(x)δk+δk22δkT(2hi(ηi))δk0=h _ i(\boldsymbol y _ k)=h _ i(\boldsymbol x^\ast)+\delta _ kJh _ i(\boldsymbol x^\ast)\boldsymbol\delta _ k +\frac{\delta _ k^2}{2}\boldsymbol \delta _ k^\mathsf T(\nabla^2 h _ i(\boldsymbol \eta _ i))\boldsymbol \delta _ k,对ff0f(yk)f(x)=δkJf(x)δk+δk22δkT(2f(η))δk0\geqslant f(\boldsymbol y _ k)-f(\boldsymbol x^\ast)=\delta _ k Jf(\boldsymbol x^\ast)\boldsymbol \delta _ k+\frac{\delta _ k^2}{2}\boldsymbol \delta _ k^\mathsf T(\nabla^2f(\boldsymbol \eta))\boldsymbol \delta _ k。适当变换后相加即知0δk22δkT(2f(η)λ12h1(η1)λm2hm(ηm))δk0\geqslant\frac{\delta _ k^2}{2}\boldsymbol \delta _ k^\mathsf T(\nabla^2 f(\boldsymbol \eta)-\lambda _ 1\nabla^2h _ 1(\boldsymbol \eta _ 1)-\dots-\lambda _ m\nabla^2\boldsymbol h _ m(\boldsymbol \eta _ m))\boldsymbol \delta _ k,两边除以δk4\delta _ k^4后令kk\to\infty(s)Txx2L(x,λ)s0(s^\ast)^\mathsf T\nabla^2 _ {\boldsymbol {xx}}L(\boldsymbol x^\ast,\boldsymbol \lambda)\boldsymbol s^\ast\leqslant0,矛盾。

一阶条件

现在回到问题
minf(x)s.t. h(x)=0,  g(x)0,xΩ.\begin{aligned} \min &\quad f(\boldsymbol x)\\ \text{s.t. }&\quad \boldsymbol h(\boldsymbol x)=\boldsymbol 0,\; \boldsymbol g(\boldsymbol x)\geqslant\boldsymbol 0,\\ &\quad \boldsymbol x\in\Omega. \end{aligned}并设f,g,hC1f,\boldsymbol g,\boldsymbol h\in C^1

定义(LICQ):linear independence constraint qualification (LICQ) 是指,积极约束的梯度{ci(x),ciA(x)}\{\nabla c _ i(\boldsymbol x),\, c _ i\in \mathcal A(\boldsymbol x)\}线性独立(其中A\mathcal A代表积极约束的集合)。

现在可以再次给出KKT条件:

Karush-Kuhn-Tucker条件:令x\boldsymbol x^\ast是上述带约束的优化问题的极小值点,且在该点LICQ (linear independence constraint qualification) 成立,那么存在mm维向量λ\boldsymbol \lambdapp维非负向量μ0\boldsymbol \mu\geqslant 0使得
f(x)h(x)λg(x)μ=0,μTg(x)=0.\begin{gathered}\nabla f(\boldsymbol x^\ast)-\nabla \boldsymbol h(\boldsymbol x^\ast)\boldsymbol \lambda-\nabla \boldsymbol g(\boldsymbol x^\ast)\boldsymbol \mu=\boldsymbol 0,\\\boldsymbol \mu^\mathsf T\boldsymbol g(\boldsymbol x^\ast)=0.\end{gathered}

第二条等式意味着μi\mu _ i非零仅当对应不等式约束是积极的,在线性规划中已经见过这种形式的关系了——complementary slackness,互补松弛条件。

考虑其证明。x\boldsymbol x^\ast是约束集下的极小值点,那么将积极约束里的不等约束全部改为等式约束,也仍是极小值点。对于这些等式约束,x\boldsymbol x^\ast是正则点,由前面的准备工作,存在Lagrange乘数,所以我们可知:第一条方程可以成立——对非积极约束我们可以令μi=0\mu _ i=0,这样第二条也跟着成立了。只剩下μ\boldsymbol \mu的非负性。假设存在kk,使得积极约束gk(x)=0g _ k(\boldsymbol x^\ast)=0成立,但对应的μk<0\mu _ k<0。考虑约束A{gk}\mathcal A\setminus\{g _ k\},对应曲面SS'和切平面MM',由于在x\boldsymbol x^\ast有LICQ成立,gk\nabla g _ k不能被其余的积极约束的梯度线性表示。切平面MM'中的向量是和其余梯度正交的向量集合,即MM'是正交补,那么切平面里应有向量d\boldsymbol d使得gk(x)Td\nabla g _ k(\boldsymbol x^\ast)^\mathsf T\boldsymbol d非零,否则gk(x)\nabla g _ k(\boldsymbol x^\ast)MM'正交,必可被约束A{gk}\mathcal A\setminus\{g _ k\}的梯度线性表示;由于MM'是线性空间,可设gk(x)Td>0\nabla g _ k(\boldsymbol x^\ast)^\mathsf T\boldsymbol d>0,和KKT条件里第一条等式作内积,得f(x)Td=μkgk(x)Td<0\nabla f(\boldsymbol x^\ast)^\mathsf T\boldsymbol d=\mu _ k\nabla g _ k(\boldsymbol x _ \ast)^\mathsf T\boldsymbol d<0——这意味着d\boldsymbol dff的下降方向,很容易构造矛盾。令x(t)\boldsymbol x(t)SS'上过点x\boldsymbol x^\ast的曲线,满足x(0)=x\boldsymbol x(0)=\boldsymbol x^\astx(0)=d\boldsymbol x'(0)=\boldsymbol d,那么对充分小的t0t\geqslant0x(t)\boldsymbol x(t)是可行的——它是SS'上的曲线 其余积极约束仍不变,且gk(x(t))>0g _ k(\boldsymbol x(t))>0(因为gk(x)Td\nabla g _ k(\boldsymbol x^\ast)^\mathsf T\boldsymbol d为正)。然而,对f(x(t))f(\boldsymbol x(t))关于tt求导并令t=0t=0,得f(x)Td\nabla f(\boldsymbol x^\ast)^\mathsf T\boldsymbol d,前面计算得负数,说明x\boldsymbol x^\ast并非假设的极小值点。矛盾。

Lagrangian

同样可以引进Lagrange函数
L(x,λ,μ)=f(x)λTh(x)μTg(x).L(\boldsymbol x,\boldsymbol \lambda,\boldsymbol \mu)=f(\boldsymbol x)-\boldsymbol \lambda^\mathsf T\boldsymbol h(\boldsymbol x)-\boldsymbol \mu^\mathsf T\boldsymbol g(\boldsymbol x).
同样地,Lagrange函数可以看作是无约束的目标函数,只是带上了两个惩罚违背约束的惩罚项。对于不等约束,若gi(x)>0g _ i(\boldsymbol x)>0则不应有惩罚,μi=0\mu _ i=0,否则就应该是正值,使得要让目标函数最小化gig _ i的值必须增大。

现在一阶必要条件可以表述为:

问题的原始约束(OVC) The Original Variable Constraints of Problem
Lagrange乘数的符号约束(MSC) The Multiplier Sign Constraints:λ\boldsymbol \lambda符号“自由”、μ0\boldsymbol \mu\geqslant0(一般地,与g\boldsymbol g同号)
Lagrangian导数条件(LDC) The Lagrangian Derivative Condition:
xL(x,λ,μ)=f(x)h(x)λg(x)μ=0.\nabla _ {\boldsymbol x}L(\boldsymbol x,\boldsymbol \lambda,\boldsymbol\mu )=\nabla f(\boldsymbol x)-\nabla\boldsymbol h(\boldsymbol x)\boldsymbol \lambda-\boldsymbol g(\boldsymbol x)\boldsymbol \mu=\boldsymbol 0.互补松弛条件(CSC) The Complementary Slackness Condition:μigi(x)=0\mu _ i g _ i(\boldsymbol x)=0i=1,,pi=1,\dots,p

考虑特殊情况,f,gf,-\boldsymbol g是凸函数且h\boldsymbol h是仿射函数:AxbA\boldsymbol x-\boldsymbol b,那么对给定的λ\boldsymbol \lambda和非负μ0\boldsymbol \mu\geqslant0,Lagrange函数对x\boldsymbol x也是凸函数,对这组Lagrange乘数x\boldsymbol x^\ast满足LDC,故是无约束优化L(x,λ,μ)L(\boldsymbol x,\boldsymbol \lambda,\boldsymbol \mu)的最小值点。

定理:若f,gf,-\boldsymbol g是凸函数且h\boldsymbol h是仿射函数,一阶必要条件是充分的。

和前面只有等式约束相比需要些步骤来证明。
0L(x,λ,μ)L(x,λ,μ)=f(x)f(x)(μ)T(g(x)g(x))=f(x)f(x)Aμi(gi(x)gi(x))=f(x)f(x)Aμigi(x)f(x)f(x).\begin{aligned} 0&\leqslant L(\boldsymbol x,\boldsymbol \lambda^\ast,\boldsymbol \mu^\ast)-\boldsymbol L(\boldsymbol x^\ast,\boldsymbol \lambda^\ast,\boldsymbol \mu^\ast)\\ &= f(\boldsymbol x)-f(\boldsymbol x^\ast)-\boldsymbol (\mu^\ast)^\mathsf T(\boldsymbol g(\boldsymbol x)-\boldsymbol g(\boldsymbol x^\ast))\\ &=f(\boldsymbol x)-f(\boldsymbol x^\ast)-\sum\nolimits _ {\mathcal A}\mu _ i(g _ i(\boldsymbol x)-g _ i(\boldsymbol x^\ast))\\ &=f(\boldsymbol x)-f(\boldsymbol x^\ast)-\sum\nolimits _ \mathcal A\mu _ ig _ i(\boldsymbol x)\\ &\leqslant f(\boldsymbol x)-f(\boldsymbol x^\ast). \end{aligned}

二阶条件

二阶必要条件:设f,g,hC2f,\boldsymbol g,\boldsymbol h\in C^2x\boldsymbol x^\astff的极小值点且满足LICQ,那么存在λ\boldsymbol \lambda和非负的μ0\boldsymbol \mu\geqslant0使得KKT条件成立且
xx2L(x,λ,μ)=2f(x)2h(x)λ2g(x)μ\nabla^2 _ {\boldsymbol {xx}}L(\boldsymbol x^\ast,\boldsymbol \lambda,\boldsymbol\mu )=\nabla^2 f(\boldsymbol x^\ast)-\nabla^2\boldsymbol h(\boldsymbol x^\ast)\boldsymbol \lambda-\nabla^2\boldsymbol g(\boldsymbol x^\ast)\boldsymbol \mux\boldsymbol x^\ast的积极约束的切平面上是半正定的。

对于充分条件,只在切平面上作限定是不够的,因为可能有退化的(degenerate)不等约束(即积极约束的对应Lagrange乘数为零)。

二阶充分条件:设f,g,hC2f,\boldsymbol g,\boldsymbol h\in C^2,下述条件是x\boldsymbol x^\astff极小值点的充分条件:存在λ\boldsymbol \lambda和非负μ0\boldsymbol \mu\geqslant0μTg(x)=0\boldsymbol \mu^\mathsf T\boldsymbol g(\boldsymbol x^\ast)=0f(x)h(x)λg(x)μ=0\nabla f(\boldsymbol x^\ast)-\nabla \boldsymbol h(\boldsymbol x^\ast)\boldsymbol \lambda-\nabla\boldsymbol g(\boldsymbol x^\ast)\boldsymbol \mu=\boldsymbol 0,且Hesse矩阵
xx2L(x,λ,μ)=2f(x)2h(x)λ2g(x)μ\nabla^2 _ {\boldsymbol {xx}}L(\boldsymbol x^\ast,\boldsymbol \lambda,\boldsymbol\mu )=\nabla^2 f(\boldsymbol x^\ast)-\nabla^2\boldsymbol h(\boldsymbol x^\ast)\boldsymbol \lambda-\nabla^2\boldsymbol g(\boldsymbol x^\ast)\boldsymbol \muMM'正定,这里MM'
{dh(x)Td=0,gi(x)Td=0,i{igi(x)=0,μi>0}}.\{\boldsymbol d\mid\nabla \boldsymbol h(\boldsymbol x^\ast)^\mathsf T\boldsymbol d=0,\, \nabla g _ i(\boldsymbol x^\ast)^\mathsf T\boldsymbol d=0,\, \forall i\in\{i\mid g _ i(\boldsymbol x^\ast)=0,\, \mu _ i>0\}\}.

可以看到,如果严格松弛互补条件(strict complementary slackness)成立,那么MM'就是MM(积极约束对应的切平面)。

对偶

Lagrange对偶

对偶理论在优化中非常重要。这里先初窥门径。为方便,先考虑不等约束的问题
minf(x)s.t. g(x)0,xΩ.\begin{aligned} \min&\quad f(\boldsymbol x)\\ \text{s.t. }&\quad \boldsymbol g(\boldsymbol x)\geqslant0,\\ &\quad \boldsymbol x\in\Omega. \end{aligned}这里Ω\Omega只考虑凸集,f,gf,\boldsymbol g当然在其上也要有定义。假设g\boldsymbol gpp维的,且问题至少有一个可行点。定义一个primal函数
ω(z)=inf  {f(x)g(x)z,xΩ}.\omega(\boldsymbol z)=\inf\; \{f(\boldsymbol x)\mid \boldsymbol g(\boldsymbol x)\geqslant \boldsymbol z,\, \boldsymbol x\in \Omega\}.其定义域就是D={zxΩ,g(x)z}D=\{\boldsymbol z\mid \exist \boldsymbol x\in\Omega,\, \boldsymbol g(\boldsymbol x)\geqslant\boldsymbol z\}。这个函数图像与因变量坐标轴的交点就是目标函数的最值。对偶就是基于在primal函数图像之下的超平面的考虑而来。

不等约束的优化,对偶函数定义为ϕ(μ)=inf  {f(x)μTg(x)xΩ}(μ0)\phi(\boldsymbol \mu)=\inf\; \{f(\boldsymbol x)-\boldsymbol \mu^\mathsf T\boldsymbol g(\boldsymbol x)\mid \boldsymbol x\in\Omega\}\, (\boldsymbol \mu\geqslant0),设所有使对偶函数有限的非负μ\boldsymbol \mu组成DD,那么:

命题:在DDϕ-\phi总是凸函数,由此DD是凸集。

只需利用f(x)(αμ1+(1α)μ2)Tg(x)=αf(x)αμ1Tg(x)+(1α)f(x)(1α)μ2Tg(x)f(\boldsymbol x)-(\alpha\boldsymbol \mu _ 1+(1-\alpha)\boldsymbol \mu _ 2)^\mathsf T\boldsymbol g(\boldsymbol x)=\alpha f(\boldsymbol x)-\alpha\boldsymbol \mu _ 1^\mathsf T\boldsymbol g(\boldsymbol x)+(1-\alpha)f(\boldsymbol x)-(1-\alpha)\boldsymbol \mu _ 2^\mathsf T\boldsymbol g(\boldsymbol x),然后两边同时取下确界即可。

现在令ϕ=supϕ(μ)\phi^\ast=\sup\phi(\boldsymbol \mu),又设ff^\ast是原问题的目标函数最优值,那么有

命题(弱对偶)
ϕf.\phi^\ast\leqslant f^\ast.
这是因为对μ0\boldsymbol \mu\geqslant0ϕ(μ)inf{f(x)μTg(x)g(x)0,xΩ}inf{f(x)g(x)0,xΩ}\phi(\boldsymbol \mu)\leqslant\inf\, \{f(\boldsymbol x)-\boldsymbol \mu^\mathsf T\boldsymbol g(\boldsymbol x)\mid \boldsymbol g(\boldsymbol x)\geqslant0,\, \boldsymbol x\in\Omega\}\leqslant\inf\, \{f(\boldsymbol x)\mid\boldsymbol g(\boldsymbol x)\geqslant0,\, \boldsymbol x\in\Omega\},再取上确界就得到该命题。

.

接下来关注对偶函数的几何含义。对μ0\boldsymbol \mu\geqslant0,考虑向量(1,μ)(1,-\boldsymbol \mu)和常数cc,它们能够定义一个超平面:(1,μ)T(r,z)=c(1,-\boldsymbol \mu)^\mathsf T(r,\boldsymbol z)=c,即rμTz=cr-\boldsymbol \mu^\mathsf T\boldsymbol z=c。当cc取不同的值我们得到一系列平行的超平面。我们取cc足够小,设存在点x\boldsymbol x使r=f(x)r=f(\boldsymbol x)z=g(x)\boldsymbol z=\boldsymbol g(\boldsymbol x),那么此时最小的c=ϕ(μ)c=\phi(\boldsymbol \mu)。再设超平面与一个轴的交点(r0,0)(r _ 0,\boldsymbol 0),代进超平面方程得到c=r0c=r _ 0,就是说轴的截距给出了ϕ(μ)\phi(\boldsymbol \mu)

考虑rr-z\boldsymbol z图,其中r=f(x)r=f(\boldsymbol x)z=g(x)\boldsymbol z=\boldsymbol g(\boldsymbol x),原问题最优解对应的是z0\boldsymbol z\geqslant0这半边的最低点(r,z)(r^\ast,\boldsymbol z^\ast)。不难看出:这些(r,z)(r,\boldsymbol z)点都在超平面rμTz=ϕ(μ)r-\boldsymbol \mu^\mathsf T\boldsymbol z=\phi(\boldsymbol \mu)之上,这是ϕ(μ)\phi(\boldsymbol \mu)的定义决定的。而满足在这些点之下这一条件的超平面的截距不会超过rr^\ast——这正是上面所说的弱对偶。原因也是一样,只考虑在z0\boldsymbol z\geqslant0这边的点之下的超平面的截距当然比考虑所有z\boldsymbol z的要增大(因为只需要在更少的点下方),而正半边对应的最小截距当然是rr^\ast(超平面r=rr=r^\ast),所以总最小截距ϕ(μ)\phi(\boldsymbol \mu)要比rr^\ast要小。

.

现在考虑包含等式约束的优化问题
minf(x)s.t. h(x)=0,  g(x)0,xΩ.\begin{aligned} \min &\quad f(\boldsymbol x)\\ \text{s.t. }&\quad \boldsymbol h(\boldsymbol x)=\boldsymbol 0,\; \boldsymbol g(\boldsymbol x)\geqslant\boldsymbol 0,\\ &\quad \boldsymbol x\in\Omega. \end{aligned}Ω\Omega仍是凸集。此时对偶函数定义为
ϕ(λ,μ)=infx  [f(x)λTh(x)μTg(x)],μ0.\phi(\boldsymbol \lambda,\boldsymbol \mu)=\inf _ \boldsymbol x\; [f(\boldsymbol x)-\boldsymbol \lambda^\mathsf T\boldsymbol h(\boldsymbol x)-\boldsymbol \mu^\mathsf T\boldsymbol g(\boldsymbol x)],\quad \boldsymbol \mu\geqslant0.对偶问题则为
ϕ=supμ0,λϕ(λ,μ).\phi^\ast=\sup _ {\boldsymbol \mu\geqslant0,\boldsymbol \lambda}\phi(\boldsymbol \lambda,\boldsymbol \mu).
弱对偶定理仍成立:ϕf\phi^\ast\leqslant f^\ast

零阶充分条件:若x\boldsymbol x(λ,μ)(\boldsymbol \lambda,\boldsymbol \mu)分别是原问题与对偶问题的可行解,使得f(x)=ϕ(λ,μ)f(\boldsymbol x)=\phi(\boldsymbol \lambda,\boldsymbol \mu),那么它们都分别是各自问题的全局最优解。

引入凸性的假设,可以有如下的强对偶定理:

强对偶定理:在上述原问题基础上,设f,gf,-\boldsymbol g是凸函数,h\boldsymbol h是仿射函数,设最小值为f(x)=ff(\boldsymbol x^\ast)=f^\astx\boldsymbol x^\ast有LICQ(或Slater条件(SCQ)),且x,λ\boldsymbol x^\ast,\boldsymbol \lambda^\ast和非负μ0\boldsymbol \mu^\ast\geqslant0满足KKT条件,那么
ϕ=f.\phi^\ast=f^\ast.λ,μ\boldsymbol \lambda^\ast,\boldsymbol \mu^\ast是对偶问题的最优解。

此时Lagrange函数是凸函数,由零阶充分条件即证。

可以看到,KKT条件是充分的,在凸优化下还是必要的。

泛函分析中的对偶与优化中的对偶的联系

我们可以对优化中的对偶泛函分析中的对偶作一点联系。但这里由于篇幅限制,且需要更深入的数学知识(泛函分析),已在 优化中的对偶与泛函分析中的对偶的联系 单独讨论

简单来说,我们可以将分析放到更一般的框架中来,在一般的赋范线性空间中进行分析。此时弱对偶变成了共轭函数的性质fff^{\ast\ast}\leqslant f;原问题是原空间上的优化问题,而对偶问题成为了一个在对偶空间上的优化问题;Lagrange函数中的Lagrange乘数即对应对偶空间中的向量。我们平时见到的是其特殊形式:考虑的空间是普通的欧氏空间,这样由Hilbert空间中的F. Riesz表示定理,其中的连续线性泛函可以与其中的向量一一对应,可以表示为它的内积形式,就得到了我们平时见到的常见形式。

局部对偶

上面的对偶理论是global的,下面简单过一些local的理论。

下面的分析对含不等约束的问题是完全类似的(只需要稍加改动),但为了叙述的简单只考虑等式约束:
minf(x)s.t. h(x)=0.\begin{aligned} \min&\quad f(\boldsymbol x)\\ \text{s.t. }&\quad \boldsymbol h(\boldsymbol x)=\boldsymbol 0. \end{aligned}这里的f,hC2f,\boldsymbol h\in C^2。我们关注这个问题的一个局部解x\boldsymbol x^\ast,假设这个局部解满足LICQ,那么,由一、二阶必要条件,存在Lagrange乘数λ\boldsymbol \lambda^\ast,使得f(x)h(x)λ=0\nabla f(\boldsymbol x^\ast)-\nabla\boldsymbol h(\boldsymbol x^\ast)\boldsymbol \lambda^\ast=\boldsymbol 0,且2f(x)2h(x)λ\nabla^2 f(\boldsymbol x^\ast)-\nabla^2\boldsymbol h(\boldsymbol x^\ast)\boldsymbol \lambda在切平面M={dJh(x)d=0}M=\{\boldsymbol d\mid J\boldsymbol h(\boldsymbol x^\ast)\boldsymbol d^\ast=\boldsymbol 0\}上半正定。

仍定义Lagrange函数为
L(x,λ)=f(x)λTh(x),L(\boldsymbol x,\boldsymbol \lambda)=f(\boldsymbol x)-\boldsymbol \lambda^\mathsf T\boldsymbol h(\boldsymbol x),那么xL(x,λ)=0\nabla _ \boldsymbol x L(\boldsymbol x^\ast,\boldsymbol \lambda^\ast)=\boldsymbol 0,且xx2L(x,λ)\nabla^2 _ {\boldsymbol {xx}}L(\boldsymbol x^\ast,\boldsymbol \lambda^\ast)MM上半正定。

现在我们需要引入局部凸性的假设以给出局部对偶理论。具体来说,我们假设xx2L(x,λ)\nabla^2 _ {\boldsymbol {xx}}L(\boldsymbol x^\ast,\boldsymbol \lambda^\ast)是正定矩阵;意即,第一,是严格正定而非半正定,第二,是在整个空间都是正定,而非仅在切平面MM上。

在这个假设下,由一、二阶充分条件,x\boldsymbol x^\ast是无约束优化问题minxL(x,λ)\min _ {\boldsymbol x} L(\boldsymbol x,\boldsymbol \lambda^\ast)的一个局部解。

我们断言:对于λ\boldsymbol \lambda^\ast附近的λ\boldsymbol \lambda,存在x\boldsymbol x^\ast附近的x\boldsymbol x使L(x,λ)L(\boldsymbol x,\boldsymbol \lambda)达到到极小值。首先,由于xx2L(x,λ)0\nabla^2 _ {\boldsymbol {xx}}L(\boldsymbol x^\ast,\boldsymbol \lambda^\ast)\succ 0,由隐函数定理,方程xL(x,λ)=0\nabla _ \boldsymbol x L(\boldsymbol x,\boldsymbol \lambda)=\boldsymbol 0对于λ\boldsymbol \lambda^\ast附近的λ\boldsymbol \lambda唯一确定了一个解x\boldsymbol x,后面记作x(λ)\boldsymbol x(\boldsymbol \lambda);由连续性假设,λ\boldsymbol \lambda充分接近λ\boldsymbol \lambda^\ast时,xx2L(x,λ)0\nabla^2 _ {\boldsymbol {xx}}L(\boldsymbol x,\boldsymbol \lambda)\succ0——所以,在局部范围内有一个连续可微的λ,x\boldsymbol \lambda,\boldsymbol x间的对应关系,这个关系通过它们是无约束优化问题的解,即极小化Lagrange函数,来体现。

我们在λ\boldsymbol \lambda^\ast附近定义一个对偶函数ϕ\phi
ϕ(λ)=minxN(x)L(x,λ)=minxN(x)[f(x)λTh(x)].\phi(\boldsymbol \lambda)=\min _ {\boldsymbol x\in N(\boldsymbol x^\ast)}L(\boldsymbol x,\boldsymbol \lambda)=\min _ {\boldsymbol x\in N(\boldsymbol x^\ast)}[f(\boldsymbol x)-\boldsymbol \lambda^\mathsf T\boldsymbol h(\boldsymbol x)].这里的最小是在局部范围内——x\boldsymbol x^\ast的邻域N(x)N(\boldsymbol x^\ast)。下面可以看到局部上带约束的原问题等价于对偶函数ϕ\phi关于λ\boldsymbol \lambda的无约束的局部极大化。因而我们建立了带约束优化问题中的x\boldsymbol x和无约束优化问题中的λ\boldsymbol \lambda的一种联系。

命题:对偶函数的梯度有简单的形式
ϕ(λ)=h(x(λ)).\nabla\phi(\boldsymbol \lambda)=-\boldsymbol h(\boldsymbol x(\boldsymbol \lambda)).命题:对偶函数的Hesse矩阵为
2ϕ(λ)=h(x(λ))T[xx2L(x(λ),λ)]1h(x(λ)).\nabla^2\phi(\boldsymbol \lambda)=-\nabla\boldsymbol h(\boldsymbol x(\boldsymbol \lambda))^\mathsf T[\nabla^2 _ {\boldsymbol {xx}}L(\boldsymbol x(\boldsymbol \lambda),\boldsymbol \lambda)]^{-1}\nabla\boldsymbol h(\boldsymbol x(\boldsymbol \lambda)).
证明:首先梯度可以通过直接计算得到,ϕ(λ)=f(x(λ))λTh(x(λ))\phi(\boldsymbol \lambda)=f(\boldsymbol x(\boldsymbol \lambda))-\boldsymbol \lambda^\mathsf T\boldsymbol h(\boldsymbol x(\boldsymbol \lambda)),求导得
Jϕ(λ)=Jf(x(λ))Jx(λ)λTJh(x(λ))Jx(λ)h(x(λ))Tϕ(λ)=x(λ)[f(x(λ))h(x(λ))λ]h(x(λ))=h(x(λ)).\begin{aligned} J\phi(\boldsymbol \lambda)&=Jf(\boldsymbol x(\boldsymbol \lambda))J\boldsymbol x(\lambda)-\boldsymbol \lambda^\mathsf TJ\boldsymbol h(\boldsymbol x(\boldsymbol \lambda))J\boldsymbol x(\boldsymbol \lambda)-\boldsymbol h(\boldsymbol x(\boldsymbol \lambda))^\mathsf T\\ \nabla\phi(\boldsymbol \lambda)&=\nabla\boldsymbol x(\boldsymbol \lambda)[\nabla f(\boldsymbol x(\boldsymbol \lambda))-\nabla \boldsymbol h(\boldsymbol x(\boldsymbol \lambda))\boldsymbol \lambda]-\boldsymbol h(\boldsymbol x(\boldsymbol \lambda))\\ &=-\boldsymbol h(\boldsymbol x(\boldsymbol \lambda)). \end{aligned}由此亦知Hessian为x(λ)h(x(λ))-\nabla \boldsymbol x(\boldsymbol \lambda)\nabla\boldsymbol h(\boldsymbol x(\boldsymbol \lambda))。对f(x(λ))h(x(λ))λ=0\nabla f(\boldsymbol x(\boldsymbol \lambda))-\nabla \boldsymbol h(\boldsymbol x(\boldsymbol \lambda))\boldsymbol \lambda=\boldsymbol 0关于λ\boldsymbol \lambda求导,得
0=Hf(x(λ))Jx(λ)λTHh(x(λ))Jx(λ)h(x(λ))h(x(λ))T=x(λ)[2f(x(λ))2h(x(λ))λ]=x(λ)xx2L(x(λ),λ)x(λ)=h(x(λ))T[xx2L(x(λ),λ)]1,\begin{aligned} \boldsymbol 0&=Hf(\boldsymbol x(\boldsymbol \lambda))J\boldsymbol x(\boldsymbol \lambda)-\boldsymbol \lambda^\mathsf TH\boldsymbol h(\boldsymbol x(\boldsymbol \lambda))J\boldsymbol x(\boldsymbol \lambda)-\nabla\boldsymbol h(\boldsymbol x(\boldsymbol \lambda)) \\ \nabla\boldsymbol h(\boldsymbol x(\boldsymbol \lambda))^\mathsf T&=\nabla\boldsymbol x(\boldsymbol \lambda)[\nabla^2f(\boldsymbol x(\boldsymbol \lambda))-\nabla^2\boldsymbol h(\boldsymbol x(\boldsymbol \lambda))\boldsymbol \lambda]\\ &=\nabla\boldsymbol x(\boldsymbol \lambda)\nabla^2 _ {\boldsymbol {xx}}L(\boldsymbol x(\boldsymbol \lambda),\boldsymbol \lambda)\\ \nabla\boldsymbol x(\boldsymbol \lambda)&=\nabla\boldsymbol h(\boldsymbol x(\boldsymbol \lambda))^\mathsf T[\nabla^2 _ {\boldsymbol {xx}}L(\boldsymbol x(\boldsymbol \lambda),\boldsymbol \lambda)]^{-1}, \end{aligned}代入Hessian即证。

.

观察ϕ\phi的Hesse矩阵,我们可以推断这是个负定矩阵。于是,有

定理(局部对偶):(在前文的设置下)又设原问题在x\boldsymbol x^\ast处的极小值为rr^\ast,则对偶问题maxϕ(λ)\max\phi(\boldsymbol \lambda)有局部最优解λ\boldsymbol \lambda^\ast且极大值也为rr^\ast

前面已求出ϕ\phi的梯度,于是我们可以有如下的dual ascent(对偶上升法):

dual ascent:迭代过程为
xk+1=argminxL(x,λk,μk),λk+1=λkρkh(xk+1),μk+1=max{0,μkρkg(xk+1)}.\begin{aligned} \boldsymbol x _ {k+1}&=\operatorname*{\arg\min}\nolimits _ {\boldsymbol x}L(\boldsymbol x,\boldsymbol \lambda _ k,\boldsymbol \mu _ k),\\ \boldsymbol \lambda _ {k+1}&=\boldsymbol \lambda _ k-\rho _ k\boldsymbol h(\boldsymbol x _ {k+1}),\\ \boldsymbol \mu _ {k+1}&=\max\{\boldsymbol 0,\, \boldsymbol \mu _ k-\rho _ k\boldsymbol g(\boldsymbol x _ {k+1})\}. \end{aligned}这一方法的具体分析,可参考更深入的文献。

Augmented Lagrangian,ADMM

Augmented Lagrangian

dual ascent要求的条件比较强。可被改进为Augmented Lagrangian method,亦称作是method of multipliers。

对于等式约束h(x)=0\boldsymbol h(\boldsymbol x)=\boldsymbol 0的优化问题minf(x)\min f(\boldsymbol x),其augmented Lagrangian为
Lρ(x,λ)=f(x)λTh(x)+ρ2h(x)2.L _ \rho(\boldsymbol x,\boldsymbol \lambda)=f(\boldsymbol x)-\boldsymbol \lambda^\mathsf T\boldsymbol h(\boldsymbol x)+\frac{\rho}{2}|\boldsymbol h(\boldsymbol x)|^2.这里的ρ>0\rho>0称作是惩罚参数(为零时就是标准的Lagrange函数)。这个函数也可以看作是问题
minf(x)+ρ2h(x)2s.t. h(x)=0\begin{aligned} \min&\quad f(\boldsymbol x)+\frac\rho2|\boldsymbol h(\boldsymbol x)|^2\\ \text{s.t. }&\quad \boldsymbol h(\boldsymbol x)=\boldsymbol 0 \end{aligned}的Lagrange函数,而这个问题显然和原问题等价。此时再应用dual ascent,得到迭代过程
xk+1=argminxLρ(x,λk),λk+1=λkρh(xk+1).\begin{aligned} \boldsymbol x _ {k+1}&=\operatorname*{\arg\min}\nolimits _ {\boldsymbol x} L _ \rho(\boldsymbol x,\boldsymbol \lambda _ k),\\ \boldsymbol \lambda _ {k+1}&=\boldsymbol \lambda _ k-\rho\boldsymbol h(\boldsymbol x _ {k+1}). \end{aligned}这里的ρ\rho使用了常数的设置,当然也可以用变化的设置,例如趋向于某一常数,再如以某一速度趋于无穷。

分析

这个过程看起来和原来的dual ascent没什么区别,然而原来的dual ascent对局部的凸性作了假设,当局部凸性不成立时就不好应用了。此时augmented Lagrangian里的ρ2h(x)2\frac\rho2|\boldsymbol h(\boldsymbol x)|^2一项就起到了将局部“凸化”的作用。对于大ρ\rho,Lagrangian确实变成了局部凸的,因而对偶方法可以应用。

命题:设x,λ\boldsymbol x^\ast,\boldsymbol \lambda^\ast满足二阶充分条件使得ff被极小化,那么存在ρ\rho^\ast使ρ>ρ\rho>\rho^\ast时,Lρ(x,λ)L _ \rho(\boldsymbol x,\boldsymbol \lambda^\ast)都在x\boldsymbol x^\ast处取得极小。

考虑证明。求Hesse矩阵得xx2Lρ(x,λ)=2f(x)2h(x)λ+ρh(x)h(x)T\nabla^2 _ {\boldsymbol {xx}}L _ \rho(\boldsymbol x^\ast,\boldsymbol \lambda^\ast)=\nabla^2 f(\boldsymbol x^\ast)-\nabla^2\boldsymbol h(\boldsymbol x^\ast)\boldsymbol \lambda^\ast+\rho \nabla \boldsymbol h(\boldsymbol x^\ast)\nabla \boldsymbol h(\boldsymbol x^\ast)^\mathsf T,第一第二项即原始Hessian,由于满足二阶充分条件,在切平面{dh(x)Td=0}\{\boldsymbol d\mid \nabla\boldsymbol h(\boldsymbol x)^\mathsf T\boldsymbol d=\boldsymbol 0\}上是正定的;而最后一项是半正定的。若命题不成立,则存在一列单位向量{dk}k=1\{\boldsymbol d _ k\} _ {k=1}^\infty使得dkT(A+ckB)dk0\boldsymbol d _ k^\mathsf T(A+c _ kB)\boldsymbol d _ k\leqslant0,其中AA表示原始Hessian,BB表示hhT\nabla\boldsymbol h\nabla\boldsymbol h^\mathsf Tckc _ k是一列趋于正无穷的数。{dk}\{\boldsymbol d _ k\}有界则存在收敛子列,不妨设dkd\boldsymbol d _ k\to\boldsymbol d,那么应有dTBd=0\boldsymbol d^\mathsf TB\boldsymbol d=0,于是dTAd0\boldsymbol d^\mathsf TA\boldsymbol d\leqslant0,但是前一式意味着Bd=0B\boldsymbol d=\boldsymbol 0,就与命题假设矛盾。最后再次用二阶充分条件即证。

命题ρ\rho充分大时,对λ\boldsymbol \lambda^\ast附近的λ\boldsymbol \lambdaLρ(x,λ)L _ \rho(\boldsymbol x,\boldsymbol \lambda)x\boldsymbol x^\ast附近有唯一极小值点x\boldsymbol x

这个和L(x,λ)L(\boldsymbol x,\boldsymbol \lambda)时的分析是一样的,证明不再赘述。

现在,如果λ\boldsymbol \lambda使得h(x(λ))=0\boldsymbol h(\boldsymbol x(\boldsymbol \lambda))=\boldsymbol 0,那么由于此时这组x,λ\boldsymbol x,\boldsymbol \lambda满足问题min{f(x)+ρ2h(x)2h(x)=0}\min\, \{f(\boldsymbol x)+\frac\rho2|\boldsymbol h(\boldsymbol x)|^2\mid\boldsymbol h(\boldsymbol x)=\boldsymbol 0\}的充分条件,它们必为x,λ\boldsymbol x^\ast,\boldsymbol \lambda^\ast,所以λ\boldsymbol \lambda的选定可视作解h(x(λ))=0\boldsymbol h(\boldsymbol x(\boldsymbol \lambda))=\boldsymbol 0。解这个方程的一种迭代就是λk+1=λkρh(x(λk))\boldsymbol \lambda _ {k+1}=\boldsymbol \lambda _ k-\rho\boldsymbol h(\boldsymbol x(\boldsymbol \lambda _ k)),它会在λ\boldsymbol \lambda^\ast的邻域以线性的速度收敛。

几何解释

考虑primal函数ω(y)=min{f(x)h(x)=y,xN(x)}\omega(\boldsymbol y)=\min\, \{f(\boldsymbol x)\mid \boldsymbol h(\boldsymbol x)=\boldsymbol y,\, \boldsymbol x\in N(\boldsymbol x^\ast)\},可以证明ω(0)=f(x)\omega(\boldsymbol 0)=f(\boldsymbol x^\ast)ω(0)=λ\nabla\omega(\boldsymbol 0)=\boldsymbol \lambda^\ast,细节略过,只给出大意:设h(x)=y\boldsymbol h(\boldsymbol x)=\boldsymbol y下极小值点为x(y)\boldsymbol x(\boldsymbol y),对y=h(x(y))\boldsymbol y=\boldsymbol h(\boldsymbol x(\boldsymbol y))关于y\boldsymbol y求导并令y=0\boldsymbol y=\boldsymbol 0I=Jh(x)Jx(0)I=J\boldsymbol h(\boldsymbol x^\ast)J\boldsymbol x(\boldsymbol 0),从而Jω(0)=Jy(f(x(y)))y=0=Jf(x)Jx(0)=(λ)TJh(x)Jx(0)=(λ)TJ\omega(\boldsymbol 0)=J _ \boldsymbol y(f(\boldsymbol x(\boldsymbol y)))| _ {\boldsymbol y=\boldsymbol 0}=Jf(\boldsymbol x^\ast)J\boldsymbol x(\boldsymbol 0)=(\boldsymbol \lambda^{\ast})^\mathsf TJ\boldsymbol h(\boldsymbol x^\ast)J\boldsymbol x(\boldsymbol 0)=(\boldsymbol \lambda^\ast)^\mathsf T,即证。

用这个primal函数,
minLρ(x,λk)=minx[f(x)λkTh(x)+ρ2h(x)2]=minx,y{f(x)λkTy+ρ2y2h(x)=y}=miny[ω(y)λkTy+ρ2y2].\begin{aligned} \min L _ \rho(\boldsymbol x,\boldsymbol \lambda _ k)&=\min _ \boldsymbol x\, \big[f(\boldsymbol x)-\boldsymbol \lambda _ k^\mathsf T\boldsymbol h(\boldsymbol x)+\frac\rho2|\boldsymbol h(\boldsymbol x)|^2\big]\\ &=\min _ {\boldsymbol {x,y}}\, \big\{f(\boldsymbol x)-\boldsymbol \lambda _ k^\mathsf T\boldsymbol y+\frac\rho2|\boldsymbol y|^2\mid \boldsymbol h(\boldsymbol x)=\boldsymbol y\big\}\\ &=\min _ \boldsymbol y\, \big[\omega(\boldsymbol y)-\boldsymbol \lambda^\mathsf T _ k\boldsymbol y+\frac\rho2|\boldsymbol y|^2 \big] . \end{aligned}这里面对y\boldsymbol y的最小是在0\boldsymbol 0的邻域内取的。对于单约束,下图展示了这一最小化的过程。有了λk\lambda _ kyky _ k应满足ω(y)+ρ2y2\omega(y)+\frac\rho2y^2在它上面切线斜率恰为λk\lambda _ k,然后ω(y)\omega(y)yky _ k的斜率正是λk+1\lambda _ {k+1}。这是因为yk\boldsymbol y _ k既然使ω(y)λkTy+ρ2y2\omega(\boldsymbol y)-\boldsymbol \lambda^\mathsf T _ k\boldsymbol y+\frac\rho2|\boldsymbol y|^2最小,那么ω(yk)+ρyk=λk\nabla\omega(\boldsymbol y _ k)+\rho\boldsymbol y _ k=\boldsymbol \lambda _ k,故λk+1=λkρh(x(λk))=λkρyk=ω(yk)\boldsymbol \lambda _ {k+1}=\boldsymbol \lambda _ k-\rho\boldsymbol h(\boldsymbol x(\boldsymbol \lambda _ k))=\boldsymbol \lambda _ k-\rho\boldsymbol y _ k=\nabla\omega(\boldsymbol y _ k)

The Alternating Direction Method of Multipliers

这一节推荐查阅著名文献:
S. Boyd and N. Parikh and E. Chu and B. Peleato and J. Eckstein (2010), “Distributed optimization and statistical learning via the alternating direction method of multipliers”

.

虽然augmented Lagrangian有更好的收敛,但是会失去问题的decomposability。(Separability is ruined by augmented Lagrangian ...)

ADMM算法试图结合dual ascent和augmented Lagrangian的优点。(ADMM is an algorithm that is intended to blend the decomposability of dual ascent with the superior convergence properties of the method of multipliers.)

考虑问题
minf(x)+g(y)s.t. Ax+By=b.\begin{aligned} \min&\quad f(\boldsymbol x)+g(\boldsymbol y)\\ \text{s.t. }&\quad A\boldsymbol x+B\boldsymbol y=\boldsymbol b. \end{aligned}最优值设为pp^\ast,augmented Lagrangian写为
Lρ(x,y,λ)=f(x)+g(y)λT(Ax+Byb)+ρ2Ax+Byb2,L _ \rho(\boldsymbol x,\boldsymbol y,\boldsymbol \lambda)=f(\boldsymbol x)+g(\boldsymbol y)-\boldsymbol \lambda^\mathsf T(A\boldsymbol x+B\boldsymbol y-\boldsymbol b)+\frac\rho2|A\boldsymbol x+B\boldsymbol y-\boldsymbol b|^2,可以看到惩罚项会有x,y\boldsymbol x,\boldsymbol y的耦合,而ADMM则交替分而治之,是谓alternating direction,迭代步骤为:
xk+1=argminxLρ(x,yk,λk),yk+1=argminyLρ(xk+1,y,λk),λk+1=λkρ(Axk+1+Byk+1b).\begin{aligned} \boldsymbol x _ {k+1}&=\operatorname*{\arg\min}\nolimits _ \boldsymbol x L _ \rho(\boldsymbol x,\boldsymbol y _ k,\boldsymbol \lambda _ k),\\ \boldsymbol y _ {k+1}&=\operatorname*{\arg\min}\nolimits _ \boldsymbol y L _ \rho(\boldsymbol x _ {k+1},\boldsymbol y,\boldsymbol \lambda _ k),\\ \boldsymbol \lambda _ {k+1}&=\boldsymbol \lambda _ k-\rho(A\boldsymbol x _ {k+1}+B\boldsymbol y _ {k+1}-\boldsymbol b). \end{aligned}
对于ADMM的收敛,这里只给出如下定理:

定理:设f,gf,g是闭的凸函数,unaugmented Lagrangian有一个鞍点,即存在(x,y,λ)(\boldsymbol x^\ast,\boldsymbol y^\ast,\boldsymbol \lambda^\ast)使得
L0(x,y,λ)L0(x,y,λ)L0(x,y,λ),L _ 0(\boldsymbol x^\ast,\boldsymbol y^\ast,\boldsymbol \lambda)\leqslant L _ 0(\boldsymbol x^\ast,\boldsymbol y^\ast,\boldsymbol \lambda^\ast)\leqslant L _ 0(\boldsymbol x,\boldsymbol y,\boldsymbol \lambda^\ast),那么ADMM满足:

  1. 残差收敛:Axk+Bykb0A\boldsymbol x _ k+B\boldsymbol y _ k-\boldsymbol b\to\boldsymbol 0,即迭代逐渐达到feasibility;
  2. 目标函数收敛:f(xk)+g(yk)pf(\boldsymbol x _ k)+g(\boldsymbol y _ k)\to p^\ast,即迭代逐渐达到最优;
  3. 对偶变量收敛:λkλ\boldsymbol \lambda _ k\to\boldsymbol \lambda^\ast,其中λ\boldsymbol \lambda^\ast为使得infx,yL0(x,y,λ)\inf _ {\boldsymbol x,\boldsymbol y}L _ 0(\boldsymbol x,\boldsymbol y,\boldsymbol \lambda)最小的点。

注意xk,zk\boldsymbol x _ k,\boldsymbol z _ k不必收敛到最优。


评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注