UA SIE545 优化理论基础4 对偶理论简介5 对偶的几何解释

UA SIE545 优化理论基础4 对偶理论简介5 对偶的几何解释

前四讲我们建立了弱对偶与强对偶的概念与理论，这一讲我们试图从直观上理解对偶。

---

强对偶的几何解释

考虑下面的优化
$$\begin{gathered} \min (x-2{)}^2 \\ s.t.x\ge 0 \end{gathered}$$

从几何上，这个优化想在数轴的非负半轴找一个距离$x=2$最近的点。下面我们写出对偶问题，
$$\theta (u)=\inf \{(x-2{)}^2-ux:x\ge 0\}=-(u+2{)}^2+4$$

取得inf的$x$满足$x=u+2$，因此对偶问题为
$$\underset{u\ge 0}{\max }\theta (u)=\underset{u\ge 0}{\max }[-(u+2{)}^2+4]$$

我们在原优化问题的空间中讨论，记$y=(x-2{)}^2$，这是原优化问题的目标函数，在空间${\mathbb{R}}^2$中，Lagrange函数是一族抛物线
$$\{(x,y):y=(x-2{)}^2-ux,u\ge 0\}$$

另外，我们可以把对偶问题理解为一个单参数映射，
$$\left[\begin{array}{c}x\\ y\end{array}\right](u)=\left[\begin{array}{c}u+2\\ -(u+2{)}^2+4\end{array}\right],u\ge 0$$

它其实就是${\mathbb{R}}^2$中的一条参数曲线，消去参数$u$，我们可以得到曲线的表达式为
$$y=-x^2+4,x\ge 2$$

它就是对偶问题目标函数在原优化问题参数空间中的表示。在下图中，黑色虚线表示原优化问题的Lagrange函数，这是一簇抛物线；红线是对偶问题的目标函数在原优化问题参数空间中的表示，当然按定义域它应该取$x\ge 2$的部分。红色的线穿过黑色的线的最小值，这是由对偶问题的定义决定的，也就是由$\theta (u)=\inf \{(x-2{)}^2-ux:x\ge 0\}$决定的。红线的最大值在(2,0)处取得，第一条黑线($y=(x-2{)}^2,x\ge 0$)的也是，因此这个优化的对偶是强对偶。

---

Duality Gap的几何解释

考虑下面的线性规划
$$\begin{gathered} \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)\} \end{gathered}$$

在之前的博客的例4中，我们导出了对偶问题的目标函数为
$$\theta (v)=\{\begin{array}{l}-4+5v,v\le -1\\ -8+v,-1\le v\le 2\\ -3v,v\ge 2\end{array}$$

我们在原问题的参数空间中作图：红色标注的点是集合$X$，蓝色虚线是约束$x_1+x_2-3=0$，它们的交集$(1,2),(2,1)$是可行域，浅蓝实线的截距是$(1,2)$对应的目标函数值，紫色实线的截距是$(2,1)$对应的目标函数值，我们要找最小值，所以应该取$(2,1)$作为最优点，最小值就是紫色实线的截距-3，在图上由绿色标记的点表示；现在看对偶问题的目标函数，它的值应该对应到图上$\{-2x_1+x_2=b\}$这组平行直线的截距，这个分段函数表示截距有三个取值范围，当$v\le -1$时，取值范围是截距小于等于-9，如下图浅绿色区域；当$-1\le v\le 2$时，取值范围是截距在-9到-6之间，如下图浅红色区域，当$v\ge 2$时，取值范围是截距小于等于-6，也就是浅绿色和浅红色区域的并。显然当$v=2$是对偶问题目标函数最大且最大值为-6，在图上标记为浅蓝色点，浅蓝色点与绿色点之间的距离3就是Duality Gap。

总结

以上是生活随笔为你收集整理的UA SIE545 优化理论基础4 对偶理论简介5 对偶的几何解释的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。