凸優化──凸函數的最小化

本文的閱讀等級:中級

凸優化 (convex optimization) 是最佳化理論的一個分支。顧名思義,凸優化探討定義於一個凸集的凸函數最小化問題[1]。令 K\subset\mathbb{R}^n 為凸集且 f:K\to\mathbb{R} 為凸函數。我們的目標要找出一個點 \mathbf{x}^\star\in K,使得每一 \mathbf{x}\in K 滿足 f(\mathbf{x}^\star)\le f(\mathbf{x})。在最佳化理論中,K 稱為可行域 (feasible set),f 稱為目標函數,\mathbf{x}^\star 稱為全域最佳解[2]。任一凸優化問題皆可表示為下列標準型:

\displaystyle  \begin{array}{lll}  \min&f(\mathbf{x})&\\  \hbox{subject to}&g_i(\mathbf{x})\le 0,&i=1,\ldots,m\\  &h_j(\mathbf{x})=0,&j=1,\ldots,p,  \end{array}

其中 f, g_1,\ldots,g_m:\mathbb{R}^n\to\mathbb{R} 是凸函數,h_1,\ldots,h_p 是仿射函數,即 h_j(\mathbf{x})=\mathbf{a}_j^T\mathbf{x}+b_j\mathbf{a}_j\in\mathbb{R}^nb_j\in\mathbb{R}。最小平方法與線性規劃是兩種常見的凸優化問題。令 A 為一個 m\times n 階實矩陣,\mathbf{b}m 維實向量,\mathbf{c}n 維實向量。最小平方法是一個無約束 (unconstrained) 最佳化問題:

\displaystyle  \min_{\mathbf{x}\in\mathbb{R}^n}\Vert \mathbf{b}-A\mathbf{x}\Vert^2

線性規劃標準型問題具有下列形式 (見“線性規劃 (一):標準型問題”):

\begin{array}{lll}  \min& \mathbf{c}^T\mathbf{x} \\  \mathrm{subject~to}& A\mathbf{x}=\mathbf{b}, ~~\mathbf{x}\ge\mathbf{0}.  \end{array}

本文介紹凸優化的一個重要性質:任一局部最佳解 (亦稱相對最佳解) 即為全域最佳解。所謂局部最佳解 \mathbf{x}^\star\in K 是指存在 \delta>0 使得集合 \{\mathbf{x}\vert\Vert\mathbf{x}-\mathbf{x}^\star\Vert<\delta,\mathbf{x}\in K\} 中每一點 \mathbf{x} 滿足 f(\mathbf{x}^\star)\le f(\mathbf{x})

 
定理一:若 f 是定義於凸集 K 的凸函數,則最佳解所形成的集合為一個凸集,且任一局部最佳解皆為全域最佳解。

如果目標函數 f 不存在局部最佳解,譬如 f(x)=x,我們默認定理成立。下面考慮最佳解存在的情況,設 c=\min_{\mathbf{x}\in K}f(\mathbf{x})。所有最佳解組成的集合可表示為 L_c^-(f)=\{\mathbf{x}\vert f(\mathbf{x})\le c,\mathbf{x}\in K\},稱為下水平集 (sublevel set)。因為 f 是凸集合,L_c^-(f) 必為凸集 (見“凸函數”,定理四)。令 \mathbf{x}^\star\in Kf 的一個局部最佳解。假設存在另一點 \mathbf{y}\in K 滿足 f(\mathbf{y})<f(\mathbf{x}^\star)。令 \mathbf{z}=\lambda\mathbf{y}+(1-\lambda)\mathbf{x}^\star,其中 0<\lambda<1。使用凸函數定義,可得

\displaystyle  f(\mathbf{z})=f\left(\lambda\mathbf{y}+(1-\lambda)\mathbf{x}^\star\right)\le\lambda f(\mathbf{y})+(1-\lambda)f(\mathbf{x}^\star)< f(\mathbf{x}^\star)

\lambda\to 0\mathbf{z}=\mathbf{x}^\star+\lambda(\mathbf{y}-\mathbf{x}^\star) 非常靠近 \mathbf{x}^\star,上式與 \mathbf{x}^\star 是一個局部最佳解的假設相矛盾,故證明局部最佳解 \mathbf{x}^\star 滿足 f(\mathbf{x}^\star)=c

 
定理一說明兩件事:如果存在一個局部最佳解,則該解為全域最佳解;所有的 (全域) 最佳解構成一個凸集。如果目標函數 f 連續可導,我們還可以得到全域最佳解的充分條件,見下面定理。

定理二:令 K\subset\mathbb{R}^n 為凸集,f:K\to\mathbb{R} 為凸函數,且 f\in C^1。若存在一點 \mathbf{x}^\star\in K 使得所有 \mathbf{y}\in K\nabla f(\mathbf{x}^\star)^T(\mathbf{y}-\mathbf{x}^\star)\ge 0,則 \mathbf{x}^\starfK 的全域最佳解。

證明使用此性質 (見“凸函數”,定理五):若 f 是凸函數,則對於任意 \mathbf{x},\mathbf{y}\in K

\displaystyle    f(\mathbf{y})\ge f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})

\mathbf{x}^\star 取代 \mathbf{x},可得

\displaystyle    f(\mathbf{y})\ge f(\mathbf{x}^\star)+\nabla f(\mathbf{x}^\star)^T(\mathbf{y}-\mathbf{x}^\star)\ge f(\mathbf{x}^\star)

 
近代常用的凸優化算法包括次梯度法 (subgradient method) 和內點法 (interior-point method)。有興趣深入了解的讀者請參閱維基百科介紹[3]或查詢非線性規劃 (nonlinear programming) 專門書籍。

 
註解:
[1] 一個向量集 K\subset\mathbb{R}^n 稱為凸集 (見“凸組合、凸包與凸集”),若給定任兩點 \mathbf{x},\mathbf{y}\in K0<\lambda<1,點 \lambda\mathbf{x}+(1-\lambda)\mathbf{y} 屬於 K 。一個函數 f:K\to\mathbb{R} 稱為凸函數 (見“凸函數”),若給定任兩點 \mathbf{x},\mathbf{y}\in K0<\lambda<1

\displaystyle  f\left(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\right)\le \lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y})

傳統上,凸優化設定為凸函數的最小化問題。若凸函數 f 定義於一個有界閉凸集 K,從直觀可推斷使 f 最大化的最佳解發生於 K 的端點。
[2] 這裡 \mathbf{x}^\star 代表最佳解,請勿與共軛轉置 \mathbf{x}^\ast=\overline{\mathbf{x}}^T 相混淆。
[3] 維基百科:次梯度法內點法

Advertisements
本篇發表於 線性代數專欄, 仿射幾何 並標籤為 , , , 。將永久鏈結加入書籤。

2 則回應給 凸優化──凸函數的最小化

  1. levinc417 說道:

    若待解問題不凸或不夠凸要怎麼凸化?

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s