KKT条件
对于不等式约束优化问题
min f ( x ) s . t . g ( x ) ≤ 0 \min\quad f(x)\\ {\rm s.t.}\quad g(x)\leq 0 minf(x)s.t.g(x)≤0
拉格朗日函数为 L ( x , λ ) = f ( x ) + λ g ( x ) L(x,\lambda)=f(x)+\lambda g(x) L(x,λ)=f(x)+λg(x) 。
KKT条件包括
- 拉格朗日函数的定常方程式: ∇ x L = ∇ f + λ ∇ g = 0 \nabla_x L = \nabla f+\lambda\nabla g=0 ∇xL=∇f+λ∇g=0
- 原始可行性: g ( x ) ≤ 0 g(x)\leq 0 g(x)≤0
- 对偶可行性: λ ≥ 0 \lambda\geq 0 λ≥0
- 互补松弛性: λ g ( x ) = 0 \lambda g(x)=0 λg(x)=0
假设 x ∗ x^* x∗ 为满足约束条件的最佳解
- g ( x ∗ ) < 0 g(x^*)<0 g(x∗)<0：最佳解在可行域的内部，称为内部解，此时约束条件无效， x ∗ x^* x∗ 满足 ∇ f = 0 , λ = 0 \nabla f = 0, \lambda = 0 ∇f=0,λ=0
- g ( x ∗ ) = 0 g(x^*)=0 g(x∗)=0：最佳解在可行域的边界，称为边界解，此时约束条件有效，约束不等式变成约束等式 g ( x ) = 0 g(x)=0 g(x)=0 。并且，此时 ∇ f \nabla f ∇f 一定指向可行域内部，而 ∇ g \nabla g ∇g 一定指向可行域外部，而 ∇ f + λ ∇ g = 0 \nabla f+\lambda\nabla g=0 ∇f+λ∇g=0 ，得到 λ ≥ 0 \lambda\geq 0 λ≥0
因此，不论是内部解还是边界解， λ g ( x ) = 0 \lambda g(x)=0 λg(x)=0 恒成立，也就是互补松弛条件
原始问题和对偶问题
min x f ( x ) s . t . c i ( x ) ≤ 0 , i = 1 , 2 , ⋯ , K h j ( x ) = 0 , j = 1 , 2 , ⋯ , L \min_x\quad f(x)\\ {\rm s.t.} \begin{aligned} \quad &c_i(x)\leq 0, \quad i=1,2,\cdots, K\\ &h_j(x)=0, \quad j=1,2,\cdots, L \end{aligned} xminf(x)s.t.ci(x)≤0,i=1,2,⋯,Khj(x)=0,j=1,2,⋯,L
拉格朗日函数
L ( x , α , β ) = f ( x ) + ∑ i = 1 K α i c i ( x ) + ∑ j = 1 L β j h j ( x ) L(x,\alpha,\beta) = f(x)+\sum_{i=1}^K \alpha_ic_i(x)+\sum_{j=1}^L \beta_j h_j(x) L(x,α,β)=f(x)+i=1∑Kαici(x)+j=1∑Lβjhj(x)
原始问题
是先取关于拉格朗日乘子 α , β \alpha,\beta α,β 的 max \max max ，再取关于参数的 min \min min
因为 α ≥ 0 \alpha\geq 0 α≥0 ，因此在可行域外（ c i ( x ) ≤ 0 c_i(x)\leq 0 ci(x)≤0），如果取 α \alpha α 接近于正无穷，那么 L ( x , α , β ) L(x,\alpha,\beta) L(x,α,β) 也会趋近于正无穷，只有在可行域内，才存在max，也就是 f ( x ) f(x) f(x) 。
对偶问题
先取关于参数的 min \min min ，再取关于拉格朗日乘子 α , β \alpha,\beta α,β 的 max \max max
显然，对偶问题的最小值一定小于等于原始问题的最小值。
参考
Karush-Kuhn-Tucker (KKT)条件
统计学习方法 李航
