对于一般地约束优化问题
其中,自变量\boldsymbol x\in \mathbb{R}^n。设f(\boldsymbol x),g_i(\boldsymbol x),h_j(\boldsymbol x)具有连续的一阶偏导数,\boldsymbol x^*是优化问题的局部可行解。若在\boldsymbol x^*处约束限制条件(constraint qualifications or regularity conditions)[1][2]成立,则一定存在\boldsymbol \mu^*=(\mu_1^*,\mu_2^*,…,\mu_m^*)^T,\boldsymbol \lambda^*=(\lambda_1^*,\lambda_2^*,…,\lambda_n^*)^T,使得
其中L(\boldsymbol x,\boldsymbol \mu,\boldsymbol \lambda)为拉格朗日函数
以上5条即为KKT条件,其中条件(2)和(3)为约束条件显然成立,条件(1)、(4)、(5)成立的简单证明(严格数学证明参见[1] § 4.2.1)如下:

由约束条件:g_i(\boldsymbol x) \leq 0可知,\boldsymbol x^*一定满足g_i(\boldsymbol x^*) \lt 0或者g_i(\boldsymbol x^*) = 0,下面对这两种情形分别进行讨论:
- 当g_i(\boldsymbol x^*) \lt 0时:
此时极小值点在g_i(\boldsymbol x) \lt 0这个区域内(如上图左部所示),所以g_i(\boldsymbol x) \leq 0这个约束可以忽略,那么此时的优化问题等价于仅含等式约束的优化问题,所以\mu_i^* = 0。 - 当g_i(\boldsymbol x^*) = 0时:
此时极小值点在g_i(\boldsymbol x) = 0这个边界上,所以约束g_i(\boldsymbol x) \leq 0等价于约束g_i(\boldsymbol x) = 0,那么此时的优化问题同样等价于仅含等式约束的最优化问题。根据拉格朗日乘子法的原理可知,此时f(\boldsymbol x)和 g_i(\boldsymbol x)=0在极小值点处相切(如上图右部所示),梯度(正梯度)平行,即\nabla f(\boldsymbol x^*)+\mu_i^* \nabla g_i(\boldsymbol x^*)=0 \quad (\mu_i^*\in \mathbb{R})。易知g_i(\boldsymbol x)=0这个边界上的梯度都是向外的,而\nabla f(\boldsymbol x^*)一定和\nabla g_i(\boldsymbol x^*)的方向相反(如果不相反的话极小值点就不会在边界上取到而是在g_i(\boldsymbol x) \lt 0内取),所以\nabla f(\boldsymbol x^*)和\nabla g_i(\boldsymbol x^*)异号,那么\mu_i^*一定大于0。
综上,当g_i(\boldsymbol x^*) \lt 0时\mu_i^* = 0, g_i(\boldsymbol x^*) = 0时\mu_i^* \gt 0,所以条件(4)、(5)恒成立;由于对\lambda_j取值无要求,所以总存在\lambda_j^*使得条件(1)恒成立。
【注】:
- 若在\boldsymbol x^*处约束限制条件成立,则KKT条件是局部可行解\boldsymbol x^*的必要条件;
- 若在\boldsymbol x^*处约束限制条件不成立,则局部解\boldsymbol x^*不一定满足KKT条件(证明参见[1] § 4.2.1);
- 满足KKT条件的点\boldsymbol x^*不一定是局部可行解(证明参见[1] § 4.2.1);
- 若上述优化问题是凸优化问题,也即目标函数f(\boldsymbol x)是凸函数,不等式约束g_i(\boldsymbol x)是凸函数,等式约束h_j(\boldsymbol x)是仿射函数,那么此时KKT条件为局部可行解\boldsymbol x^*的充分条件,同时局部可行解\boldsymbol x^*也为全局可行解(证明参见[1] § 4.4),特别地,此时若在\boldsymbol x^*处约束限制条件也成立,那么KKT条件即升级为充要条件=充分条件+必要条件;
参考文献:
[1] 王燕军. 《最优化基础理论与方法》
[2] Karush–Kuhn–Tucker conditions
加载更多评论