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

梯度下降法、最速下降法、牛頓法等疊代求解方法，都是在無限制的條件下使用的，而在有限制的問題中，直接使用這些梯度方法會有問題，如更新後的值不滿足限制條件。如何處理有限制的優化問題？大緻可以分為以下兩種方式：

1. 将有限制的問題轉化為無限制的問題，如拉格朗日乘子法和KKT條件；

2. 對無限制問題下的求解算法進行修改，使其能夠運用在有限制的問題中，如對梯度下降法進行投影，使得更新後的值都滿足限制條件。

目錄

• 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. 對無限制問題下的求解算法進行修改，使其能夠運用在有限制的問題中，如對梯度下降法進行投影，使得更新後的值都滿足限制條件。

僅含等式限制的優化問題

\[\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^{*}\) 不一定是極值點。

既含等式限制又含不等式限制的優化問題：

\[\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乘子。

将含限制的優化問題轉化為拉格朗日形式後，我們可以用更新方程對該問題進行疊代求解。

這也是一種梯度算法，但拉格朗日乘子、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\}\)。

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

凸優化問題指的是目标函數是凸函數，限制集是凸集的優化問題。線性規劃、二次規劃（目标函數為二次型函數、限制方程為線性方程）都可以歸為凸優化問題。

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

考慮一般形式的有限制優化問題：

\[\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}\)）。

梯度下降法、最速下降法、牛頓法等優化算法都有通用的疊代公式：

\[\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)})\)。

考慮優化問題：

在上述有限制的優化問題中，\(\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\) 上的投影。

梯度下降法的疊代公式為：

\[\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]

含線性限制優化問題的投影梯度法可以利用正交投影算子來更新 \(\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)})

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

【機器學習之數學】01 導數、偏導數、方向導數、梯度

【機器學習之數學】02 梯度下降法、最速下降法、牛頓法、共轭方向法、拟牛頓法

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

作者：wuliytTaotao

出處：https://www.cnblogs.com/wuliytTaotao/

本作品采用知識共享署名-非商業性使用-相同方式共享 4.0 國際許可協定進行許可，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接。