拉格朗日乘子法(Lagrangian Multiplier Method)和KKT条件

设目标函数f(x),不等式约束约束为g(x),等式约束为h(x)，那么可以将优化问题描述如下

min⁡f(X)s.t.hj(X)=0j=1,2,...,pgk(X)≤0k=1,2,...q\begin{aligned} \min \quad&f(X)\\ s.t. \quad&h_j(X)=0\quad j=1,2,...,p\\ &g_k(X)\le 0 \quad k=1,2,...q\\ \end{aligned} mins.t.​f(X)hj​(X)=0j=1,2,...,pgk​(X)≤0k=1,2,...q​

我们定义不等式约束下的拉格朗日函数L，则L的表达式为

L(X,λ,μ)=f(X)+∑j=1pλjhj(X)+∑k=1qμkgk(X)L(X, \lambda, \mu)=f(X)+\sum\limits_{j=1}^{p}{\lambda_jh_j(X)}+\sum\limits_{k=1}^q{\mu_k\mathrm{g}_k(X)} L(X,λ,μ)=f(X)+j=1∑p​λj​hj​(X)+k=1∑q​μk​gk​(X)

对于有约束的情况下能取到极值点的地方可能有两种情况：

在h(x) 和 等值线相切的地方f(x) 的极值点本身就在可行域里面。

若要求解上述优化问题，必须满足下述的条件，即求解条件：

∂L∂x∣X=X∗=0λj≠0μk≥0μkgk(X∗)=0hj(X∗)=0j=1,2,...,pgk(X∗)≤0k=1,2,...q\begin{aligned} &\frac{\partial L}{\partial x}\bigg|_{X=X^*}=0\\ &\lambda_j\neq0\\ &\mu_k\geq0\\ &\mu_kg_k(X^*)=0\\ &h_j(X^*)=0 \quad j=1,2,...,p\\ &g_k(X^*)\leq0 \quad k=1,2,...q \end{aligned} ​∂x∂L​∣∣∣∣​X=X∗​=0λj​​=0μk​≥0μk​gk​(X∗)=0hj​(X∗)=0j=1,2,...,pgk​(X∗)≤0k=1,2,...q​

这些求解条件就是KKT条件。

(1)是对拉朗格朗日函数取极值时的必要条件

(2)是拉格朗日系数等式约束

(3)是拉格朗日系数不等式约束

(4)是互补松弛条件

(5)(6)原约束条件

增广拉格朗日见我另一个博客