UA SIE545 優(yōu)化理論基礎(chǔ)4 對(duì)偶理論簡(jiǎn)介5 對(duì)偶的幾何解釋

前四講我們建立了弱對(duì)偶與強(qiáng)對(duì)偶的概念與理論，這一講我們?cè)噲D從直觀上理解對(duì)偶。

---

強(qiáng)對(duì)偶的幾何解釋

考慮下面的優(yōu)化
$$\begin{gathered} \min (x?2{)}^2 \\ s.t.x\ge 0 \end{gathered}$$

從幾何上，這個(gè)優(yōu)化想在數(shù)軸的非負(fù)半軸找一個(gè)距離$x=2$最近的點(diǎn)。下面我們寫出對(duì)偶問(wèn)題，
$$\theta (u)=\inf \{(x?2{)}^2?ux:x\ge 0\}=?(u+2{)}^2+4$$

取得inf的$x$滿足$x=u+2$，因此對(duì)偶問(wèn)題為
$$\underset{u\ge 0}{\max }\theta (u)=\underset{u\ge 0}{\max }[?(u+2{)}^2+4]$$

我們?cè)谠瓋?yōu)化問(wèn)題的空間中討論，記$y=(x?2{)}^2$，這是原優(yōu)化問(wèn)題的目標(biāo)函數(shù)，在空間${\mathbb{R}}^2$中，Lagrange函數(shù)是一族拋物線
$$\{(x,y):y=(x?2{)}^2?ux,u\ge 0\}$$

另外，我們可以把對(duì)偶問(wèn)題理解為一個(gè)單參數(shù)映射，
$$\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$$

它其實(shí)就是${\mathbb{R}}^2$中的一條參數(shù)曲線，消去參數(shù)$u$，我們可以得到曲線的表達(dá)式為
$$y=?x^2+4,x\ge 2$$

它就是對(duì)偶問(wèn)題目標(biāo)函數(shù)在原優(yōu)化問(wèn)題參數(shù)空間中的表示。在下圖中，黑色虛線表示原優(yōu)化問(wèn)題的Lagrange函數(shù)，這是一簇拋物線；紅線是對(duì)偶問(wèn)題的目標(biāo)函數(shù)在原優(yōu)化問(wèn)題參數(shù)空間中的表示，當(dāng)然按定義域它應(yīng)該取$x\ge 2$的部分。紅色的線穿過(guò)黑色的線的最小值，這是由對(duì)偶問(wèn)題的定義決定的，也就是由$\theta (u)=\inf \{(x?2{)}^2?ux:x\ge 0\}$決定的。紅線的最大值在(2,0)處取得，第一條黑線($y=(x?2{)}^2,x\ge 0$)的也是，因此這個(gè)優(yōu)化的對(duì)偶是強(qiáng)對(duì)偶。

---

Duality Gap的幾何解釋

考慮下面的線性規(guī)劃
$$\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中，我們導(dǎo)出了對(duì)偶問(wèn)題的目標(biāo)函數(shù)為
$$\theta (v)=?\begin{array}{l}?4+5v,v\le ?1\\ ?8+v,?1\le v\le 2\\ ?3v,v\ge 2\end{array}$$

我們?cè)谠瓎?wèn)題的參數(shù)空間中作圖：紅色標(biāo)注的點(diǎn)是集合$X$，藍(lán)色虛線是約束$x_1+x_2?3=0$，它們的交集$(1,2),(2,1)$是可行域，淺藍(lán)實(shí)線的截距是$(1,2)$對(duì)應(yīng)的目標(biāo)函數(shù)值，紫色實(shí)線的截距是$(2,1)$對(duì)應(yīng)的目標(biāo)函數(shù)值，我們要找最小值，所以應(yīng)該取$(2,1)$作為最優(yōu)點(diǎn)，最小值就是紫色實(shí)線的截距-3，在圖上由綠色標(biāo)記的點(diǎn)表示；現(xiàn)在看對(duì)偶問(wèn)題的目標(biāo)函數(shù)，它的值應(yīng)該對(duì)應(yīng)到圖上$\{?2x_1+x_2=b\}$這組平行直線的截距，這個(gè)分段函數(shù)表示截距有三個(gè)取值范圍，當(dāng)$v\le ?1$時(shí)，取值范圍是截距小于等于-9，如下圖淺綠色區(qū)域；當(dāng)$?1\le v\le 2$時(shí)，取值范圍是截距在-9到-6之間，如下圖淺紅色區(qū)域，當(dāng)$v\ge 2$時(shí)，取值范圍是截距小于等于-6，也就是淺綠色和淺紅色區(qū)域的并。顯然當(dāng)$v=2$是對(duì)偶問(wèn)題目標(biāo)函數(shù)最大且最大值為-6，在圖上標(biāo)記為淺藍(lán)色點(diǎn)，淺藍(lán)色點(diǎn)與綠色點(diǎn)之間的距離3就是Duality Gap。

總結(jié)

以上是生活随笔為你收集整理的UA SIE545 优化理论基础4 对偶理论简介5 对偶的几何解释的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。