深圳網(wǎng)站優(yōu)化教程廣州seo優(yōu)化電話
引言
本文簡單地介紹一些凸優(yōu)化(Convex Optimization)的基礎(chǔ)知識(shí),可能不會(huì)有很多證明推導(dǎo),目的是能快速應(yīng)用到機(jī)器學(xué)習(xí)問題上。
凸集
直線與線段
設(shè) x 1 ≠ x 2 x_1 \neq x_2 x1?=x2?為 R n \Bbb R^n Rn空間中的兩個(gè)點(diǎn),那么具有下列形式的點(diǎn)
y = θ x 1 + ( 1 ? θ ) x 2 , θ ∈ R y= \theta x_1 + (1-\theta)x_2,\, \theta \in \Bbb R y=θx1?+(1?θ)x2?,θ∈R
組成一條穿越 x 1 x_1 x1?和 x 2 x_2 x2?的直線。
如果參數(shù) θ \theta θ的值在 0 0 0到 1 1 1之間變動(dòng),就構(gòu)成了 x 1 x_1 x1?和 x 2 x_2 x2?之間的線段。
仿射集合
如果通過集合 C ? R n C \subseteq \Bbb R^n C?Rn中任意兩個(gè)不同點(diǎn)的直線仍然在集合 C C C中,那么稱集合 C C C是仿射的。
可以擴(kuò)展到多個(gè)點(diǎn)的情況,如果 θ 1 + ? + θ k = 1 \theta_1+ \cdots + \theta_k=1 θ1?+?+θk?=1,我們稱具有 θ 1 x 1 + ? + θ k x k \theta_1 x_1 + \cdots + \theta_k x_k θ1?x1?+?+θk?xk?形式的點(diǎn)為 x 1 , ? , x k x_1,\cdots, x_k x1?,?,xk?的仿射組合。
凸集
首先來了解下什么是凸集(Convex Set)。
集合 C C C被稱為凸集,如果 C C C中任意兩點(diǎn)間的線段仍然在 C C C中,即對(duì)于任意 x 1 , x 2 ∈ C x_1,x_2 \in C x1?,x2?∈C和滿足 0 ≤ θ ≤ 1 0\leq \theta \leq 1 0≤θ≤1的 θ \theta θ都有
θ x 1 + ( 1 ? θ ) x 2 ∈ C (1) \theta x_1 + (1-\theta)x_2 \in C \tag{1} θx1?+(1?θ)x2?∈C(1)
直觀上來看,凸集的形狀是飽滿的,即沒有凹進(jìn)去的地方。
我們稱
θ x 1 + ( 1 ? θ ) x 2 (2) \theta x_1 + (1-\theta)x_2 \tag{2} θx1?+(1?θ)x2?(2)
為點(diǎn) x 1 , x 2 x_1,x_2 x1?,x2?的凸組合,類似地,可以推廣到多個(gè)點(diǎn):
θ 1 x 1 + ? + θ k x k (3) \theta_1 x_1 + \cdots + \theta_kx_k \tag{3} θ1?x1?+?+θk?xk?(3)
為點(diǎn) x 1 , ? , x k x_1,\cdots,x_k x1?,?,xk?的一個(gè)凸組合,其中 θ 1 + ? + θ k = 1 \theta_1 + \cdots + \theta_k=1 θ1?+?+θk?=1且 θ i ≥ 0 , i = 1 , ? , k \theta_i \geq 0, \, i=1,\cdots,k θi?≥0,i=1,?,k。
一個(gè)集合是凸集也可以說集合包含其中所有點(diǎn)的凸組合。
我們稱集合 C C C中所有點(diǎn)的凸組合的集合為其凸包,記作 conv C \text{conv} \,C convC。
多個(gè)凸集的交集也是凸集,這意味著如果每個(gè)不等式或等式約束條件定義的集合都是凸集,那么這些條件聯(lián)合起來定義的集合仍然是凸集。
基于凸集的概念可以定義凸函數(shù)。
凸函數(shù)
函數(shù) f : R n → R f : \Bbb R^n \rightarrow \Bbb R f:Rn→R是凸的,如果函數(shù)的定義域( dom f \text{dom}\, f domf)是凸集,且對(duì)于任意 x 1 , x 2 ∈ dom f x_1,x_2 \in \text{dom}\, f x1?,x2?∈domf和任意的 0 ≤ θ ≤ 1 0 \leq \theta \leq 1 0≤θ≤1,有
f ( θ x 1 + ( 1 ? θ ) x 2 ) ≤ θ f ( x 1 ) + ( 1 ? θ ) f ( x 2 ) (4) f(\theta x_1 + (1-\theta)x_2) \leq \theta f(x_1) + (1-\theta) f(x_2) \tag{4} f(θx1?+(1?θ)x2?)≤θf(x1?)+(1?θ)f(x2?)(4)
如圖2(取 θ = 1 2 \theta=\frac{1}{2} θ=21?),從幾何意義上看,式 ( 4 ) (4) (4)的不等式成立意味著點(diǎn) ( x 1 , f ( x 1 ) ) (x_1,f(x_1)) (x1?,f(x1?))和 ( x 2 , f ( x 2 ) ) (x_2,f(x_2)) (x2?,f(x2?))之間的線段,即從 x 1 x_1 x1?到 x 2 x_2 x2?的弦,在函數(shù) f f f的圖像上方。
反之,如果式 ( 4 ) (4) (4)中的函數(shù)為 ≥ \geq ≥,則稱為凹函數(shù)。如果 f f f是凸函數(shù),那么 ? f -f ?f就是凹函數(shù)。注意,還有很多函數(shù)是非凸也非凹的。
凸函數(shù)的一個(gè)很好的性質(zhì)是,它只有一個(gè)局部極小值點(diǎn),同時(shí)也是全局最小值點(diǎn)。
凸優(yōu)化問題
優(yōu)化問題
我們用
minimize f 0 ( x ) s.t. f i ( x ) ≤ 0 , i = 1 , … , m h i ( x ) = 0 , i = 1 , … , p (5) \begin{aligned} &\text{minimize}\quad &&f_0(x)\\ &\text{s.t.}\quad &&f_i(x) \leq 0,\quad i=1,\dots,m\\ &&&h_i(x) = 0,\quad i=1,\dots,p \end{aligned} \tag{5} ?minimizes.t.??f0?(x)fi?(x)≤0,i=1,…,mhi?(x)=0,i=1,…,p?(5)
描述在所有滿足 f i ( x ) ≤ 0 , i = 1 , ? , m f_i(x) \leq 0,\, i=1,\cdots,m fi?(x)≤0,i=1,?,m及 h i ( x ) = 0 , i = 1 , ? , p h_i(x)=0,\,i=1,\cdots,p hi?(x)=0,i=1,?,p的 x x x中尋找極小化 f 0 ( x ) f_0(x) f0?(x)的 x x x的問題,即優(yōu)化問題。
-
x ∈ R n x \in \Bbb R^n x∈Rn為優(yōu)化變量;
-
函數(shù) f 0 : R n → R f_0 : \Bbb R^n \rightarrow \Bbb R f0?:Rn→R為目標(biāo)函數(shù);
-
不等式 f i ( x ) ≤ 0 f_i(x) \leq 0 fi?(x)≤0稱為不等式約束,相應(yīng)的函數(shù) f i : R n → R f_i: \Bbb R^n \rightarrow \Bbb R fi?:Rn→R稱為不等式約束函數(shù);
-
方程組 h i ( x ) = 0 h_i(x) =0 hi?(x)=0稱為等式約束,相應(yīng)的函數(shù) h i : R n → R h_i: \Bbb R^n \rightarrow \Bbb R hi?:Rn→R稱為等式約束函數(shù)。
如果沒有約束,即 m = p = 0 m=p=0 m=p=0,我們稱問題 ( 5 ) (5) (5)為無約束問題。
對(duì)目標(biāo)和所有約束函數(shù)有定義的點(diǎn)的集合
D = ? i = 0 m dom f i ∩ ? i = 1 p dom h i \mathcal D = \bigcap_{i=0}^m \text{dom}\, f_i \cap \bigcap_{i=1}^p \text{dom}\, h_i D=i=0?m?domfi?∩i=1?p?domhi?
稱為優(yōu)化問題 ( 5 ) (5) (5)的定義域。當(dāng)點(diǎn) x ∈ D x \in \cal D x∈D滿足約束 f i ( x ) ≤ 0 , i = 1 , ? , m f_i(x) \leq 0,\, i=1,\cdots,m fi?(x)≤0,i=1,?,m和 h i ( x ) = 0 , i = 1 , ? , p h_i(x)=0,\, i=1,\cdots, p hi?(x)=0,i=1,?,p時(shí), x x x是可行的。當(dāng)問題 ( 5 ) (5) (5)至少有一個(gè)可行點(diǎn)時(shí),我們稱為可行的,否則稱為不可行。所有可行點(diǎn)的集合稱為可行集或約束集。
如果 x ? x^* x?是可行的并且 f 0 ( x ? ) = p ? f_0(x^*)=p^* f0?(x?)=p?最優(yōu)值,我們稱 x ? x^* x?為最優(yōu)點(diǎn)。如果問題存在最優(yōu)解,我們稱最優(yōu)質(zhì)是課的或可達(dá)的,稱問題可解。
如果 x x x可行且 f i ( x ) = 0 f_i(x)=0 fi?(x)=0,我們稱約束 f i ( x ) ≤ 0 f_i(x)\leq 0 fi?(x)≤0的第 i i i個(gè)不等式在 x x x處起作用。如果 f i ( x ) < 0 f_i(x) < 0 fi?(x)<0,則約束 f i ( x ) ≤ 0 f_i(x) \leq 0 fi?(x)≤0不起作用。我們稱約束是冗余的,如果去掉它不改變可行集。
凸優(yōu)化
凸優(yōu)化問題是形如
minimize f 0 ( x ) s.t. f i ( x ) ≤ 0 , i = 1 , … , m a i T x = b i , i = 1 , ? , p (6) \begin{aligned} &\text{minimize}\quad &&f_0(x)\\ &\text{s.t.}\quad &&f_i(x) \leq 0,\quad i=1,\dots,m\\ &&&a_i^Tx = b_i,\quad\, i=1,\cdots,p \end{aligned} \tag{6} ?minimizes.t.??f0?(x)fi?(x)≤0,i=1,…,maiT?x=bi?,i=1,?,p?(6)
的問題,其中 f 0 , ? , f m f_0,\cdots,f_m f0?,?,fm?為凸函數(shù),對(duì)比優(yōu)化問題 ( 5 ) (5) (5),凸優(yōu)化問題有三個(gè)附加的要求:
- 目標(biāo)函數(shù)必須是凸的;
- 不等式約束函數(shù)必須是凸的;
- 等式約束函數(shù) h i ( x ) = a i T ? b i h_i(x) = a^T_i - b_i hi?(x)=aiT??bi?必須是仿射的;
立即可以看到一個(gè)重要的性質(zhì):凸優(yōu)化問題的可行集是凸的。
帶約束的優(yōu)化問題
拉格朗日乘子法
拉格朗日乘子法(Lagrange Multiplier Method)用于求解帶等式約束條件的函數(shù)極值(優(yōu)化問題)。假設(shè)有如下極值問題
minimize f ( x ) s.t. h i ( x ) = 0 , i = 1 , … , p (7) \begin{aligned} &\text{minimize}\quad &&f(x)\\ &\text{s.t.}\quad &&h_i(x) = 0,\quad i=1,\dots,p\\ \end{aligned} \tag{7} ?minimizes.t.??f(x)hi?(x)=0,i=1,…,p?(7)
拉格朗日乘子法構(gòu)造如下拉格朗日乘子函數(shù)
L ( x , λ ) = f ( x ) + ∑ i = 1 p λ i h i ( x ) (8) L(x,\lambda) = f(x) + \sum_{i=1}^p \lambda_i h_i(x) \tag{8} L(x,λ)=f(x)+i=1∑p?λi?hi?(x)(8)
其中 λ \lambda λ為新引入的自變量,稱為拉格朗日乘子((Lagrange Multiplier)。構(gòu)造了該函數(shù)之后,去掉了對(duì)優(yōu)化變量的等式約束。對(duì)拉格朗日乘子函數(shù)的所有自變量求偏導(dǎo),并令其為 0 0 0。包括對(duì) x x x求導(dǎo)、對(duì) λ \lambda λ求導(dǎo)。得到下面的方程組:
? x f ( x ) + ∑ i = 1 p λ i ? x h i ( x ) = 0 h i ( x ) = 0 (9) \begin{aligned} \nabla_x f(x) + \sum_{i=1}^p \lambda_i \nabla_x h_i(x) &= 0 \\ h_i(x) &= 0 \end{aligned} \tag{9} ?x?f(x)+i=1∑p?λi??x?hi?(x)hi?(x)?=0=0?(9)
求解該方程組即可得到函數(shù)的候選極值點(diǎn)。
拉格朗日對(duì)偶
對(duì)偶是求解最優(yōu)化問題的一種手段,它將一個(gè)最優(yōu)化問題轉(zhuǎn)換為另一個(gè)更容易求解的問題,這兩個(gè)問題是等價(jià)的。
對(duì)于如下帶等式約束和不等式約束的優(yōu)化問題:
minimize f ( x ) s.t. g i ( x ) ≤ 0 , i = 1 , … , m h i ( x ) = 0 , i = 1 , … , p (10) \begin{aligned} &\text{minimize}\quad &&f(x)\\ &\text{s.t.}\quad &&g_i(x) \leq 0,\quad i=1,\dots,m\\ &&&h_i(x) = 0,\quad i=1,\dots,p \end{aligned} \tag{10} ?minimizes.t.??f(x)gi?(x)≤0,i=1,…,mhi?(x)=0,i=1,…,p?(10)
仿照拉格朗日乘子法構(gòu)造廣義拉格朗日乘子函數(shù)
L ( x , λ , μ ) = f ( x ) + ∑ i = 1 m λ i g i ( x ) + ∑ i = 1 p μ i h i ( x ) (11) L(x,\lambda,\mu ) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{i=1}^p \mu_i h_i(x) \tag{11} L(x,λ,μ)=f(x)+i=1∑m?λi?gi?(x)+i=1∑p?μi?hi?(x)(11)
稱 λ \lambda λ和 μ \mu μ為拉格朗日乘子,特別要求 λ i ≥ 0 \lambda_i \geq 0 λi?≥0。接下來將上面的問題轉(zhuǎn)化為所謂的原問題,其最優(yōu)化解為 p ? p^* p?。
p ? = min ? x max ? λ , μ , λ i ≥ 0 L ( x , λ , μ ) = min ? x θ P ( x ) (12) p^* = \min_x \, \max_{\lambda,\mu,\lambda_i \geq 0} L(x,\lambda, \mu) = \min_x \theta_P(x) \tag{12} p?=xmin?λ,μ,λi?≥0max?L(x,λ,μ)=xmin?θP?(x)(12)
上式第一個(gè)等號(hào)右邊的含義是先固定變量 x x x,將其看成常數(shù),讓拉格朗日函數(shù)對(duì)乘子變量 λ \lambda λ和 μ \mu μ求極大值;消掉(確定了)變量 λ \lambda λ和 μ \mu μ之后,再對(duì)變量 x x x求極小值。
為了簡化表述,定義如下極大值問題
θ P ( x ) = max ? λ , μ , λ i ≥ 0 L ( x , λ , μ ) (13) \theta_P(x) =\max_{\lambda,\mu,\lambda_i \geq 0} L(x,\lambda, \mu) \tag{13} θP?(x)=λ,μ,λi?≥0max?L(x,λ,μ)(13)
這是一個(gè)對(duì)變量 λ \lambda λ和 μ \mu μ求函數(shù) L L L的極大值的問題,將 x x x看成常數(shù)。這樣,原始問題被轉(zhuǎn)化為先對(duì)變量 λ \lambda λ和 μ \mu μ求極大值,再對(duì) x x x求極小值。
這個(gè)原問題和我們要求解的原始問題有同樣的解,下面給出證明。對(duì)于任意的 x x x,分兩種情況討論。
(1)如果 x x x是不可行解,對(duì)于某些 i i i有 g i ( x ) > 0 g_i(x) > 0 gi?(x)>0,即 x x x違反了不等式約束條件,我們讓拉格朗日乘子 λ i = + ∞ \lambda_i = +\infty λi?=+∞,最終使得目標(biāo)函數(shù) θ P ( x ) = + ∞ \theta_P(x) = +\infty θP?(x)=+∞。如果對(duì)于某些 i i i有 h i ( x ) ≠ 0 h_i(x) \neq 0 hi?(x)=0,即違反了等式約束,我們可以讓 μ i = + ∞ ? sgn ( h i ( x ) ) \mu_i = +\infty \cdot \text{sgn}(h_i(x)) μi?=+∞?sgn(hi?(x)),從而使得 θ P ( x ) = + ∞ \theta_P(x) = +\infty θP?(x)=+∞。
即對(duì)于任意不滿足等式或不等式約束條件的 x x x, θ P ( x ) \theta_P(x) θP?(x)的值是 + ∞ +\infty +∞。
(2)如果 x x x是可行解,這時(shí) θ P ( x ) = f ( x ) \theta_P(x) = f(x) θP?(x)=f(x)。因?yàn)橛?span id="vxwlu0yf4" class="katex--inline"> h i ( x ) = 0 h_i(x) =0 hi?(x)=0且 g i ( x ) ≤ 0 g_i(x) \leq 0 gi?(x)≤0,而我們要求 λ i ≥ 0 \lambda_i \geq 0 λi?≥0,因?yàn)?span id="vxwlu0yf4" class="katex--inline"> θ P ( x ) \theta_P(x) θP?(x)的極大值就是 f ( x ) f(x) f(x)。為了達(dá)到這個(gè)極大值,我們讓 λ i \lambda_i λi?和 μ i \mu_i μi?為 0 0 0,函數(shù) f ( x ) + ∑ i = 1 p μ i h i ( x ) f(x) + \sum_{i=1}^p \mu_i h_i(x) f(x)+∑i=1p?μi?hi?(x)的極大值就是 f ( x ) f(x) f(x)。
綜上兩種情況,問題 θ P ( x ) \theta_P(x) θP?(x)和我們要優(yōu)化的原始問題的關(guān)系可以表述為
θ P ( x ) = { f ( x ) g i ( x ) ≤ 0 , h i ( x ) = 0 + ∞ else \theta_P(x) = \begin{cases} f(x) & g_i(x) \leq 0, h_i(x) = 0\\ +\infty & \text{else} \end{cases} θP?(x)={f(x)+∞?gi?(x)≤0,hi?(x)=0else?
即 θ P ( x ) \theta_P(x) θP?(x)是原始優(yōu)化問題的無約束版本。對(duì)于任何不可行的 x x x,有 θ P ( x ) = + ∞ \theta_P(x) = +\infty θP?(x)=+∞,從而使得原始問題的目標(biāo)函數(shù)趨向于無窮大,排除掉 x x x的不可行區(qū)域,只剩下可行的 x x x組成的區(qū)域。
這樣我們要求解的帶約束優(yōu)化問題被轉(zhuǎn)化成了對(duì) x x x不帶約束的優(yōu)化問題,并且二者等價(jià)。
下面定義對(duì)偶問題與其最優(yōu)解 d ? d^* d?。
d ? = max ? λ , μ , λ i ≥ 0 min ? x L ( x , λ , μ ) = max ? λ , μ , λ i ≥ 0 θ D ( λ , μ ) (14) d^* = \max_{\lambda,\mu,\lambda_i \geq 0}\, \min_x L(x,\lambda, \mu) = \max_{\lambda,\mu,\lambda_i \geq 0} \theta_D(\lambda, \mu) \tag{14} d?=λ,μ,λi?≥0max?xmin?L(x,λ,μ)=λ,μ,λi?≥0max?θD?(λ,μ)(14)
這里先固定拉格朗日乘子 λ \lambda λ和 μ \mu μ,調(diào)整 x x x讓拉格朗日函數(shù)對(duì) x x x求極小值;然后調(diào)整 λ \lambda λ和 μ \mu μ對(duì)函數(shù)求極大值。
原問題和對(duì)偶問題只是改變了求極大值和極小值的順序,每次操控的變量是一樣的。如果原問題和對(duì)偶問題都存在最優(yōu)解,則對(duì)偶問題的最優(yōu)值不大于原問題的最優(yōu)值,即
d ? = max ? λ , μ , λ i ≥ 0 min ? x L ( x , λ , μ ) ≤ min ? x max ? λ , μ , λ i ≥ 0 L ( x , λ , μ ) = p ? (15) d^* =\max_{\lambda,\mu,\lambda_i \geq 0}\, \min_x L(x,\lambda, \mu) \leq \min_x \, \max_{\lambda,\mu,\lambda_i \geq 0} L(x,\lambda, \mu) = p^* \tag{15} d?=λ,μ,λi?≥0max?xmin?L(x,λ,μ)≤xmin?λ,μ,λi?≥0max?L(x,λ,μ)=p?(15)
證明,假設(shè)原問題的最優(yōu)解為 x 1 , λ 1 , μ 1 x_1,\lambda_1,\mu_1 x1?,λ1?,μ1?,對(duì)偶問題的最優(yōu)解為 x 2 , λ 2 , μ 2 x_2,\lambda_2,\mu_2 x2?,λ2?,μ2?,由于原問題是先對(duì) ( λ , μ ) (\lambda,\mu) (λ,μ)取極大值,有
L ( x 1 , λ 1 , μ 1 ) ≥ L ( x 1 , λ 2 , μ 2 ) L(x_1,\lambda_1,\mu_1) \geq L(x_1,\lambda_2,\mu_2) L(x1?,λ1?,μ1?)≥L(x1?,λ2?,μ2?)
這里固定 x 1 x_1 x1?。
而對(duì)偶問題先對(duì) x x x取極小值,有
L ( x 2 , λ 2 , μ 2 ) ≤ L ( x 1 , λ 2 , μ 2 ) L(x_2,\lambda_2,\mu_2) \leq L(x_1,\lambda_2,\mu_2) L(x2?,λ2?,μ2?)≤L(x1?,λ2?,μ2?)
這類變化的只是 x x x。上面兩個(gè)式子中右邊都是一樣的,從而有
L ( x 1 , λ 1 , μ 1 ) ≥ L ( x 2 , λ 2 , μ 2 ) L(x_1,\lambda_1,\mu_1) \geq L(x_2,\lambda_2,\mu_2) L(x1?,λ1?,μ1?)≥L(x2?,λ2?,μ2?)
這一結(jié)論稱為弱對(duì)偶定理(Weak Duality)。
原問題最優(yōu)值和對(duì)偶問題最優(yōu)值的差 p ? ? d ? p^*-d^* p??d?稱為對(duì)偶間隙。如果原問題和對(duì)偶問題有相同的最優(yōu)解,那么我們就可以把求解原問題轉(zhuǎn)化為求解對(duì)偶問題,此時(shí)對(duì)偶間隙為0,這種情況稱為強(qiáng)對(duì)偶。
但要滿足怎樣的條件才能使得 d ? = p ? d^*=p^* d?=p?呢,就是下面闡述的KKT條件。
KKT條件
KKT(Karush-Kuhn-Tucker)條件用于求解帶有等式和不等式約束的優(yōu)化問題,是拉格朗日乘子法的推廣。
對(duì)于如下帶等式約束和不等式約束的優(yōu)化問題:
minimize f ( x ) s.t. g i ( x ) ≤ 0 , i = 1 , … , m h i ( x ) = 0 , i = 1 , … , n (16) \begin{aligned} &\text{minimize}\quad &&f(x)\\ &\text{s.t.}\quad &&g_i(x) \leq 0,\quad i=1,\dots,m\\ &&&h_i(x) = 0,\quad i=1,\dots,n \end{aligned} \tag{16} ?minimizes.t.??f(x)gi?(x)≤0,i=1,…,mhi?(x)=0,i=1,…,n?(16)
與拉格朗日對(duì)偶的做法類似,為其構(gòu)造拉格朗日乘子函數(shù)消掉等式和不等式約束:
L ( x , λ , μ ) = f ( x ) + ∑ i = 1 m μ i g i ( x ) + ∑ i = 1 n λ i h i ( x ) (17) L(x,\lambda,\mu ) = f(x) + \sum_{i=1}^m \mu_i g_i(x) + \sum_{i=1}^n \lambda_i h_i(x) \tag{17} L(x,λ,μ)=f(x)+i=1∑m?μi?gi?(x)+i=1∑n?λi?hi?(x)(17)
λ \lambda λ和 μ \mu μ稱為KKT乘子。
KKT條件包括:
- ? x L ( x , λ , μ ) = 0 \nabla_x L(x,\lambda,\mu) = \pmb 0 ?x?L(x,λ,μ)=0
- g i ( x ) ≤ 0 g_i (x) \leq 0 gi?(x)≤0
- h i ( x ) = 0 h_i(x) =0 hi?(x)=0
- μ i ≥ 0 \mu_i \geq 0 μi?≥0
- μ i g i ( x ) = 0 \mu_ig_i(x) =0 μi?gi?(x)=0
其中第三個(gè)條件 h i ( x ) = 0 h_i(x) =0 hi?(x)=0等式約束和第二個(gè)條件 g i ( x ) ≤ 0 g_i (x) \leq 0 gi?(x)≤0不等式約束是本身應(yīng)該滿足的約束;第一個(gè)條件 ? x L ( x , λ , μ ) = 0 \nabla_x L(x,\lambda,\mu) = \pmb 0 ?x?L(x,λ,μ)=0和拉格朗日乘子法相同。
第四個(gè)條件稱為對(duì)偶可行性條件;
第五個(gè)條件稱為互補(bǔ)松弛條件,而且當(dāng)一個(gè)變量取非零值時(shí),另一個(gè)變量必須取零。
KKT條件是取得極值的必要條件,但如果一個(gè)優(yōu)化問題是凸優(yōu)化問題,則KKT條件是取得極小值的充分條件。
Slater條件
Slater條件:一個(gè)凸優(yōu)化問題如果存在一個(gè)候選 x x x使得所有不等式約束都是嚴(yán)格滿足的,即對(duì)于所有的 i i i都有 g i ( x ) < 0 g_i(x) < 0 gi?(x)<0,也就是說,在不等式約束區(qū)域內(nèi)部至少有一個(gè)可行點(diǎn),則存在 ( x ? , λ ? , μ ? ) (x^*,\lambda^*,\mu^*) (x?,λ?,μ?)使得它們同時(shí)為原問題和對(duì)偶問題的最優(yōu)解,即
p ? = d ? = L ( x ? , λ ? , μ ? ) p^*=d^*= L(x^*,\lambda^*,\mu^*) p?=d?=L(x?,λ?,μ?)
Slater條件是強(qiáng)對(duì)偶成立的充分條件而不是必要條件。
小結(jié)
Slater條件和KKT條件都是用來判斷最優(yōu)化問題是否有解的條件。它們之間的關(guān)系可以總結(jié)如下:
- Slater條件是一種充分條件,當(dāng)最優(yōu)化問題滿足Slater條件時(shí),會(huì)保證強(qiáng)對(duì)偶性成立,并且原始問題和對(duì)偶問題都存在最優(yōu)解。具體來說,Slater條件要求不等式約束條件 g i ( x ) ≤ 0 g_i(x) \leq 0 gi?(x)≤0 和等式約束條件 h i ( x ) = 0 h_i(x)=0 hi?(x)=0 滿足嚴(yán)格可行性,即存在一個(gè) x x x使得所有的不等式約束條件 g i ( x ) < 0 g_i(x) < 0 gi?(x)<0 均嚴(yán)格成立。
- KKT條件是一組必要條件,可以用于判斷某個(gè)點(diǎn)是否為最優(yōu)解。對(duì)于有約束的最優(yōu)化問題,其KKT條件包括互補(bǔ)松弛條件、不等式約束條件的拉格朗日乘子大于等于零以及梯度為零。若最優(yōu)化問題的解滿足KKT條件,則該解是最優(yōu)解的必要條件。
需要注意的是,Slater條件只是強(qiáng)對(duì)偶性的一種充分條件,而不是必要條件。也就是說,如果一個(gè)問題不滿足Slater條件,仍然有可能存在最優(yōu)解以及強(qiáng)對(duì)偶性。而KKT條件則是最優(yōu)解的必要條件,但不一定是充分條件,也就是說,一個(gè)滿足KKT條件的點(diǎn)并不一定是最優(yōu)解。
因此,在實(shí)際求解問題時(shí),我們通常需要結(jié)合Slater條件和KKT條件來進(jìn)行判斷,以保證得到的解是可行的、正確的,并且滿足約束條件。
最優(yōu)化方法
梯度下降法
梯度下降法(gradient descent)或最速下降法是求解無約束最優(yōu)化問題的一種最常用的方法,它的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單。梯度下降法是一種迭代算法,每一步需要求解目標(biāo)函數(shù)的梯度向量。
假設(shè) f ( x ) f(x) f(x)是 R n \Bbb R^n Rn是具有一階連續(xù)偏導(dǎo)數(shù)的函數(shù)。要求解的無約束最優(yōu)化問題是
min ? x ∈ R n f ( x ) (18) \min_{x \in \Bbb R^n} f(x) \tag{18} x∈Rnmin?f(x)(18)
x ? x^* x?表示目標(biāo)函數(shù) f ( x ) f(x) f(x)的極小值點(diǎn)。
梯度下降法通過選擇適當(dāng)?shù)某踔?span id="vxwlu0yf4" class="katex--inline"> x ( 0 ) x^{(0)} x(0),不斷迭代,更新 x x x的值,進(jìn)行目標(biāo)函數(shù)的極小化,直到收斂。由于負(fù)梯度方向是使函數(shù)值下降最快的方向,在迭代的每一步,以負(fù)梯度方向更新 x x x的值,從而達(dá)到減少函數(shù)值的目的。
由于 f ( x ) f(x) f(x)具有一階連續(xù)偏導(dǎo)數(shù),若第 k k k次迭代值為 x ( k ) x^{(k)} x(k),則可將 f ( x ) f(x) f(x)在 x ( k ) x^{(k)} x(k)附近進(jìn)行一階泰勒展開:
f ( x ) = f ( x ( k ) ) + g k T ( x ? x ( k ) ) (19) f(x) = f(x^{(k)}) + g_k^T(x-x^{(k)}) \tag{19} f(x)=f(x(k))+gkT?(x?x(k))(19)
在人工智能高等數(shù)學(xué)中我們知道在 x = a x=a x=a點(diǎn)的泰勒展開式為:
g ( x ) = f ( a ) + f ′ ( a ) 1 ! ( x ? a ) + f ′ ′ ( a ) 2 ! ( x ? a ) 2 + f 3 ( a ) 3 ! ( x ? a ) 3 + . . . + f n ( a ) n ! ( x ? a ) n (20) g(x) = f(a) + \frac{f^\prime(a)}{1!}(x-a) + \frac{f^{\prime\prime}(a)}{2!}(x-a)^2 + \frac{f^3(a)}{3!}(x-a)^3 + ... + \frac{f^n(a)}{n!}(x-a)^n \tag{20} g(x)=f(a)+1!f′(a)?(x?a)+2!f′′(a)?(x?a)2+3!f3(a)?(x?a)3+...+n!fn(a)?(x?a)n(20)
這里去掉了高階項(xiàng)就得到了公式 ( 19 ) (19) (19), g k = g ( x ( k ) ) = ? f ( x ( k ) ) g_k=g(x^{(k)})=\nabla f(x^{(k)}) gk?=g(x(k))=?f(x(k))為 f ( x ) f(x) f(x)在 x ( k ) x^{(k)} x(k)的梯度,即一階偏導(dǎo)。
求出第 k + 1 k+1 k+1次迭代值 x ( k + 1 ) x^{(k+1)} x(k+1):
x ( k + 1 ) ← x ( k ) + λ k p k (21) x^{(k+1)} \leftarrow x^{(k)} + \lambda_k p_k \tag{21} x(k+1)←x(k)+λk?pk?(21)
其中, p k p_k pk?是搜索方向,取負(fù)梯度方向 p k = ? ? f ( x ( k ) ) p_k= -\nabla f(x^{(k)}) pk?=??f(x(k)), λ k \lambda_k λk?是步長,這里由一維搜索確定,即找到 λ k \lambda_k λk?使得
f ( x ( k ) + λ k p k ) = min ? λ ≥ 0 f ( x ( k ) + λ p k ) (22) f(x^{(k)} + \lambda_k p_k) = \min_{\lambda \geq 0} f(x^{(k)} + \lambda p_k) \tag{22} f(x(k)+λk?pk?)=λ≥0min?f(x(k)+λpk?)(22)
一維搜索是一種優(yōu)化算法,也被稱為線性搜索。在機(jī)器學(xué)習(xí)中,一維搜索通常是用來確定如何更新模型參數(shù)的步長或?qū)W習(xí)率,以最小化訓(xùn)練數(shù)據(jù)上的損失函數(shù)。
一維搜索可以簡單理解為在某個(gè)方向上尋找一個(gè)合適的步長,使得當(dāng)前位置向這個(gè)方向前進(jìn)這個(gè)步長之后,能夠使目標(biāo)函數(shù)(或者損失函數(shù))達(dá)到最小值。其實(shí)現(xiàn)過程通常是沿著負(fù)梯度方向進(jìn)行搜索,并通過逐步縮小搜索范圍和增加精度等方法,找到一個(gè)近似的最優(yōu)解。
因?yàn)橐痪S搜索只在一個(gè)方向上進(jìn)行搜索,在復(fù)雜的高維問題中很少直接使用,通常會(huì)作為其他更復(fù)雜優(yōu)化算法的輔助手段。
梯度下降法算法如下:
輸入: 目標(biāo)函數(shù) f ( x ) f(x) f(x),梯度函數(shù) g ( x ) = ? f ( x ) g(x) = \nabla f(x) g(x)=?f(x),計(jì)算精度 ? \epsilon ?;
輸出: f ( x ) f(x) f(x)的極小點(diǎn) x ? x^* x?。
(1) 取初值 x ( 0 ) ∈ R n x^{(0)} \in \Bbb R^n x(0)∈Rn,令 k = 0 k=0 k=0。
(2) 計(jì)算 f ( x ( k ) ) f(x^{(k)}) f(x(k))。
(3) 計(jì)算梯度 g k = g ( x ( k ) ) g_k=g(x^{(k)}) gk?=g(x(k)),當(dāng) ∣ ∣ g k ∣ ∣ < ? ||g_k|| < \epsilon ∣∣gk?∣∣<?時(shí),停止迭代,令 x ? = x ( k ) x^*=x^{(k)} x?=x(k);否則,令 p k = ? g ( x ( k ) ) p_k=-g(x^{(k)}) pk?=?g(x(k)),求 λ k \lambda_k λk?使
f ( x ( k ) + λ k p k ) = min ? λ ≥ 0 f ( x ( k ) + λ p k ) f(x^{(k)} + \lambda_k p_k) = \min_{\lambda \geq 0} f(x^{(k)} + \lambda p_k) f(x(k)+λk?pk?)=λ≥0min?f(x(k)+λpk?)
(4) 置 x ( k + 1 ) = x ( k ) + λ k p k x^{(k+1)}=x^{(k)} + \lambda_kp_k x(k+1)=x(k)+λk?pk?,計(jì)算 f ( x ( k + 1 ) ) f(x^{(k+1)}) f(x(k+1))
當(dāng) ∣ ∣ f ( x ( k + 1 ) ) ? f ( x ( k ) ) ∣ ∣ < ? ||f(x^{(k+1)}) - f(x^{(k)})|| < \epsilon ∣∣f(x(k+1))?f(x(k))∣∣<?或 ∣ ∣ x ( k + 1 ) ? x ( k ) ∣ ∣ < ? ||x^{(k+1)} - x^{(k)}|| < \epsilon ∣∣x(k+1)?x(k)∣∣<?時(shí),停止迭代,令 x ? = x ( k + 1 ) x^*=x^{(k+1)} x?=x(k+1)。
(5) 否則,置 k = k + 1 k=k+1 k=k+1,轉(zhuǎn)(3)。
當(dāng)目標(biāo)函數(shù)是凸函數(shù)時(shí),梯度下降法的解釋全局最優(yōu)解。但一般情況下,其解不保證是全局最優(yōu)解。且收斂速度也未必是很快的。
如果是無約束優(yōu)化問題,想要收斂速度快的話,可以考慮牛頓法或擬牛頓法。
牛頓法和擬牛頓法都是求解無約束最優(yōu)化問題的常用方法,具有收斂速度快的優(yōu)點(diǎn)。牛頓法是迭代算法,每一步需要求解目標(biāo)函數(shù)的海森矩陣的逆矩陣,計(jì)算比較復(fù)雜,而且有時(shí)候海森矩陣不一定存在逆陣。擬牛頓法通過正定矩陣近似海森矩陣的逆矩陣或海森矩陣,簡化了這一計(jì)算過程。