UA SIE545 優化理論基礎 例題 對偶函數的凸性與次梯度計算

例 考慮對偶函數
$$\theta (u_1,u_2)=\underset{x_1^2+x_2^2\le 4}{\min }{x}_1(2?u_1)+x_2(3?u_2)$$它是凸函數還是凹函數？計算它在$(2,3)$處的次梯度。

分析 這個對偶函數對應的原優化問題是
$$\begin{gathered} \underset{(x_1,x_2)\in X}{\min }2x_1+3x_2 \\ s.t.x_1\ge 0,x_2\ge 0 \\ X=\{(x_1,x_2):x_1^2+x_2^2\le 4\} \end{gathered}$$

不難驗證這個對偶問題滿足強對偶條件，因此原優化與對偶優化的最優值是相等的。

解
第一問：判斷對偶函數的凸性，有兩種方法：

直接法：按照凸性的定義直接驗證對偶函數是不是凸函數；

解析法：求解出對偶函數的表達式，再判斷對偶函數的凸性。

(i) 直接法：考慮$u=(u_1,u_2),v=(v_1,v_2),\lambda \in (0,1)$，$\theta$的定義中，目標函數可以寫成
$$\begin{gathered} \lambda \theta (u)+(1?\lambda )\theta (v) \\ =\underset{x\in X}{\min }\lambda [x_1(2?u_1)+x_2(3?u_2)]+\underset{x\in X}{\min }(1?\lambda )[x_1(2?v_1)+x_2(3?v_2)] \\ \le \underset{x\in X}{\min }\lambda [x_1(2?u_1)+x_2(3?u_2)]+(1?\lambda )[x_1(2?v_1)+x_2(3?v_2)] \\ =\theta (\lambda u+(1?\lambda )v) \end{gathered}$$

于是$\theta$是凹函數；

(ii) 解析法：考慮求解$\theta (u_1,u_2)$的表達式，把$x_1,x_2$消掉，
$$\theta (u_1,u_2)=\underset{x_1^2+x_2^2\le 4}{\min }{x}_1(2?u_1)+x_2(3?u_2)$$這個優化目標函數是線性函數、可行域是圓，可以用幾何法求解，當然也可以用代數法，我們先考慮代數法：

記$v=[2?u_1,3?u_2{]}^T$，則
$$\theta (u_1,u_2)=\min \{x^{T}v:\Vert x\Vert \le 2\}$$

根據Cauchy-Schwarz不等式，$?\Vert x\Vert \Vert v\Vert \le x^{T}v\le \Vert x\Vert \Vert v\Vert$，因此
$$\theta (u_1,u_2)\ge \min \{?\Vert x\Vert \Vert v\Vert :\Vert x\Vert \le 2\}=?2\Vert v\Vert ,?u_1,u_2$$當且僅當$$x=?\frac{2v}{\Vert v\Vert }$$時取等。因此
$$\theta (u_1,u_2)=?2\Vert v\Vert =?2\sqrt{(2?u_1{)}^2+(3?u_2{)}^2}$$

不難驗證這個是凹函數；

接下來演示一下幾何法求$\theta (u_1,u_2)$的表達式。
$$\theta (u_1,u_2)=\underset{x_1^2+x_2^2\le 4}{\min }{x}_1(2?u_1)+x_2(3?u_2)$$

可行域是圓心在原點，半徑為2的圓，目標函數是斜率為$\frac{2?u_1}{u_2?3}$的直線族的斜率，如果$\frac{2?u_1}{u_2?3}=0$，則$x_1=0,x_2=2$時函數值最小，此時$\theta (u_1,u_2)=6?2u_2$；如果$\frac{2?u_1}{u_2?3}<0$，則直線與圓在第三象限相切時函數值最小，對于圓而言，
$$2x_{1}d{x}_1+2x_{2}d{x}_2=0?\frac{d{x}_2}{d{x}_1}=?\frac{x_1}{x_2}=\frac{2?u_1}{u_2?3}$$

再根據$x_1^2+x_2^2=4$，不難解出
$$\{\begin{array}{l}{x}_1^2=\frac{4(2?u_1{)}^2}{(2?u_1{)}^2+(3?u_2{)}^2}\\ x_2^2=\frac{4(3?u_2{)}^2}{(2?u_1{)}^2+(3?u_2{)}^2}\end{array}$$

如果$\frac{2?u_1}{u_2?3}>0$，則直線與圓在第四象限相切時函數值最小，計算過程與上面這個相同。可以算出
$$\theta (u_1,u_2)=?2\sqrt{(2?u_1{)}^2+(3?u_2{)}^2}$$

顯然這個比$\theta (u_1,u_2)=6?2u_2$更小，綜上，
$$\theta (u_1,u_2)=?2\sqrt{(2?u_1{)}^2+(3?u_2{)}^2}$$

第二問：計算在$(2,3)$處的次梯度。次梯度的定義是
$f:S\to \mathbb{R}$ is concave where $S$ is a nonempty convex set. Then $\xi$ is called subgradient of $f$ at $\bar{x}$ if
$$f(x)\le f(\bar{x})+{\xi }^T(x?\bar{x}),?x\in S$$

根據這個定義，假設$\xi$是次梯度，則
$$\begin{gathered} \theta (u_1,u_2)\le \theta (2,3)+{\xi }^T[u_1?2,u_2?3{]}^T \\ \le {\xi }^T[u_1?2,u_2?3{]}^T \end{gathered}$$

根據第一問的不同證法，第二問也有兩種不同的計算方法：

方法一：如果第一問用的直接法，那么我們觀察一下
$$\begin{gathered} \theta (u_1,u_2)=\underset{x_1^2+x_2^2\le 4}{\min }{x}_1(2?u_1)+x_2(3?u_2) \\ ??x_1^2+x_2^2\le 4,\theta (u_1,u_2)\le x^T[u_1?2,u_2?3{]}^T \end{gathered}$$

把$x$換成$\xi$就是我們需要的結果，于是$\Vert \xi \Vert \le 2$，次梯度為
$$\{\xi :\Vert \xi \Vert \le 2\}$$

方法二：如果第一問用的解析法，那么我們已經知道了$$\theta (u_1,u_2)=?2\sqrt{(2?u_1{)}^2+(3?u_2{)}^2}$$

于是我們要做的是求解：
$$?2\sqrt{(2?u_1{)}^2+(3?u_2{)}^2}\le {\xi }^T[u_1?2,u_2?3{]}^T$$

也就是$2\Vert v\Vert \ge {\xi }^{T}v$，根據Cauchy-Schwarz定理，$\Vert \xi \Vert \le 2$時對所有$v\in {\mathbb{R}}^2$成立，所以次梯度為
$$\{\xi :\Vert \xi \Vert \le 2\}$$

總結

以上是生活随笔為你收集整理的UA SIE545 优化理论基础 例题 对偶函数的凸性与次梯度计算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。