【優化算法】限制優化

• 定義
• 簡單方法：映射-修改
• 複雜方法 ： 轉化為無限制優化問題
• 通用解決方案 – KKT 方法

定義

之前提到的梯度下降法，牛頓法都是在定義域全集上尋找函數 f(x) f ( x ) 的最大值或者最小值，但有時候，我們希望的不是全集，而是在 x x 的某個子集SS 中找到 f(x) f ( x ) 的最大值或者最小值。這稱為限制優化(constrained optimization)。 在優化術語中，集合 S S 内的點 x x 稱為

可行(feasible)點

.例如我們常常希望找到在某種意義上小的解，針對這種情況下的常見方法就是強加一個範數限制(norm constraint), 如 ∥x∥⩽1‖x‖⩽1.

簡單方法：映射-修改

限制優化的一個簡單方法是将限制考慮在内後簡單地對梯度下降進行修改。

• 如果使用一個小的恒定步長 ϵ ϵ , 我們可以先取梯度下降的單步結果，然後将結果投影回 S S .
• 如果使用線性搜尋，我們隻能在步長為 ϵ ϵ 範圍内搜尋可行的 x x 點， 或者可以将線上的每個點投影到限制區域。
• 如果可能，在梯度下降或線性搜尋前将梯度投影到可行域的切空間會更高效

複雜方法 ： 轉化為無限制優化問題

一種更複雜的方法是設計一個不同的、無限制的優化問題，其解可以轉化為原始限制優化問題的解。例如，我們要在 x∈R2x∈R2 中最小化 f(x) f ( x ) , 其中 x x 限制為具有機關 L2L2 範數。我們就可以構造關于 θ θ 最小化 g(θ)=f([cosθ,sinθ]T) g ( θ ) = f ( [ cos ⁡ θ , sin ⁡ θ ] T ) , 最後傳回 [cosθ,sinθ] [ cos ⁡ θ , sin ⁡ θ ] 作為原問題的解。

這種方法需要創造性；優化問題之間的轉換必須專門根據我們遇到的每一個情況進行設計。

通用解決方案 – KKT 方法

Karush-Kuhn-Tucker(KKT)方法

是針對限制優化非常通用的解決方案，形式上它是

隻允許等式限制的Lagrange乘子法

的推廣。為使用 KKT 方法，我們需要先引入一個新函數

廣義Lagrange函數(generalized Lagrange function)

.

為了定義 廣義Lagrange函數， 我們先要通過等式和不等式的形式描述 S S 。 我們希望通過 m m 個函數 g(i)g(i)和 n n 個函數hjhj來描述 S S , 那麼 S S 可以表示為

S={x|∀i,g(i)(x)=0 and ∀j,h(j)(x)≤0} S = { x | ∀ i , g ( i ) ( x ) = 0  and  ∀ j , h ( j ) ( x ) ≤ 0 }

. 其中

• 涉及 g(i) g ( i ) 的等式稱為

  等式限制(equality constraint)

• 涉及 h(j) h ( j ) 的不等式稱為

  不等式限制(inequality constraint)

我們為每個限制引入新的變量 λi λ i 和 αj α j , 這些新變量稱

KKT乘子

。廣義Lagrange函數可以定義為

L(x,λ,α)=f(x)+∑iλig(i)(x)+∑jαjh(j)(x) L ( x , λ , α ) = f ( x ) + ∑ i λ i g ( i ) ( x ) + ∑ j α j h ( j ) ( x )

, 現在，我們可以通過優化無限制的廣義Lagrange 函數來解決限制最小化問題。

隻要存在至少一個可行點且 f(x) f ( x ) 不允許取 ∞ ∞ , 那麼以下左右兩個函數具有相同的最優目标函數和最優點集 x x

minxmaxλmaxα,α>0L(x,λ,α)⇐⇒minx∈Sf(x)minxmaxλmaxα,α>0L(x,λ,α)⇐⇒minx∈Sf(x)

,

這是因為當限制滿足時，

maxλmaxα,α>0L(x,λ,α)=f(x) max λ max α , α > 0 L ( x , λ , α ) = f ( x )

, 而違反任意限制時， maxλmaxα,α>0L(x,λ,α)=∞ max λ max α , α > 0 L ( x , λ , α ) = ∞

. 這組性質保證了不可行點不會是最佳的，而可行點範圍内的最優點不變。

我們可以使用一組簡單的性質來描述限制優化問題的最優點。這些性質稱為

KKT條件

。這些事确定一個點事最優點的必要條件，但不一定是充分條件。這些條件是：

• 廣義Lagrange函數的梯度為零
• 所有關于 x x 和 KKT 乘子的限制都滿足
• 不等式限制顯示的互補松弛性： α⊙h(x)=0α⊙h(x)=0