条件约束下的最优化问题–拉格朗日乘数法与KKT条件
等式约束优化问题 (拉格朗日乘数定理)
min x f ( x ) s . t . g ( x ) = 0 \min_x f(x) \\ s.t. \quad g(x) = 0xminf(x)s.t.g(x)=0
为方便分析，假设 f ff 与 g gg 是连续可导函数;构造Lagrange函数
L ( x , λ ) = f ( x ) + λ g ( x ) L(x,\lambda) = f(x) + \lambda g(x)L(x,λ)=f(x)+λg(x)
计算 L LL 对 x xx与 λ \lambdaλ 的偏导数并设为零，可得最优解的必要条件：
d L d x = f ′ ( x ) + λ g ′ ( x ) = 0 d L d λ = g ( x ) = 0 \frac{dL}{dx} = f'(x) + \lambda g'(x) = 0 \\ \frac{dL}{d\lambda} = g(x) = 0 \\dxdL=f′(x)+λg′(x)=0dλdL=g(x)=0
简单的例子
求此方程的最小值：
f ( x , y ) = x 2 y f(x,y) = x^2 yf(x,y)=x2y
同时未知数满足约束
x 2 + y 2 = 1 g ( x , y ) = x 2 + y 2 − 1 = 0 x^2 + y^2 = 1 \\ g(x,y) = x^2 + y^2 - 1 = 0x2+y2=1g(x,y)=x2+y2−1=0
构造拉格朗日函数
L = f ( x , y ) + λ g ( x , y ) = x 2 y + λ ( x 2 + y 2 − 1 ) { ∂ L ∂ x = 2 x y + 2 λ x = 0 ∂ L ∂ y = x 2 + 2 λ y = 0 ∂ L ∂ λ = x 2 + y 2 − 1 = 0 ⇒ { x = − 2 3 , x = 2 3 y = − 1 3 , y = − 1 3 λ = 1 3 , λ = 1 3 L = f(x,y) + \lambda g(x,y) = x^2 y + \lambda(x^2 + y^2 - 1) \\ \begin{cases} \frac{\partial{L}}{\partial{x}} = 2xy + 2\lambda x = 0 \\ \frac{\partial{L}}{\partial{y}} = x^2 + 2\lambda y = 0 \\ \frac{\partial{L}}{\partial{\lambda}} = x^2 + y^2 - 1 = 0 \\ \end{cases}\Rightarrow \begin{cases} x = -\sqrt{\frac{2}{3}} , x=\sqrt{\frac{2}{3}} \\ y = -\sqrt{\frac{1}{3}} , y=-\sqrt{\frac{1}{3}} \\ \lambda = \sqrt{\frac{1}{3}} , \lambda=\sqrt{\frac{1}{3}} \\ \end{cases}L=f(x,y)+λg(x,y)=x2y+λ(x2+y2−1)⎩⎨⎧∂x∂L=2xy+2λx=0∂y∂L=x2+2λy=0∂λ∂L=x2+y2−1=0⇒⎩⎨⎧x=−32,x=32y=−31,y=−31λ=31,λ=31
不等式约束优化问题 (KKT条件)
min x f ( x ) s . t . g ( x ) ≤ 0 \min_x f(x) \\ s.t. \quad g(x) \leq 0xminf(x)s.t.g(x)≤0
约束不等式g ( x ) ≤ 0 g(x) \leq 0g(x)≤0称为原始可行性(primal feasibility)，据此我们定义可行域(feasible region) K = { x ∈ R n ∣ g ( x ) ≤ 0 } K=\{x\in R^n|g(x)\leq 0\}K={x∈Rn∣g(x)≤0} 。假设 x ∗ x^*x∗为满足约束条件的最佳解，分开两种情况讨论：
- g ( x ) < 0 g(x) < 0g(x)<0最佳解位于K KK的内部，称为内部解(interior solution)，这时约束条件是无效的(inactive)；
- g ( x ) = 0 g(x) = 0g(x)=0最佳解落在K KK的边界，称为边界解(boundary solution)，此时约束条件是有效的(active)。
这两种情况的最佳解具有不同的必要条件。
- 内部解：在约束条件无效的情形下，g ( x ) g(x)g(x)不起作用，约束优化问题退化为无约束优化问题，因此驻点x ∗ x^*x∗满足f ′ = 0 且 λ = 0 f' = 0且\lambda = 0f′=0且λ=0(因为g ( x ) < 0 且 λ ≠ 0 g(x) < 0且\lambda \neq 0g(x)<0且λ=0，那么L LL的最优就不是f ff的最优)
- 边界解：在约束条件有效的情形下，约束不等式变成等式g ( x ) = 0 g(x) = 0g(x)=0，这与前述Lagrange乘数法的情况相同。我们可以证明驻点x ∗ x^*x∗发生于▽ f ∈ s p a n { ▽ g } ( ▽ g 张成的空间 ) \triangledown f\in span\{\triangledown g\}(\triangledown g张成的空间)▽f∈span{▽g}(▽g张成的空间);换句话说，存在 λ \lambdaλ 使得▽ f = − λ ▽ g \triangledown f = -\lambda \triangledown g▽f=−λ▽g ，但这里 的正负号是有其意义的。因为我们希望最小化f ff，梯度▽ f \triangledown f▽f (函数f ff 在点x xx 的最陡上升方向)应该指向可行域 K KK 的内部(因为你的最优解最小值是在边界取得的)，但▽ g \triangledown g▽g 指向 K KK的外部(即 g ( x ) > 0 g(x) > 0g(x)>0的区域，因为你的约束是小于等于0)，因此 ，称为对偶可行性(dual feasibility)。
因此，不论是内部解或边界解，λ ▽ g = 0 \lambda\triangledown g=0λ▽g=0 恒成立，称为互补松弛性(complementary slackness)。整合上述两种情况，最佳解的必要条件包括Lagrangian函数L ( x , λ ) L(x,\lambda)L(x,λ) 的定常方程式、原始可行性、对偶可行性，以及互补松弛性：
min x f ( x ) s . t . g ( x ) ≤ 0 L = f ( x ) + λ g ( x ) { ∂ L ∂ x = ▽ f + λ ▽ g = 0 g ( x ) ≤ 0 λ ≥ 0 λ g ( x ) = 0 \min_x f(x) \\ s.t. \quad g(x) \leq 0 \\ L = f(x) + \lambda g(x) \\ \begin{cases} \frac{\partial{L}}{\partial{x}} = \triangledown f + \lambda \triangledown g = 0 \\ g(x) \leq 0 \\ \lambda \geq 0 \\ \lambda g(x) = 0 \end{cases}xminf(x)s.t.g(x)≤0L=f(x)+λg(x)⎩⎨⎧∂x∂L=▽f+λ▽g=0g(x)≤0λ≥0λg(x)=0
这些条件合称为Karush-Kuhn-Tucker (KKT)条件。如果我们要最大化 f ( x ) f(x)f(x) 且受限于g ( x ) ≤ 0 g(x) \leq 0g(x)≤0 ，那么对偶可行性要改成 λ ≤ 0 \lambda \leq 0λ≤0 。
上面结果可推广至多个约束等式与约束不等式的情况。
考虑标准约束优化问题(或称非线性规划)：
min x f ( x ) s . t . g j ( x ) = 0 , j = 1 , … , m h k ( x ) ≤ 0 , k = 1 , … , p \min_x f(x) \\ \begin{aligned} s.t. \quad & g_j(x) = 0, j=1,\dots,m \\ & h_k(x) \leq 0, k=1,\dots,p \\ \end{aligned}xminf(x)s.t.gj(x)=0,j=1,…,mhk(x)≤0,k=1,…,p
构造Lagrangian函数
L ( x , { λ j } , { μ k } ) = f ( x ) + ∑ j = 1 m λ j g j ( x ) + ∑ k = 1 p μ k h k ( x ) L(x,\{\lambda_j\},\{\mu_k\}) = f(x) + \sum_{j=1}^m\lambda_jg_j(x) + \sum_{k=1}^p \mu_kh_k(x)L(x,{λj},{μk})=f(x)+j=1∑mλjgj(x)+k=1∑pμkhk(x)
KKT条件为：
{ ▽ x L = 0 g j ( x ) = 0 , j = 1 , … , m h k ( x ) ≤ 0 μ k ≥ 0 μ k h k ( x ) = 0 , k = 1 , … , p \begin{cases} \triangledown_x L = 0 \\ g_j(x) = 0, j=1,\dots,m \\ h_k(x) \leq 0 \\ \mu_k \geq 0 \\ \mu_k h_k(x) = 0, k=1,\dots,p \\ \end{cases}⎩⎨⎧▽xL=0gj(x)=0,j=1,…,mhk(x)≤0μk≥0μkhk(x)=0,k=1,…,p
简单的例子
min x 1 2 + x 2 2 s . t . x 1 + x 2 = 1 x 2 ≤ a \min x_1^2 + x_2^2 \\ \begin{aligned} s.t. \quad & x_1 + x_2 = 1 \\ & x_2 \leq a \end{aligned}minx12+x22s.t.x1+x2=1x2≤a
构造拉格朗日函数
L = x 1 2 + x 2 2 + λ ( 1 − x 1 − x 2 ) + μ ( x 2 − a ) L = x_1^2 + x_2^2 + \lambda(1-x_1-x_2) + \mu(x_2-a)L=x12+x22+λ(1−x1−x2)+μ(x2−a)
利用KKT条件
{ ∂ L ∂ x i = 0 , i = 1 , 2 x 1 + x 2 = 1 x 2 − a ≤ 0 μ ≥ 0 μ ( x 2 − a ) = 0 ⇒ { x 1 = μ 4 + 1 2 x 2 = − μ 4 + 1 2 − μ 4 + 1 2 ≤ a \begin{cases} \frac{\partial{L}}{\partial{x_i}} = 0,i=1,2 \\ x_1 + x_2 = 1 \\ x_2-a \leq 0 \\ \mu \geq 0 \\ \mu(x_2-a) = 0 \\ \end{cases} \Rightarrow \begin{cases} x_1 = \frac{\mu}{4} + \frac{1}{2} \\ x_2 = -\frac{\mu}{4} + \frac{1}{2} \\ -\frac{\mu}{4} + \frac{1}{2} \leq a \\ \end{cases}⎩⎨⎧∂xi∂L=0,i=1,2x1+x2=1x2−a≤0μ≥0μ(x2−a)=0⇒⎩⎨⎧x1=4μ+21x2=−4μ+21−4μ+21≤a
对a aa分类讨论
- 当a ≥ 1 2 a\geq\frac{1}{2}a≥21时，μ = 0 ⇒ x 2 − a < 0 \mu=0\Rightarrow x_2-a < 0μ=0⇒x2−a<0不等式无效，x 1 ∗ = x 2 ∗ = 1 2 , f m i n ( x ) = 1 2 x_1^*=x_2^*=\frac{1}{2},f_{min}(x)=\frac{1}{2}x1∗=x2∗=21,fmin(x)=21
- 当a < 1 2 a<\frac{1}{2}a<21时, 约束不等式有效,x 2 ∗ = a , x 1 ∗ = 1 − a , f m i n ( x ) = ( 1 − a ) 2 + a 2 x_2^*=a,x_1^*=1-a,f_{min}(x)=(1-a)^2+a^2x2∗=a,x1∗=1−a,fmin(x)=(1−a)2+a2
本文参考-- 不等式约束的优化问题 https://zhuanlan.zhihu.com/p/146837325