在之前的拉格朗日乘数法中介绍了拉格朗日乘数法求极值的基本思想而当时的约束条件都是等式所以如果约束条件变成了不等式那么如何利用拉格朗日乘数法求极值呢这就是本篇文章中涉及到的拉格朗日乘数法的KTT条件推广。不等式约束对于不等式约束g(x)0g(x)0g(x)0和等式约束h(x)0h(x)0h(x)0不一样h(x)0h(x)0h(x)0可以在平面上画出一条等高线而g(x)0g(x)0g(x)0是一个区域很多个等高线堆叠而成的一块区域我们把这块区域称为可行域。不等式约束分两种情况来讨论第一种是极小值点落在可行域内不包含边界第二种是极小值点落在可行域外包含边界。下面举两个例子来解释这两种情况然后总结两种情况给出转换求解。极小值点落在可行域内不包含边界考虑目标函数f(x)x12x22f(x) x_1^2 x_2^2f(x)x12x22,不等式约束g(x)x12x22−1≤0g(x) x_1^2 x_2^2 -1 \le 0g(x)x12x22−1≤0显然f(x)f(x)f(x)的极小值为原点(0,0)落在可行域内。可行域以原点为圆心半径为1。可以看出这种情况下约束不起作用问题退化成了无约束求最极值问题所以在拉格朗日函数中直接令拉格朗日乘子λ0\lambda0λ0此时拉格朗日函数可不就简化为L(x,λ)f(x)L(x, λ)f(x)L(x,λ)f(x)了。对于这种无约束求极小值点x∗x^*x∗就是求函数f(x)f(x)f(x)的极小值点对应极小值点有f(x∗)f(x^*)f(x∗)的梯度等于0。极小值点落在可行域外包含边界考虑目标函数f(x)(x1−2)2(x22)2f(x) (x_1 - 2)^2 (x_2 2)^2f(x)(x1−2)2(x22)2,不等式约束g(x)x12x22−1≤0g(x) x_1^2 x_2^2 - 1 \le 0g(x)x12x22−1≤0显然f(x)f(x)f(x)的极小值为点(2, -2)落在可行域外。可行域是以原点为圆心半径为1的区域。这种情况约束起作用要考虑求解f(x)f(x)f(x)在可行域内的极小值点。根据梯度的知识对于f(x)f(x)f(x)而言要沿着f(x)f(x)f(x)的负梯度方向走才能走到极小值点如下图的蓝色箭头。这个时候g(x)g(x)g(x)的梯度往区域外发散如下图红色箭头。显然走到极小值点的时候g(x)g(x)g(x)的梯度和f(x)f(x)f(x)的负梯度同向。因为极小值点在边界上这个时候g(x)等于0,那么约束条件变为了等式约束也就是我们之前提到的利用拉格朗日乘数法求解的问题。这里注意一下要求λ0\lambda0λ0因为我们的KKT条件中标准形式是最小化且不等式约束条件都是0的而g(x)的梯度是指向大于 0 的一侧所以有目标函数和约束条件梯度反向。只有当λ0\lambda0λ0是才有能保证目标函数和约束条件梯度反向。至此可以将两种情况做一个总结极小值点落在可行域内不包含边界这个时候可行域的限制不起作用相当于没有约束,直接f(x)的梯度等于0求解这个时候g(x极小值点)0因为落在可行域内。即g(X∗)0λ0g(X^*)0\lambda0g(X∗)0λ0∇xf(X∗)0\nabla_x f(X^*)0∇xf(X∗)0极小值点落在可行域外包含边界可行域的限制起作用极小值点应该落在可行域边界上即g(x)0类似于等值约束此时有g(x)的梯度和f(x)的负梯度同向。即g(X∗)0g(X^*)0g(X∗)0−∇xf(X∗)λg(X∗)λ0-\nabla_x f(X^*)\lambda g(X^*)\lambda0−∇xf(X∗)λg(X∗)λ0将两种情况结合起来并且数学家们为了更简洁的表示两种情况下λ⋅g0\lambda \cdot g0λ⋅g0都成立这样就可以得到拉格朗日乘数法的KKT条件要在约束g(x)⩽0g(\boldsymbol{x}) \leqslant 0g(x)⩽0下最小化f(x)f(\boldsymbol{x})f(x)可转化为在如下约束下最小化式的拉格朗日函数{g(x)⩽0;λ⩾0;λjgj(x)0. \begin{cases} g(\boldsymbol{x}) \leqslant 0; \\ \lambda \geqslant 0; \\ \lambda_j g_j(\boldsymbol{x}) 0 . \end{cases}⎩⎨⎧g(x)⩽0;λ⩾0;λjgj(x)0.对应最小值的解满足如下约束∇xL(x∗,λ∗)0\nabla_x \mathcal{L}(x^*,\lambda^*) 0∇xL(x∗,λ∗)0(拉格朗日求解条件)λ∗≥0\lambda^* \ge 0λ∗≥0拉格朗日乘子必须为非负称为对偶可行性条件λ∗g(x∗)0\lambda^* g(x^*) 0λ∗g(x∗)0转换为拉格朗日函数两种分类情况的约束称为互补松弛条件g(x∗)⩽0g({x^*}) \leqslant 0g(x∗)⩽0(原始问题中的约束条件称为可行性条件)这些条件称为 Karush-Kuhn-Tucker (简称KKT)条件。上述做法可推广到多个约束。考虑具有mmm个等式约束和nnn个不等式约束且可行域D⊂Rd\mathbb{D} \subset \mathbb{R}^dD⊂Rd非空的优化问题minxf(x)s.t.hi(x)0(i1,…,m),gj(x)⩽0(j1,…,n). \begin{align} \min_{\boldsymbol{x}} \quad f(\boldsymbol{x}) \\ \text{s.t.} \quad h_i(\boldsymbol{x}) 0 \quad (i1,\dots,m), \\ g_j(\boldsymbol{x}) \leqslant 0 \quad (j1,\dots,n). \end{align}xmins.t.f(x)hi(x)0(i1,…,m),gj(x)⩽0(j1,…,n).引入拉格朗日乘子λ(λ1,λ2,…,λm)T\boldsymbol{\lambda} (\lambda_1,\lambda_2,\dots,\lambda_m)^\mathrm{T}λ(λ1,λ2,…,λm)T和μ(μ1,μ2,…,μn)T\boldsymbol{\mu} (\mu_1,\mu_2,\dots,\mu_n)^\mathrm{T}μ(μ1,μ2,…,μn)T相应的拉格朗日函数为L(x,λ,μ)f(x)∑i1mλihi(x)∑j1nμjgj(x) L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) f(\boldsymbol{x}) \sum_{i1}^{m} \lambda_i h_i(\boldsymbol{x}) \sum_{j1}^{n} \mu_j g_j(\boldsymbol{x})L(x,λ,μ)f(x)i1∑mλihi(x)j1∑nμjgj(x)由不等式约束引入的 KKT 条件(j1,2,…,n)(j 1,2,\dots,n)(j1,2,…,n)为{gj(x)⩽0;μj⩾0;μjgj(x)0. \begin{cases} g_j(\boldsymbol{x}) \leqslant 0; \\ \mu_j \geqslant 0; \\ \mu_j g_j(\boldsymbol{x}) 0 . \end{cases}⎩⎨⎧gj(x)⩽0;μj⩾0;μjgj(x)0.特别注意优化问题是凸优化的话KKT条件就是极小值点而且是全局极小存在的充要条件。
)
