AI學習指南數學工具篇-凸優化之對偶性與拉格朗日對偶
在凸優化中，對偶性是一個非常重要的概念。通過對偶性，我們可以將原始問題轉化為對偶問題，從而更容易求解。其中，拉格朗日對偶問題是對偶性的一個重要應用，通過拉格朗日對偶問題，我們可以得到原始問題的最優解。本篇博客將重點介紹對偶性及拉格朗日對偶問題，并通過詳細的示例來解釋其求解過程。
1. 對偶問題的定義
在凸優化中，對偶問題是指通過原始問題構造一個與之等價的問題，稱為對偶問題。對偶問題通常可以更容易求解，而且其最優解可以用來得到原始問題的最優解。
對于凸優化問題：
minimize f 0 ( x ) subject?to f i ( x ) ≤ 0 , i = 1 , 2 , . . . , m h i ( x ) = 0 , i = 1 , 2 , . . . , p \begin{aligned} \text{minimize} \quad & f_0(x) \\ \text{subject to} \quad & f_i(x) \leq 0, \quad i = 1,2,...,m \\ & h_i(x) = 0, \quad i = 1,2,...,p \end{aligned} minimizesubject?to?f0?(x)fi?(x)≤0,i=1,2,...,mhi?(x)=0,i=1,2,...,p?
其中， f 0 ( x ) f_0(x) f0?(x) 是目標函數， f i ( x ) f_i(x) fi?(x) 是不等式約束， h i ( x ) h_i(x) hi?(x) 是等式約束。
其對偶問題為：
maximize g ( λ , ν ) subject?to λ ≥ 0 \begin{aligned} \text{maximize} \quad & g(\lambda, \nu) \\ \text{subject to} \quad & \lambda \geq 0 \end{aligned} maximizesubject?to?g(λ,ν)λ≥0?
其中， g ( λ , ν ) g(\lambda, \nu) g(λ,ν) 是對偶函數， λ \lambda λ 是不等式約束的拉格朗日乘子， ν \nu ν 是等式約束的拉格朗日乘子。
2. 對偶問題與原始問題的關系
對偶問題與原始問題之間存在一種緊密的關系，它們互為最優化問題的等價形式。具體來說，對于原始問題的最優解 x ? x^* x?和對偶問題的最優解 ( λ ? , ν ? ) (\lambda^*, \nu^*) (λ?,ν?)，有以下關系成立：
- 若 x ? x^* x?是原始問題的最優解，則存在 ( λ ? , ν ? ) (\lambda^*, \nu^*) (λ?,ν?)使得 g ( λ ? , ν ? ) = f 0 ( x ? ) g(\lambda^*, \nu^*) = f_0(x^*) g(λ?,ν?)=f0?(x?)，即對偶問題的最優值等于原始問題的最優值；
- 若 ( λ ? , ν ? ) (\lambda^*, \nu^*) (λ?,ν?)是對偶問題的最優解，則存在 x ? x^* x?使得 f 0 ( x ? ) = g ( λ ? , ν ? ) f_0(x^*) = g(\lambda^*, \nu^*) f0?(x?)=g(λ?,ν?)，即原始問題的最優值等于對偶問題的最優值。
這些關系為我們提供了一種通過對偶問題求解原始問題的方法，也為原始問題的最優解提供了一種判定條件。
3. 拉格朗日對偶問題的求解
3.1 對偶函數的定義
在介紹拉格朗日對偶問題的求解過程之前，我們需要先定義對偶函數。對于原始問題：
minimize f 0 ( x ) subject?to f i ( x ) ≤ 0 , i = 1 , 2 , . . . , m h i ( x ) = 0 , i = 1 , 2 , . . . , p \text{minimize} \quad f_0(x) \\ \text{subject to} \quad f_i(x) \leq 0, \quad i = 1,2,...,m \\ h_i(x) = 0, \quad i = 1,2,...,p minimizef0?(x)subject?tofi?(x)≤0,i=1,2,...,mhi?(x)=0,i=1,2,...,p
其拉格朗日函數定義為：
L ( x , λ , ν ) = f 0 ( x ) + ∑ i = 1 m λ i f i ( x ) + ∑ i = 1 p ν i h i ( x ) L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \sum_{i=1}^{p} \nu_i h_i(x) L(x,λ,ν)=f0?(x)+i=1∑m?λi?fi?(x)+i=1∑p?νi?hi?(x)
其中， λ \lambda λ和 ν \nu ν分別是不等式約束和等式約束的拉格朗日乘子。
對偶函數 g ( λ , ν ) g(\lambda, \nu) g(λ,ν)定義為原始問題的拉格朗日函數 L ( x , λ , ν ) L(x, \lambda, \nu) L(x,λ,ν)關于 x x x的下確界：
g ( λ , ν ) = inf ? x L ( x , λ , ν ) g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu) g(λ,ν)=xinf?L(x,λ,ν)
3.2 求解拉格朗日對偶問題
對于原始問題和對偶問題的關系，我們有以下結論：
- 若原始問題是凸優化問題，并且滿足一定條件（如Slater條件），則對偶問題也是凸優化問題；
- 對于凸優化問題的對偶問題，其最優解可以通過對偶函數的解析形式來求解。
下面通過一個具體的凸優化問題和其拉格朗日對偶問題來示例求解過程。
示例：原始問題
考慮以下凸優化問題：
minimize f 0 ( x ) = ( x ? 1 ) 2 subject?to f 1 ( x ) = x ≤ 3 \begin{aligned} \text{minimize} \quad & f_0(x) = (x-1)^2 \\ \text{subject to} \quad & f_1(x) = x \leq 3 \end{aligned} minimizesubject?to?f0?(x)=(x?1)2f1?(x)=x≤3?
其拉格朗日函數為：
L ( x , λ ) = ( x ? 1 ) 2 + λ ( x ? 3 ) L(x, \lambda) = (x-1)^2 + \lambda(x-3) L(x,λ)=(x?1)2+λ(x?3)
對偶函數為：
g ( λ ) = inf ? x ( x ? 1 ) 2 + λ ( x ? 3 ) g(\lambda) = \inf_{x} (x-1)^2 + \lambda(x-3) g(λ)=xinf?(x?1)2+λ(x?3)
接下來，我們需要求解對偶函數 g ( λ ) g(\lambda) g(λ)的最優值。由于原始問題是凸優化問題，并且滿足Slater條件（存在嚴格可行解），對偶問題也是凸優化問題。因此，我們可以通過對偶函數的解析形式（最優解的解析形式）來求解對偶問題。
對 g ( λ ) g(\lambda) g(λ)關于 x x x進行求導，并令導數等于0，得到 x ? x^* x?關于 λ \lambda λ的表達式：
? ? x [ ( x ? 1 ) 2 + λ ( x ? 3 ) ] = 0 2 ( x ? 1 ) + λ = 0 x ? = 1 ? λ 2 \frac{\partial}{\partial x} [(x-1)^2 + \lambda(x-3)] = 0 \\ 2(x-1) + \lambda = 0 \\ x^* = 1 - \frac{\lambda}{2} ?x??[(x?1)2+λ(x?3)]=02(x?1)+λ=0x?=1?2λ?
將 x ? x^* x?代入對偶函數 g ( λ ) g(\lambda) g(λ)，得到對偶問題的最優解：
g ( λ ) = ( 1 ? λ 2 ? 1 ) 2 + λ ( 1 ? λ 2 ? 3 ) = λ 2 4 ? 3 λ 2 + 4 g(\lambda) = (1 - \frac{\lambda}{2} - 1)^2 + \lambda(1 - \frac{\lambda}{2} - 3) \\ = \frac{\lambda^2}{4} - \frac{3\lambda}{2} + 4 g(λ)=(1?2λ??1)2+λ(1?2λ??3)=4λ2??23λ?+4
因此，原始問題的最優解 x ? x^* x?和對偶問題的最優解 λ ? \lambda^* λ?的關系為：
x ? = 1 ? λ ? 2 x^* = 1 - \frac{\lambda^*}{2} x?=1?2λ??
通過對偶問題的最優解 λ ? \lambda^* λ?，我們可以通過上述關系得到原始問題的最優解 x ? x^* x?。
4. 總結
本篇博客介紹了對偶問題的定義，以及對偶問題與原始問題的關系。同時，通過詳細的示例，介紹了拉格朗日對偶問題的求解過程。對偶性及拉格朗日對偶問題是凸優化中的重要概念，對于理解凸優化問題的求解過程具有重要的意義。希望通過本篇博客的介紹，讀者能夠更好地理解對偶性及拉格朗日對偶問題，并在實際問題中更加靈活地運用這些概念。
：機器閱讀理解-基礎概念解析01)
