1. 原问题的拉格朗日等价形式
对一个约束优化问题:
min x f ( x ) s.t. g i ( x ) ≤ 0 , i = 1 , ⋯ , m h i ( x ) = 0 , i = 1 , ⋯ , p \min\limits_{\mathbf{x}} f(\mathbf{x})\\ \text{s.t. } g_i(\mathbf{x})\leq0,i=1,\cdots,m\\ h_i(\mathbf{x})=0,i=1,\cdots,p xminf(x)s.t. gi(x)≤0,i=1,⋯,mhi(x)=0,i=1,⋯,p
-
不等式约束: g i : R n ↦ R , i = 1 , ⋯ , m g_i:\R^n\mapsto \R,i=1,\cdots,m gi:Rn↦R,i=1,⋯,m
-
等式约束: h i : R n ↦ R , i = 1 , ⋯ , p h_i:\R^n\mapsto\R,i=1,\cdots,p hi:Rn↦R,i=1,⋯,p
-
可行域: Ω = { x ∈ R n : g i ( x ) ≤ 0 , h j ( x ) = 0 , i = 1 , ⋯ , m , j = 1 , ⋯ , p } \Omega=\{\mathbf{x}\in\R^n:g_i(\mathbf{x})\leq0,h_j(\mathbf{x})=0,i=1,\cdots,m,j=1,\cdots,p\} Ω={x∈Rn:gi(x)≤0,hj(x)=0,i=1,⋯,m,j=1,⋯,p}
-
拉格朗日函数: L ( x , λ , μ ) = f ( x ) + ∑ i = 1 m λ i g i ( x ) + ∑ j = 1 p μ j h j ( x ) , λ i ≥ 0 L(\mathbf{x},\lambda,\mu)=f(\mathbf{x})+\sum_{i=1}^m\lambda_ig_i(\mathbf{x})+\sum_{j=1}^p\mu_jh_j(\mathbf{x}),\lambda_i\geq0 L(x,λ,μ)=f(x)+∑i=1mλigi(x)+∑j=1pμjhj(x),λi≥0
可以看到:
- case 1:当 x ∈ Ω \mathbf{x}\in\Omega x∈Ω 时, L ( x , λ , μ ) = f ( x ) + ∑ λ i g i ⏟ ≤ 0 + ∑ μ j h j ⏟ = 0 ≤ f ( x ) L(\mathbf{x},\lambda,\mu)=f(\mathbf{x})+\underbrace{\sum\lambda_ig_i}_{\leq0}+\underbrace{\sum\mu_jh_j}_{=0}\leq f(\mathbf{x}) L(x,λ,μ)=f(x)+≤0 ∑λigi+=0 ∑μjhj≤f(x),因此 max λ ≥ 0 , μ L ( x , λ , μ ) = f ( x ) \max\limits_{\lambda\geq0,\mu}L(\mathbf{x},\lambda,\mu)=f(\mathbf{x}) λ≥0,μmaxL(x,λ,μ)=f(x)
- case 2:当 x ∉ Ω \mathbf{x}\notin\Omega x∈/Ω 时, L ( x , λ , μ ) = f ( x ) + ∑ λ i g i ⏟ + ∞ + ∑ μ j h j ⏟ + ∞ = ∞ L(\mathbf{x},\lambda,\mu)=f(\mathbf{x})+\underbrace{\sum\lambda_ig_i}_{+\infin}+\underbrace{\sum\mu_jh_j}_{+\infin}=\infin L(x,λ,μ)=f(x)++∞ ∑λigi++∞ ∑μjhj=∞
- 综合上述情况:
f ( x ) = { max λ ≥ 0 , μ L ( x , λ , μ ) , x ∈ Ω + ∞ , otherwise f(\mathbf{x}) = \begin{cases} \max\limits_{\lambda\geq0,\mu}L(\mathbf{x},\lambda,\mu),\quad \mathbf{x}\in \Omega \\[2ex] +\infin, \quad \text{otherwise}\end{cases} f(x)=⎩ ⎨ ⎧λ≥0,μmaxL(x,λ,μ),x∈Ω+∞,otherwise
因此原问题(Primal): min x ∈ Ω f ( x ) ⇔ min x ∈ R n max λ ≥ 0 , μ L ( x , λ , μ ) \min\limits_{\mathbf{x}\in\Omega}f(\mathbf{x})\Leftrightarrow\min\limits_{\mathbf{x\in\R^n}}\max\limits_{\lambda\geq0,\mu}L(\mathbf{x},\lambda,\mu) x∈Ωminf(x)⇔x∈Rnminλ≥0,μmaxL(x,λ,μ)
2. 对偶函数和对偶问题
【思考】:现在我们知道了原问题等价于求拉格朗日函数的最大值再求最小值,那么倘若交换 min \min min 和 max \max max 运算,即 max λ ≥ 0 , μ min x ∈ R n L ( x , λ , μ ) \max\limits_{\lambda\geq0,\mu}\min\limits_{\mathbf{x\in\R^n}}L(\mathbf{x},\lambda,\mu) λ≥0,μmaxx∈RnminL(x,λ,μ) 是否依旧和原问题等价呢?
于是我们定义:
- 对偶函数(Dual Function): q ( λ , μ ) : = min x L ( x , λ , μ ) q(\lambda,\mu):=\min\limits_{\mathbf{x}}L(\mathbf{x},\lambda,\mu) q(λ,μ):=xminL(x,λ,μ)
- 对偶问题(Dual Problem): max λ ≥ 0 , μ q ( λ , μ ) \max\limits_{\lambda\geq0,\mu}q(\lambda,\mu) λ≥0,μmaxq(λ,μ)
【思考】:我们对原问题和对偶问题是否等价很感兴趣。如果他们不等价,那么原问题和对偶问题有怎样的关系?在某些特殊情况下,原问题和对偶问题等价?
3. 弱对偶定理
【定理】:对任意 x ∈ Ω \mathbf{x}\in\Omega x∈Ω(原问题可行) 和任意 λ ≥ 0 , μ \lambda\geq0,\mu λ≥0,μ(对偶问题可行), q ( λ , μ ) ≤ f ( x ) q(\lambda,\mu)\leq f(\mathbf{x}) q(λ,μ)≤f(x) 恒成立。
【证明】:设 x ∗ \mathbf{x}^* x∗ 是原问题的最优解,则对任意 λ ≥ 0 , μ , x ∈ Ω \lambda\geq0,\mu, \mathbf{x}\in\Omega λ≥0,μ,x∈Ω 有如下不等式:
q ( λ , μ ) = min x L ( x , λ , μ ) ≤ L ( x ∗ , λ , μ ) ≤ max λ ≥ 0 , μ L ( x ∗ , λ , μ ) = f ( x ∗ ) ≤ f ( x ) q(\lambda,\mu)=\min\limits_{\mathbf{x}}L(\mathbf{x},\lambda,\mu)\leq L(\mathbf{x}^*,\lambda,\mu)\\\leq\max\limits_{\lambda\geq0,\mu}L(\mathbf{x}^*,\lambda,\mu)=f(\mathbf{x}^*)\leq f(\mathbf{x}) q(λ,μ)=xminL(x,λ,μ)≤L(x∗,λ,μ)≤λ≥0,μmaxL(x∗,λ,μ)=f(x∗)≤f(x)
因为在对偶函数中, x ∈ R n \mathbf{x}\in\R^n x∈Rn,而 x ∗ ∈ Ω , Ω ⊂ R n \mathbf{x}^*\in\Omega,\Omega\subset\R^n x∗∈Ω,Ω⊂Rn,所以 min X L ( x , λ , μ ) ≤ L ( x ∗ , λ , μ ) \min\limits_{\mathbf{X}}L(\mathbf{x},\lambda,\mu)\leq L(\mathbf{x}^*,\lambda,\mu) XminL(x,λ,μ)≤L(x∗,λ,μ)
【推论】:设 λ ∗ , μ ∗ = arg max λ ≥ 0 , μ q ( λ , μ ) \lambda^*,\mu^*=\arg\max\limits_{\lambda\geq0,\mu}q(\lambda,\mu) λ∗,μ∗=argλ≥0,μmaxq(λ,μ),并且 x ∗ = arg max x ∈ Ω f ( x ) \mathbf{x}^*=\arg\max\limits_{\mathbf{x}\in\Omega}f(\mathbf{x}) x∗=argx∈Ωmaxf(x),则由弱对偶定理,我们可以得到:
q ( λ ∗ , μ ∗ ) ≤ f ( x ∗ ) ⇔ max λ ≥ 0 , μ min x L ≤ min x ∈ Ω max λ ≥ 0 , μ L q(\lambda^*,\mu^*)\leq f(\mathbf{x}^*)\Leftrightarrow\max\limits_{\lambda\geq0,\mu}\min\limits_{\mathbf{x}}L\leq\min\limits_{\mathbf{x}\in\Omega}\max\limits_{\lambda\geq0,\mu}L q(λ∗,μ∗)≤f(x∗)⇔λ≥0,μmaxxminL≤x∈Ωminλ≥0,μmaxL
4. 强对偶定理
在约束优化问题中,强对偶定理是指原问题的最优值与其对偶问题的最优值相等的情况。然而,强对偶定理成立的条件依赖于问题的具体结构和性质。以下是针对不同类型的优化问题,强对偶定理成立的常见条件:
- 线性规划问题(LP):只要原问题有一个可行解并且最优解存在,那么强对偶定理总是成立。在这种情况下,强对偶性条件非常宽松。
- 凸(Convex)优化问题:对于凸优化问题,强对偶定理的成立通常需要满足Slater 条件。该条件是针对凸优化问题中强对偶性成立的充分条件,Slater 条件要求:
- 凸性:目标函数 f ( x ) f(\mathbf{x}) f(x) 和不等式约束函数 g i ( x ) g_i(\mathbf{x}) gi(x) 必须是凸函数,等式约束函数 h j ( x ) h_j(\mathbf{x}) hj(x) 必须是仿射函数(即线性函数)。
- 严格可行性: ∃ x 0 s.t. ∀ i g i ( x 0 ) < 0 , h ( x ) = 0 \exist\mathbf{x}_0\ \text{s.t.}\ \forall i\ g_i(\mathbf{x}_0)<0,h(\mathbf{x})=0 ∃x0 s.t. ∀i gi(x0)<0,h(x)=0
由弱对偶定理我们有: q ( λ ∗ , μ ∗ ) ≤ L ( x ∗ , λ ∗ , μ ∗ ) ≤ f ( x ∗ ) q(\lambda^*,\mu^*)\leq L(\mathbf{x}^*,\lambda^*,\mu^*)\leq f(\mathbf{x}^*) q(λ∗,μ∗)≤L(x∗,λ∗,μ∗)≤f(x∗),所以当 q ( λ ∗ , μ ∗ ) = f ( x ∗ ) q(\lambda^*,\mu^*)= f(\mathbf{x}^*) q(λ∗,μ∗)=f(x∗) 时,
L ( x ∗ , λ ∗ , μ ∗ ) = f ( x ∗ ) ⇒ ∑ i = 1 m λ i ∗ g i ( x ∗ ) + ∑ j = 1 p μ i ∗ h i ( x ∗ ) ⏟ = 0 = 0 ⇒ ∑ i = 1 m λ i ∗ g i ( x ∗ ) = 0 ⇒ λ i ∗ g i ( x ∗ ) = 0 ⇒ KKT: 互补松弛条件 \begin{aligned} &L(\mathbf{x}^*,\lambda^*,\mu^*)= f(\mathbf{x}^*)\\ &\Rightarrow\sum_{i=1}^m\lambda_i^*g_i(\mathbf{x}^*)+\underbrace{\sum_{j=1}^p\mu_i^*h_i(\mathbf{x}^*)}_{=0}=0\\ &\Rightarrow\sum_{i=1}^m\lambda_i^*g_i(\mathbf{x}^*)=0\\ &\Rightarrow\lambda_i^*g_i(\mathbf{x}^*)=0 \Rightarrow\textbf{KKT: 互补松弛条件} \end{aligned} L(x∗,λ∗,μ∗)=f(x∗)⇒i=1∑mλi∗gi(x∗)+=0 j=1∑pμi∗hi(x∗)=0⇒i=1∑mλi∗gi(x∗)=0⇒λi∗gi(x∗)=0⇒KKT: 互补松弛条件
5. KKT条件
KKT(Karush-Kuhn-Tucker)条件是用于解决非线性优化问题的一个重要工具,特别是带有约束的优化问题。它为寻找局部最优解提供了必要条件和充分条件(在某些情况下)。
- 在凸优化问题中,如果目标函数和不等式约束函数都是凸的,KKT条件不仅是局部最优解的必要条件,还是全局最优解的充分条件。这种情况下,满足KKT条件的解就是最优解。
- 在非凸优化问题中,KKT条件仍然是局部最优解的必要条件,但不再是充分条件。也就是说,即使一个解满足KKT条件,它也不一定是全局最优解。只有在特定问题结构下(如凸性条件),KKT条件才是充分条件。
【KKT条件】:设 x ∗ , λ ∗ , μ ∗ \mathbf{x}^*,\lambda^*,\mu^* x∗,λ∗,μ∗ 分别是原问题和对偶问题的最优解,则满足如下条件:
- 原问题可行: g i ( x ∗ ) ≤ 0 , ∀ i = 1 , ⋯ , m g_i(\mathbf{x}^*)\leq0,\forall i=1,\cdots,m gi(x∗)≤0,∀i=1,⋯,m, h j ( x ∗ ) = 0 , ∀ j = 1 , ⋯ , p h_j(\mathbf{x}^*)=0,\forall j=1,\cdots,p hj(x∗)=0,∀j=1,⋯,p
- 对偶问题可行: λ i ∗ ≥ 0 , ∀ i = 1 , ⋯ , m \lambda_i^*\geq0,\forall i=1,\cdots,m λi∗≥0,∀i=1,⋯,m
- 互补松弛条件: λ i ∗ g i ( x ) = 0 , ∀ i = 1 , ⋯ , m \lambda_i^*g_i(\mathbf{x})=0,\forall i=1,\cdots,m λi∗gi(x)=0,∀i=1,⋯,m
- 稳定点: ∇ x L ( x ∗ , λ ∗ , μ ∗ ) = 0 \nabla_{\mathbf{x}}L(\mathbf{x}^*,\lambda^*,\mu^*)=0 ∇xL(x∗,λ∗,μ∗)=0
下一节将介绍支持向量机SVM的数学原理