条件约束下的最优化问题

作者: pdnbplus | 发布时间: 2024/07/13 | 阅读量: 323

条件约束下的最优化问题--拉格朗日乘数法与KKT条件

等式约束优化问题 (拉格朗日乘数定理)

min⁡xf(x)s.t.g(x)=0\min_x f(x) \\ s.t. \quad g(x) = 0
为方便分析，假设 ff 与 gg 是连续可导函数;构造Lagrange函数
L(x,λ)=f(x)+λg(x)L(x,\lambda) = f(x) + \lambda g(x)
计算 LL 对 xx与 λ\lambda 的偏导数并设为零，可得最优解的必要条件：
dLdx=f′(x)+λg′(x)=0dLdλ=g(x)=0\frac{dL}{dx} = f'(x) + \lambda g'(x) = 0 \\ \frac{dL}{d\lambda} = g(x) = 0 \\

简单的例子

求此方程的最小值：
f(x,y)=x2yf(x,y) = x^2 y
同时未知数满足约束
x2+y2=1g(x,y)=x2+y2−1=0x^2 + y^2 = 1 \\ g(x,y) = x^2 + y^2 - 1 = 0
构造拉格朗日函数
L=f(x,y)+λg(x,y)=x2y+λ(x2+y2−1){∂L∂x=2xy+2λx=0∂L∂y=x2+2λy=0∂L∂λ=x2+y2−1=0⇒{x=−23,x=23y=−13,y=−13λ=13,λ=13L = 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}

不等式约束优化问题 (KKT条件)

min⁡xf(x)s.t.g(x)≤0\min_x f(x) \\ s.t. \quad g(x) \leq 0
约束不等式g(x)≤0g(x) \leq 0称为原始可行性(primal feasibility)，据此我们定义可行域(feasible region) K={x∈Rn∣g(x)≤0}K=\{x\in R^n|g(x)\leq 0\} 。假设 x∗x^*为满足约束条件的最佳解，分开两种情况讨论：

  1. g(x)<0g(x) < 0最佳解位于KK的内部，称为内部解(interior solution)，这时约束条件是无效的(inactive)；
  2. g(x)=0g(x) = 0最佳解落在KK的边界，称为边界解(boundary solution)，此时约束条件是有效的(active)。

这两种情况的最佳解具有不同的必要条件。

  1. 内部解：在约束条件无效的情形下，g(x)g(x)不起作用，约束优化问题退化为无约束优化问题，因此驻点x∗x^*满足f′=0且λ=0f' = 0且\lambda = 0(因为g(x)<0且λ≠0g(x) < 0且\lambda \neq 0，那么LL的最优就不是ff的最优)
  2. 边界解：在约束条件有效的情形下，约束不等式变成等式g(x)=0g(x) = 0，这与前述Lagrange乘数法的情况相同。我们可以证明驻点x∗x^*发生于▽f∈span{▽g}(▽g张成的空间)\triangledown f\in span\{\triangledown g\}(\triangledown g张成的空间);换句话说，存在 λ\lambda 使得▽f=−λ▽g\triangledown f = -\lambda \triangledown g ，但这里 的正负号是有其意义的。因为我们希望最小化ff，梯度▽f\triangledown f (函数ff 在点xx 的最陡上升方向)应该指向可行域 KK 的内部(因为你的最优解最小值是在边界取得的)，但▽g\triangledown g 指向 KK的外部(即 g(x)>0g(x) > 0的区域，因为你的约束是小于等于0)，因此 ，称为对偶可行性(dual feasibility)。

因此，不论是内部解或边界解，λ▽g=0\lambda\triangledown g=0 恒成立，称为互补松弛性(complementary slackness)。整合上述两种情况，最佳解的必要条件包括Lagrangian函数L(x,λ)L(x,\lambda) 的定常方程式、原始可行性、对偶可行性，以及互补松弛性：
min⁡xf(x)s.t.g(x)≤0L=f(x)+λg(x){∂L∂x=▽f+λ▽g=0g(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}
这些条件合称为Karush-Kuhn-Tucker (KKT)条件。如果我们要最大化 f(x)f(x) 且受限于g(x)≤0g(x) \leq 0 ，那么对偶可行性要改成 λ≤0\lambda \leq 0 。

上面结果可推广至多个约束等式与约束不等式的情况。

考虑标准约束优化问题(或称非线性规划)：
min⁡xf(x)s.t.gj(x)=0,j=1,…,mhk(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}
构造Lagrangian函数
L(x,{λj},{μk})=f(x)+∑j=1mλjgj(x)+∑k=1pμkhk(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)
KKT条件为：
{▽xL=0gj(x)=0,j=1,…,mhk(x)≤0μk≥0μkhk(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}

简单的例子

min⁡x12+x22s.t.x1+x2=1x2≤a\min x_1^2 + x_2^2 \\ \begin{aligned} s.t. \quad & x_1 + x_2 = 1 \\ & x_2 \leq a \end{aligned}
构造拉格朗日函数
L=x12+x22+λ(1−x1−x2)+μ(x2−a)L = x_1^2 + x_2^2 + \lambda(1-x_1-x_2) + \mu(x_2-a)
利用KKT条件
{∂L∂xi=0,i=1,2x1+x2=1x2−a≤0μ≥0μ(x2−a)=0⇒{x1=μ4+12x2=−μ4+12−μ4+12≤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}
对aa分类讨论

  • 当a≥12a\geq\frac{1}{2}时，μ=0⇒x2−a<0\mu=0\Rightarrow x_2-a < 0不等式无效，x1∗=x2∗=12,fmin(x)=12x_1^*=x_2^*=\frac{1}{2},f_{min}(x)=\frac{1}{2}
  • 当a<12a<\frac{1}{2}时, 约束不等式有效,x2∗=a,x1∗=1−a,fmin(x)=(1−a)2+a2x_2^*=a,x_1^*=1-a,f_{min}(x)=(1-a)^2+a^2

本文参考-- 不等式约束的优化问题 https://zhuanlan.zhihu.com/p/146837325