UA SIE545 优化理论基础4 对偶理论简介2 弱对偶与Duality Gap
UA SIE545 优化理论基础4 对偶理论简介2 弱对偶与Duality Gap
上一讲我们定义了Lagrange对偶，这一讲我们介绍第一个重要结论——弱对偶定理(Weak duality theorem)。
我们先回顾一下Lagrange对偶的定义：考虑优化问题P：
minf(x)s.t.g(x)≤0,h(x)=0,x∈X\min f(x) \\ s.t. \ g(x) \le 0, h(x) = 0, x \in Xminf(x)s.t. g(x)≤0,h(x)=0,x∈X
定义其对偶问题为优化D：
supu,vθ(u,v)s.t.u≥0\sup_{u,v} \theta(u,v) \\ s.t. u \ge 0u,vsupθ(u,v)s.t.u≥0
其中
θ(u,v)=infx∈Xϕ(x,u,v)=infx∈Xf(x)+uTg(x)+vTh(x)\theta(u,v)=\inf_{x \in X}\phi(x,u,v) =\inf_{x \in X} f(x)+u^Tg(x)+v^Th(x)θ(u,v)=x∈Xinfϕ(x,u,v)=x∈Xinff(x)+uTg(x)+vTh(x)
Weak duality theorem 假设xˉ\bar xxˉ是优化问题P的可行解，(u,v)(u,v)(u,v)是优化问题D的可行解，则f(xˉ)≥θ(u,v)f(\bar x)\ge \theta(u,v)f(xˉ)≥θ(u,v)。
评注 这个结果直觉上是来自我们上一讲例1导出Lagrange对偶的过程的，我们导出对偶问题的目标是要找一个目标函数最小值的一个“有价值”的下界，所以从直觉上讲对偶问题目标函数的最优值当然比原问题的目标函数最优值更小。
证明
直接摘录上面的定义，
θ(u,v)=infx∈Xf(x)+uTg(x)+vTh(x)≤f(x)+uTg(x)+vTh(x),∀x∈X≤f(xˉ)\theta(u,v)=\inf_{x \in X} f(x)+u^Tg(x)+v^Th(x) \\ \le f(x)+u^Tg(x)+v^Th(x) ,\forall x \in X \le f(\bar x)θ(u,v)=x∈Xinff(x)+uTg(x)+vTh(x)≤f(x)+uTg(x)+vTh(x),∀x∈X≤f(xˉ)
最后这个不等号是因为u≥0u \ge 0u≥0, g(x)≤0g(x) \le 0g(x)≤0而h(x)=0h(x)=0h(x)=0。
证毕
可以说弱对偶定理并不是一个很令人惊叹的结果，因为我们从直觉、从定义就可以发现这个事实。但弱对偶定理还有四个有趣的推论：
推论1
inf{f(x):x∈X,g(x)≤0,h(x)=0}≥sup{θ(u,v):u≥0}\inf\{f(x):x \in X,g(x) \le 0,h(x)=0\} \\ \ge \sup\{\theta(u,v):u \ge 0\}inf{f(x):x∈X,g(x)≤0,h(x)=0}≥sup{θ(u,v):u≥0}
这个推论可以看成是用公式来表示的弱对偶定理，并没有提供额外的信息。
推论2
如果f(xˉ)=θ(uˉ,vˉ)f(\bar x)=\theta(\bar u,\bar v)f(xˉ)=θ(uˉ,vˉ)，uˉ≥0,xˉ∈{x∈X:g(x)≤0,h(x)=0}\bar u \ge 0,\bar x \in \{x \in X:g(x) \le 0,h(x)=0\}uˉ≥0,xˉ∈{x∈X:g(x)≤0,h(x)=0}，则xˉ\bar xxˉ和uˉ,vˉ\bar u,\bar vuˉ,vˉ分别是优化P与优化D的解。
这个推论可以从推论1直接得到，如果xˉ\bar xxˉ不是最优解就违背了下确界的定义，如果uˉ,vˉ\bar u,\bar vuˉ,vˉ不是最优解就违背了上确界的定义。
推论3
如果inf{f(x):x∈X,g(x)≤0,h(x)=0}=−∞\inf\{f(x):x \in X,g(x) \le 0,h(x)=0\}=-\inftyinf{f(x):x∈X,g(x)≤0,h(x)=0}=−∞
则θ(u,v)=−∞,∀u≥0\theta(u,v)=-\infty,\forall u \ge 0θ(u,v)=−∞,∀u≥0。
小于负无穷大量，那就是负无穷了，这个也能直接从弱对偶定理推出。
推论4
如果sup{θ(u,v):u≥0}=+∞\sup\{\theta(u,v):u \ge 0\}=+\inftysup{θ(u,v):u≥0}=+∞，则优化P没有可行解。因为根据推论1，inff\inf finff就大于无穷大量的。
推论1点出了弱对偶中“弱”这个字的内涵，因为对偶问题目标函数最优值只是原问题目标函数最优值的下界，所以它实际上能告诉我们的信息非常弱，下一讲我们会介绍强对偶定理，强对偶意味着原问题与对偶问题最优值是相等的，也就是推论1中的不等式会取等
inf{f(x):x∈X,g(x)≤0,h(x)=0}=sup{θ(u,v):u≥0}\inf\{f(x):x \in X,g(x) \le 0,h(x)=0\}=\sup\{\theta(u,v):u \ge 0\}inf{f(x):x∈X,g(x)≤0,h(x)=0}=sup{θ(u,v):u≥0}这样的对偶能提供的信息就非常强了。当
inf{f(x):x∈X,g(x)≤0,h(x)=0}>sup{θ(u,v):u≥0}\inf\{f(x):x \in X,g(x) \le 0,h(x)=0\}>\sup\{\theta(u,v):u \ge 0\}inf{f(x):x∈X,g(x)≤0,h(x)=0}>sup{θ(u,v):u≥0}
时，称二者之差为Duality gap。下面的两个例子分别是关于强对偶与Duality gap的。
例3 考虑优化问题
min(x−2)2+(y−2)2s.t.x≤0,y≤0\min (x-2)^2+(y-2)^2 \\ s.t. x \le 0,y \le 0min(x−2)2+(y−2)2s.t.x≤0,y≤0
这个问题的几何含义是在第三象限内找一个距离(2,2)(2,2)(2,2)最近的点。我们先写出它的对偶问题，定义
ϕ(x,y,u1,u2)=(x−2)2+(y−2)2+2u1x+2u2y\phi(x,y,u_1,u_2)=(x-2)^2+(y-2)^2+2u_1x+2u_2yϕ(x,y,u1,u2)=(x−2)2+(y−2)2+2u1x+2u2y
选择x,yx,yx,y最小化这个函数，不难发现x=2−u1,y=2−u2x=2-u_1,y=2-u_2x=2−u1,y=2−u2，因此
θ(u1,u2)=−[(u1−2)2+(u2−2)2]+8\theta(u_1,u_2)=-[(u_1-2)^2+(u_2-2)^2]+8θ(u1,u2)=−[(u1−2)2+(u2−2)2]+8
对偶问题为
max−[(u1−2)2+(u2−2)2]+8s.t.u1≥0,u2≥0\max -[(u_1-2)^2+(u_2-2)^2]+8 \\ s.t. u_1 \ge 0,u_2 \ge 0max−[(u1−2)2+(u2−2)2]+8s.t.u1≥0,u2≥0
我们一眼就能看出对偶问题和原问题的最优值是相同的，因此这个原问题的对偶是一个强对偶。
例4 考虑下面的线性规划
min−2x1+x2s.t.x1+x2−3=0(x1,x2)∈{(0,0),(0,4),(4,4),(4,0),(1,2),(2,1)}\min -2x_1+x_2 \\ s.t. x_1+x_2-3 = 0 \\ (x_1,x_2) \in \{(0,0),(0,4),(4,4),(4,0),(1,2),(2,1)\}min−2x1+x2s.t.x1+x2−3=0(x1,x2)∈{(0,0),(0,4),(4,4),(4,0),(1,2),(2,1)}
因为可行域是一个有限集，我们很容易验证(2,1)(2,1)(2,1)是最优点，并且最优值为-3。下面考虑它的对偶问题，
θ(v)=minx∈X{−2x1+x2+v(x1+x2−3)}={−4+5v,v≤−1−8+v,−1≤v≤2−3v,v≥2\theta(v)=\min_{x \in X}\{-2x_1+x_2+v(x_1+x_2-3)\} \\ = \begin{cases} -4+5v, v \le -1 \\ -8+v , -1 \le v \le 2 \\ -3v, v \ge 2 \end{cases}θ(v)=x∈Xmin{−2x1+x2+v(x1+x2−3)}=⎩⎪⎨⎪⎧−4+5v,v≤−1−8+v,−1≤v≤2−3v,v≥2
它的最大值在v=2v=2v=2处取得，为-6，它是小于原问题的最优值-3的，它们的差值3就是Duality gap。
总结
以上是生活随笔为你收集整理的UA SIE545 优化理论基础4 对偶理论简介2 弱对偶与Duality Gap的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： UA MATH523A 实分析3 积分理
- 下一篇： UA MATH563 概率论的数学基础