【機器學習之數學】03 有約束的非線性優化問題——拉格朗日乘子法、KKT條件、投影法

目錄

  • 1 將有約束問題轉化為無約束問題
    • 1.1 拉格朗日法
      • 1.1.1 KKT條件
      • 1.1.2 拉格朗日法更新方程
      • 1.1.3 凸優化問題下的拉格朗日法
    • 1.2 罰函數法
  • 2 對梯度算法進行修改,使其運用在有約束條件下
    • 2.1 投影法
      • 2.1.1 梯度下降法 to 投影梯度法
      • 2.1.2 正交投影算子
  • References
  • 相關博客

梯度下降法、最速下降法、牛頓法等迭代求解方法,都是在無約束的條件下使用的,而在有約束的問題中,直接使用這些梯度方法會有問題,如更新后的值不滿足約束條件。

那麼問題來了,如何處理有約束的優化問題?大致可以分為以下兩種方式:

  1. 將有約束的問題轉化為無約束的問題,如拉格朗日乘子法和KKT條件;
  2. 對無約束問題下的求解算法進行修改,使其能夠運用在有約束的問題中,如對梯度下降法進行投影,使得更新后的值都滿足約束條件。

1 將有約束問題轉化為無約束問題

1.1 拉格朗日法

僅含等式約束的優化問題
\[ \begin{array}{cl}{\text { minimize }} & {f(\boldsymbol{x})} \\ {\text { subject to }} & {\boldsymbol{h}(\boldsymbol{x})=\mathbf{0}}\end{array} \]

其中,\(x \in \mathbb{R}^n\)\(f : \mathbb{R}^{n} \rightarrow \mathbb{R}\)\(\boldsymbol{h} : \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}, \boldsymbol{h}=\left[h_{1}, \ldots, h_{m}\right]^{\top}, \text { and } m \leq n\)

該問題的拉格朗日函數為:
\[ l(\boldsymbol{x}, \boldsymbol{\lambda})=f(\boldsymbol{x})+\boldsymbol{\lambda}^{\top} \boldsymbol{h}(\boldsymbol{x}) \]

FONC:對拉格朗日函數 \(l(\boldsymbol{x}, \boldsymbol{\lambda})\) 求偏導數,令偏導數都等於 0,求得的解必然滿足原問題的等式約束,可以從這些解裏面尋找是否有局部最優解。這是求得局部最優解的一階必要條件。

拉格朗日條件:(分別對 \(\bm x\)\(\bm \lambda\) 求偏導)
\[ \begin{array}{l}{D_{x} l\left(\boldsymbol{x}^{*}, \boldsymbol{\lambda}^{*}\right)=\mathbf{0}^{\top}} \\ {D_{\lambda} l\left(\boldsymbol{x}^{*}, \boldsymbol{\lambda}^{*}\right)=\mathbf{0}^{\top}}\end{array} \]

上式中,對 \(\lambda\) 求偏導數得到的就是等式約束。

拉格朗日條件是必要而非充分條件,即滿足上述方程的點 \(\boldsymbol x^{*}\) 不一定是極值點。

1.1.1 KKT條件

既含等式約束又含不等式約束的優化問題:
\[ \begin{array}{rl}{\operatorname{minimize}} & {f(\boldsymbol{x})} \\ {\text { subject to }} & {\boldsymbol{h}(\boldsymbol{x})=\mathbf{0}} \\ {} & {\boldsymbol{g}(\boldsymbol{x}) \leq \mathbf{0}}\end{array} \]

其中,\(f : \mathbb{R}^{n} \rightarrow \mathbb{R}\)\(\boldsymbol{h} : \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}, m \leq n\),並且 \(\boldsymbol{g} : \mathbb{R}^{n} \rightarrow \mathbb{R}^{p}\)

將該問題轉化為拉格朗日形式:
\[ l(\boldsymbol{x}, \boldsymbol{\lambda})=f(\boldsymbol{x})+\boldsymbol{\lambda}^{\top} \boldsymbol{h}(\boldsymbol{x}) +\boldsymbol{\mu}^{\top} \boldsymbol{g}(\boldsymbol{x}) \]

\(\bm x^{*}\) 是原問題的一個局部極小點,則必然存在 \(\bm{\lambda}^{* \top} \in \mathbb{R}^m\)\(\bm{\mu}^{* \top} \in \mathbb{R}^p\),使得下列KKT條件成立:

  1. \(\bm {\mu}^{*} \geq 0\)
  2. \(D f\left(\boldsymbol{x}^{*}\right)+\boldsymbol{\lambda}^{* \top} D \boldsymbol{h}\left(\boldsymbol{x}^{*}\right)+\boldsymbol{\mu}^{* \top} D \boldsymbol{g}\left(\boldsymbol{x}^{*}\right)=\mathbf{0}^{\top}\)
  3. \(\boldsymbol{\mu}^{* \top} \boldsymbol{g}\left(\boldsymbol{x}^{*}\right)=0\)
  4. \({\boldsymbol{h}(\boldsymbol{x}^*)=\mathbf{0}}\)
  5. \({\boldsymbol{g}(\boldsymbol{x}^*) \leq \mathbf{0}}\)

KKT條件中,\(\bm{\lambda}^{*}\) 是拉格朗日乘子向量,\(\bm{\mu}^{*}\) 是KKT乘子向量,\(\bm{\lambda}^{*}\)\(\bm{\mu}^{*}\) 的元素分別稱為拉格朗日乘子和KKT乘子。

1.1.2 拉格朗日法更新方程

將含約束的優化問題轉化為拉格朗日形式后,我們可以用更新方程對該問題進行迭代求解。

這也是一種梯度算法,但拉格朗日乘子、KKT 乘子的更新和自變量 \(\bm x\) 的更新不同,自變量 \(\bm x\) 繼續採用梯度下降法更新,而拉格朗日乘子、KKT 乘子的更新方程如下:
\[ \boldsymbol{\lambda}^{(k+1)}=\boldsymbol{\lambda}^{(k)}+\beta_{k} \boldsymbol{h}\left(\boldsymbol{x}^{(k)}\right), \\ \boldsymbol{\mu}^{(k+1)}=\left[\boldsymbol{\mu}^{(k)}+\beta_{k} \boldsymbol{g}\left(\boldsymbol{x}^{(k)}\right)\right]_{+} \]

其中,\([\cdot]_{+}=\max \{\cdot, 0\}\)

1.1.3 凸優化問題下的拉格朗日法

拉格朗日乘子法和KKT條件在一般的含約束條件的優化問題中,都只是一階必要條件,而在凸優化問題中,則變成了充分條件。

凸優化問題指的是目標函數是凸函數,約束集是凸集的優化問題。線性規劃、二次規劃(目標函數為二次型函數、約束方程為線性方程)都可以歸為凸優化問題。

凸優化問題中,局部極小點就是全局極小點。極小點的一階必要條件就是凸優化問題的充分條件。

1.2 罰函數法

考慮一般形式的有約束優化問題:
\[ \begin{array}{cl}{\operatorname{minimize}} & {f(\boldsymbol{x})} \\ {\text { subject to }} & {\boldsymbol{x} \in \Omega}\end{array} \]

將問題變為如下無約束的形式:
\[ \operatorname{minimize} f(\boldsymbol{x})+\gamma P(\boldsymbol{x}) \]

其中,\(\gamma\) 是懲罰因子,\(P : \mathbb{R}^{n} \rightarrow \mathbb{R}\) 是罰函數。求解該無約束優化問題,把得到的解近似作為原問題的極小點。

罰函數需要滿足以下 3 個條件:

  1. \(\bm P\) 是連續的;
  2. 對所有 \(\bm x \in \mathbb{R}^n\)\(P(\boldsymbol{x}) \ge 0\) 成立;
  3. \(P(\boldsymbol{x})=0\),當且僅當 \(\bm x\) 是可行點(即 \({\bm{x} \in \Omega}\))。

2 對梯度算法進行修改,使其運用在有約束條件下

2.1 投影法

梯度下降法、最速下降法、牛頓法等優化算法都有通用的迭代公式:
\[ \boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}+\alpha_{k} \boldsymbol{d}^{(k)} \]

其中,\(\boldsymbol{d}^{(k)}\) 是關於梯度 \(\nabla f(\bm x^{(k)})\) 的函數,如在梯度下降法中,\(\boldsymbol{d}^{(k)} = -\nabla f(\bm x^{(k)})\)

考慮優化問題:
\[ \begin{array}{cl}{\operatorname{minimize}} & {f(\boldsymbol{x})} \\ {\text { subject to }} & {\boldsymbol{x} \in \Omega}\end{array} \]

在上述有約束的優化問題中,\(\boldsymbol{x}^{(k)}+\alpha_{k} \boldsymbol{d}^{(k)}\) 可能不在約束集 \(\Omega\) 內,這是梯度下降等方法無法使用的原因。

而投影法做的是,如果 \(\boldsymbol{x}^{(k)}+\alpha_{k} \boldsymbol{d}^{(k)}\) 跑到約束集 \(\Omega\) 外面去了,那麼將它投影到約束集內“最接近”的點;如果 \(\boldsymbol{x}^{(k)}+\alpha_{k} \boldsymbol{d}^{(k)} \in \Omega\),那麼正常更新即可。

投影法的更新公式為:
\[ \boldsymbol{x}^{(k+1)}=\boldsymbol{\Pi}\left[\boldsymbol{x}^{(k)}+\alpha_{k} \boldsymbol{d}^{(k)}\right] \]

其中 \(\bm \Pi\) 為投影算子,\(\bm \Pi[\bm x]\) 稱為 \(\bm x\)\(\Omega\) 上的投影。

2.1.1 梯度下降法 to 投影梯度法

梯度下降法的迭代公式為:
\[ \boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}-\alpha_{k} \nabla f\left(\boldsymbol{x}^{(k)}\right) \]

將投影算法引入梯度下降法,可得投影梯度法,迭代公式如下:
\[ \boldsymbol{x}^{(k+1)}=\boldsymbol{\Pi}\left[\boldsymbol{x}^{(k)}-\alpha_{k} \nabla f\left(\boldsymbol{x}^{(k)}\right)\right] \]

2.1.2 正交投影算子

含線性約束優化問題的投影梯度法可以利用正交投影算子來更新 \(\bm x^{(k)}\)

含線性約束的優化問題如下所示:
\[ \begin{array}{cl}{\operatorname{minimize}} & {f(\boldsymbol{x})} \\ {\text { subject to }} & {\boldsymbol{A x}=\boldsymbol{b}}\end{array} \]

其中,\(f : \mathbb{R}^{n} \rightarrow \mathbb{R}\)\(\boldsymbol{A} \in \mathbb{R}^{m \times n}, m<n\)\(\operatorname{rank} \boldsymbol{A}=m, \boldsymbol{b} \in \mathbb{R}^{m}\),約束集 \(\Omega=\{\boldsymbol{x} :\boldsymbol{A} \boldsymbol{x}=\boldsymbol{b} \}\)

這種情況下,正交投影算子矩陣 \(\bm P\) 為:
\[ \boldsymbol{P}=\boldsymbol{I}_{n}-\boldsymbol{A}^{\top}\left(\boldsymbol{A} \boldsymbol{A}^{\top}\right)^{-1} \boldsymbol{A} \]

正交投影算子 \(\bm P\) 有兩個重要性質:

  1. \(P=P^{\top}\).
  2. \(P^{2}=P\).

在投影梯度算法中,可以按照如下公式更新 \(\bm x^{(k)}\)
\[ \boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}-\alpha_{k} \boldsymbol{P} \nabla \boldsymbol{f}(\boldsymbol{x}^{(k)}) \]

References

Edwin K. P. Chong, Stanislaw H. Zak-An Introduction to Optimization, 4th Edition

相關博客

【機器學習之數學】01 導數、偏導數、方嚮導數、梯度
【機器學習之數學】02 梯度下降法、最速下降法、牛頓法、共軛方向法、擬牛頓法
【機器學習之數學】03 有約束的非線性優化問題——拉格朗日乘子法、KKT條件、投影法

【精選推薦文章】

智慧手機時代的來臨,RWD網頁設計已成為網頁設計推薦首選

想知道網站建置、網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計及後台網頁設計

帶您來看台北網站建置台北網頁設計,各種案例分享

廣告預算用在刀口上,網站設計公司幫您達到更多曝光效益

您可能也會喜歡…