UA SIE545 优化理论基础4 对偶理论简介3 强对偶
UA SIE545 优化理论基础4 对偶理论简介3 强对偶
上一讲介绍了弱对偶，弱对偶满足
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}
如果这个式子取等，那就是强对偶，原问题与对偶问题的最优值相等。相比弱对偶，我们肯定是更希望有强对偶的，这一讲我们讨论什么样的优化问题，它的Lagrange对偶是强对偶。
Strong Duality Theorem
假设XXX是非空凸集，f,gf,gf,g是凸函数，h(x)h(x)h(x)是仿射函数(或者可以写成h(x)=Ax−bh(x)=Ax-bh(x)=Ax−b的形式)，使得下面的条件成立：
∃x^∈X,g(x^)<0,h(x^)=0,0∈inth(X)\exists \hat x \in X,g(\hat x)<0,h(\hat x)=0,0 \in int\ h(X)∃x^∈X,g(x^)<0,h(x^)=0,0∈int h(X)则下面的结论成立
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}<∞\inf\{f(x):x \in X,g(x) \le 0,h(x)=0\}<\inftyinf{f(x):x∈X,g(x)≤0,h(x)=0}<∞，并且xˉ\bar xxˉ和uˉ,vˉ\bar u,\bar vuˉ,vˉ分别为原问题与对偶问题的最优解，则
uˉTg(xˉ)=0\bar u^Tg(\bar x)=0uˉTg(xˉ)=0
这一讲我们先完成这个定理的证明，之后再讨论强对偶的实际应用。
在正式证明这个定理之前，我们先介绍一个非常重要的Farkas定理类型的引理，这个引理将提供强对偶定理的证明框架。
引理 假设XXX是一个非空凸集，α,g\alpha,gα,g是两个凸函数，hhh是一个仿射函数，如果System 1无解，则System 2有解。
System 1：α(x)<0,g(x)≤0,h(x)=0,∃x∈X\alpha(x)<0,g(x) \le 0,h(x)=0,\exists x \in Xα(x)<0,g(x)≤0,h(x)=0,∃x∈X
System 2: u0α(x)+uTg(x)+vTh(x)≥0,∀x∈X,(u0,u)≥0,(u0,u,v)≠0u_0\alpha(x)+u^Tg(x)+v^Th(x) \ge 0,\forall x \in X,(u_0,u) \ge 0,(u_0,u,v) \ne 0u0α(x)+uTg(x)+vTh(x)≥0,∀x∈X,(u0,u)≥0,(u0,u,v)=0
证明
这是比较典型的Farkas定理类型的结论，所以证明方法是比较标准的，主要思路仍然是分离定理，参考UA SIE545 优化理论基础1 例题2 Farkas定理与相关结论。
定义集合，
A={(p,q,r):p>α(x),q≥g(x),r=h(x),∃x∈X}A = \{(p,q,r):p>\alpha(x),q \ge g(x),r = h(x),\exists x \in X\}A={(p,q,r):p>α(x),q≥g(x),r=h(x),∃x∈X}
假设System 1无解，则(0,0,0)∉A(0,0,0) \notin A(0,0,0)∈/A。因为α,g\alpha,gα,g是凸函数，hhh是仿射函数，而XXX也是凸集，不难验证AAA也是凸集。根据凸集与点的分离，∃(u0,u,v)\exists (u_0,u,v)∃(u0,u,v),
u0p+uTp+vTr≥0,∀(p,q,r)∈Aˉu_0p+u^Tp+v^Tr \ge 0,\forall (p,q,r) \in \bar Au0p+uTp+vTr≥0,∀(p,q,r)∈Aˉ
我们先固定一个使(p,q,r)∈A(p,q,r) \in A(p,q,r)∈A的xxx，接下来我们观察集合AAA的构造，很明显p,qp,qp,q可以任意大，因此u0,uu_0,uu0,u必须非负才能保证上面这个不等式成立。另外，我们可以验证(p,q,r)=[α(x),g(x),h(x)]∈clA(p,q,r)=[\alpha(x),g(x),h(x)] \in cl A(p,q,r)=[α(x),g(x),h(x)]∈clA，因此
u0α(x)+uTg(x)+vTh(x)≥0u_0\alpha(x)+u^Tg(x)+v^Th(x) \ge 0u0α(x)+uTg(x)+vTh(x)≥0
其中(u0,u)≥0,(u0,u,v)≠0(u_0,u) \ge 0,(u_0,u,v) \ne 0(u0,u)≥0,(u0,u,v)=0，所以System 2有解。
证毕
下面我们正式开始证明强对偶定理。
证明
先定义一个记号，γ=inf{f(x):x∈X,g(x)≤0,h(x)=0}\gamma = \inf\{f(x):x \in X,g(x) \le 0,h(x)=0\}γ=inf{f(x):x∈X,g(x)≤0,h(x)=0}，假设γ<+∞\gamma<+\inftyγ<+∞，需要注意一下的是如果γ=−∞\gamma=-\inftyγ=−∞，根据弱对偶，
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}
sup{θ(u,v):u≥0}=−∞\sup\{\theta(u,v):u \ge 0\}=-\inftysup{θ(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}
是成立的。
下面讨论∣γ∣<∞|\gamma|<\infty∣γ∣<∞。定义System 1如下：
f(x)−γ<0,g(x)≤0,h(x)=0,x∈Xf(x)-\gamma<0,g(x) \le 0,h(x)=0,x \in Xf(x)−γ<0,g(x)≤0,h(x)=0,x∈X
按γ\gammaγ的定义，f(x)−γf(x)-\gammaf(x)−γ肯定是不成立的，因此System 1无解。现在使用前面叙述的引理，u0[f(x)−γ]+uTg(x)+vTh(x)≥0,∀x∈Xu_0[f(x)-\gamma]+u^Tg(x)+v^Th(x) \ge 0,\forall x \in Xu0[f(x)−γ]+uTg(x)+vTh(x)≥0,∀x∈X
其中(u0,u)≥0,(u0,u,v)≠0(u_0,u) \ge 0,(u_0,u,v) \ne 0(u0,u)≥0,(u0,u,v)=0。接下来我们利用这个不等式(下文称之为(1)式)导出想要的结论，具体操作分为三步：
我们先用反证法完成第一步，假设u0=0u_0=0u0=0，定理的假设提到
∃x^∈X,g(x^)<0,h(x^)=0,0∈inth(X)\exists \hat x \in X,g(\hat x)<0,h(\hat x)=0,0 \in int\ h(X)∃x^∈X,g(x^)<0,h(x^)=0,0∈int h(X)
代入(1)式，
u0[f(x^)−γ]+uTg(x^)+vTh(x^)=uTg(x^)≥0u_0[f(\hat x)-\gamma]+u^Tg(\hat x)+v^Th(\hat x) = u^Tg(\hat x) \ge 0u0[f(x^)−γ]+uTg(x^)+vTh(x^)=uTg(x^)≥0
因为g(x^)<0,u≥0g(\hat x)<0,u \ge 0g(x^)<0,u≥0，因此要使uTg(x^)≥0u^Tg(\hat x) \ge 0uTg(x^)≥0成立，除非u=0u=0u=0。这时，如果我们再使用一次(1)式，并代入u0=0,u=0u_0=0,u=0u0=0,u=0，会得到vTh(x)≥0,∀x∈Xv^Th(x) \ge 0,\forall x \in XvTh(x)≥0,∀x∈X。因为0∈inth(X)0 \in int\ h(X)0∈int h(X)，这说明h(X)h(X)h(X)是XXX的线性子空间，选择x∈Xx \in Xx∈X使得h(x)=−λv,λ>0h(x)=-\lambda v,\lambda>0h(x)=−λv,λ>0，则
vTh(x)=−λ∥v∥2≤0,∀vv^Th(x)= -\lambda \left\| v\right\|^2 \le 0,\forall vvTh(x)=−λ∥v∥2≤0,∀v
考虑到vTh(x)≥0,∀x∈Xv^Th(x) \ge 0,\forall x \in XvTh(x)≥0,∀x∈X，要使上式成立除非v=0v=0v=0，也就是说假设u0=0u_0=0u0=0，我们导出了u,vu,vu,v也都是零向量，这与定理假设矛盾。因此，u0>0u_0>0u0>0。
接下来我们完成第二步。使用(1)式，两边除以u0u_0u0可以得到
f(x)+uˉTg(x)+vˉTh(x)≥γ,∀x∈Xf(x)+\bar u^Tg(x)+\bar v^Th(x) \ge \gamma,\forall x \in Xf(x)+uˉTg(x)+vˉTh(x)≥γ,∀x∈X
记这个不等式为(2)式。进而
θ(uˉ,vˉ)=inf{f(x)+uˉTg(x)+vˉTh(x):x∈X}≥γ\theta(\bar u,\bar v)=\inf\{f(x)+\bar u^Tg(x)+\bar v^Th(x): x \in X\} \ge \gammaθ(uˉ,vˉ)=inf{f(x)+uˉTg(x)+vˉTh(x):x∈X}≥γ
根据弱对偶定理，θ(uˉ,vˉ)≤γ\theta(\bar u,\bar v) \le \gammaθ(uˉ,vˉ)≤γ，因此θ(uˉ,vˉ)=γ\theta(\bar u,\bar v)=\gammaθ(uˉ,vˉ)=γ。
最后我们完成第三步。假设xˉ\bar xxˉ是一个原问题的最优解，也就是xˉ∈X,g(xˉ)≤0,h(xˉ)=0,f(xˉ)=γ\bar x \in X,g(\bar x) \le 0,h(\bar x)=0,f(\bar x)=\gammaxˉ∈X,g(xˉ)≤0,h(xˉ)=0,f(xˉ)=γ。利用(2)式，取x=xˉx = \bar xx=xˉ，
uˉTg(xˉ)≥0\bar u^Tg(\bar x) \ge 0uˉTg(xˉ)≥0
因为uˉ≥0,g(xˉ)≤0\bar u\ge 0,g(\bar x) \le 0uˉ≥0,g(xˉ)≤0，因此uˉTg(xˉ)=0\bar u^Tg(\bar x)=0uˉTg(xˉ)=0。
证毕
总结
以上是生活随笔为你收集整理的UA SIE545 优化理论基础4 对偶理论简介3 强对偶的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： UA SIE545 优化理论基础4 对偶
- 下一篇： 初等数学O 集合论基础 第一节 集合及其