almost 3 years ago

Introduction

在解「 有條件的最佳化問題 」時,有時需要把原本的問題轉換成對偶問題(Dual Problem)後,會比較好解。
如果對偶問題有最佳解,原本問題也有最佳解,且這兩個最佳解相同,則必須要滿足 Karush-Kuhn-Tucker (KKT) Conditions

  1. Primal Feasibility
  2. Dual Feasibility
  3. Complementary Slackness
  4. Stationarity

至於這四項到底是什麼?講起來有點複雜。本文會先從對偶問題的概念開始介紹,再來講解這四個條件。

The Lagrange dual function

首先,講解一下什麼是對偶問題。
通常,有條件的最佳化問題,可寫成 <公式一>

其中, 是目標函數,而 為不等式的條件限制, 為等式的條件限制。也就是說,最佳化的目標是要求出 得出最小值,而這個 ,必須滿足 所限定的條件。若滿足這兩項條件,則表示這個最佳化問題有解,即為滿足 primal feasibility

此最佳化問題可以轉換成對偶問題,如下:

其中,我們把 稱為 Lagrangian 稱為 Lagrange multiplier

所謂的對偶函數( Lagrange dual function ),即是在給定了 Lagrange multiplier 之下,改變 來得出 Lagrangian 最小值,如下:

其中, 為對偶函數,而 即是在改變 的情況下,找出最小值。

Lower bounds on optimal value

接著來證明,對偶函數可當作原本問題的 Lower Bound 。設原本問題公式一的最佳解為 ,則在所有 (記作 )和 為任意數的情況下,會滿足以下條件:

此性質不難證明,對於所有滿足 這兩個條件的 ,必滿足:

則:

設原本問題公式一最佳解時的 ,由於 必須滿足 滿足 這兩個條件,又因 ,故 成立。

舉個例子,下圖中,黑色的實線為目標函數 ,此最佳化問題有一個不等式條件限制 ,用綠色虛線表示,而滿足於 範圍落在 之間,範圍用兩條鉛直的紅色虛線表示。 紫色的圓圈為最佳解的點 。此最佳化問題沒有等式條件,故沒有 。則此問題的 Lagrangian 。藍色的點為 所畫出來的 Lagrangian 圖形。

在上圖中,兩條紅色虛線之間的範圍內,即 滿足不等式的條件限制 ,此時藍色的虛線皆位於黑色線的下方,滿足

下圖畫出改變不同 值時,對偶函數 的值,其中,黑色的實線為 ,紫色的虛線為 的值( )。

根據此圖,黑色的線恆在紫色的虛線下方,滿足

The Lagrange dual problem

所謂的對偶問題(Lagrange dual problem)即是把原本的問題轉成對偶函數之後,來解最佳化問題。

從前面結論可得知,對偶函數若滿足 (也就是所有的 都滿足 )的條件,則必足 。如果想找出最接近 的對偶函數解,則可藉由改變 ,來找出 的最大值。此對偶問題如下 <公式二>

如果可以找出一組解,滿足 ,可得出 的最大值 ,則此問題滿足 dual feasibility

根據對偶問題的解 和原本問題的解 的關係,可將對偶性質分為 weak dualitystrong duality 兩類:

Weak duality

若對偶問題的解,小於或等於原本問題的解,即滿足 weak duality

根據前面段落 Lower bounds on optimal value 所推導的結論, Weak duality 必定成立。

Strong duality

若對偶問題的解,等於原本問題的解,即滿足 strong duality

這個條件不一定會成立,如果要成立的話,原本問題公式一的中的 要是凸函數,但即使滿足此條件,仍須滿足其他條件才能使 strong duality 成立,這講起來比較複雜,在此先不提。

Complementary Slackness

設原本問題最佳解的 ,對偶問題最佳解的 ,根據對偶函數 的定義,和前面段落 Lower bounds on optimal value 所推導出的結論,可得出:

若對偶問題滿足 strong duality

則須滿足:

由於 為原本問題的等式條件限制,故 (b) 必會成立,若 (a) 要成立的話,須滿足:

也就是說, 的其中一項必須為零,不可以兩項都不為零。這種情形稱為 complementary slackness ,也就是林軒田教授在機器學習技法課程中所提到的:

哈利波特和佛地魔,其中一個必須死掉。

Karush-Kuhn-Tucker (KKT) conditions

KKT conditions 即為下四個條件:

  1. Primal Feasibility:即滿足原本問題公式一的限制條件 ,使原本問題有解。
  2. Dual Feasibility:即滿足對偶問題公式二的限制條件: ,使對偶問題有解。
  3. Complementary Slackness:即滿足 strong duality ,使原本問題和對偶問題有相同解。
  4. Stationarity(gradient of Lagrangian with respect to x vanishes):

第四項雖然前面沒提到,但很容易理解,也就是說,在得出最佳解 的時候, Lagrangian 對於 gradient 要等於 0 。

Reference

本文參考至以下教科書,本文中的圖片也取自於以下教科書:
Stephen Boyd & Lieven Vandenberghe. Convex Optimization. Chapter 5 Duality.

← 類神經網路 -- Neural Turing Machine Optimization Method -- Gradient Descent & AdaGrad →
 
comments powered by Disqus