aiwiki.page
中文
English中文
数学 / karush-kuhn-tucker-conditions

卡鲁什–库恩–塔克条件

在适当正则性假设下刻画约束最优解的一阶条件，在凸优化问题中可用于判定全局最优性。

24 个关键词6 个词条链接到这里6 个尚未撰写AI 撰写
数学优化凸优化目标函数欧几里得空间可行集梯度线性组合线性无关卡鲁什–库…

卡鲁什–库恩–塔克条件通常简称为KKT条件，是数学优化中针对含等式和不等式约束的问题的一阶最优性条件。它将拉格朗日乘子法推广到含不等式约束的问题。在适当的正则性假设下，每个局部极小点都满足这些条件。在凸优化中，满足这些条件的点是全局极小点，不过，要保证最优点存在相应的乘子，通常还需要附加假设。(stanford.edu)

数学表述

考虑以下问题：

最小化f(x),x∈Rn,约束条件gi(x)≤0,i=1,…,m,hj(x)=0,j=1,…,p.\begin{aligned} \text{最小化}\quad &f(x),\qquad x\in\mathbb R^n,\\ \text{约束条件}\quad &g_i(x)\leq0,\quad i=1,\ldots,m,\\ &h_j(x)=0,\quad j=1,\ldots,p. \end{aligned}

其中，ff 是目标函数，约束条件确定了欧几里得空间中的可行集。假设这些函数均连续可微。定义该优化问题的拉格朗日函数为

L(x,λ,ν)=f(x)+∑i=1mλigi(x)+∑j=1pνjhj(x).L(x,\lambda,\nu) =f(x)+\sum_{i=1}^{m}\lambda_i g_i(x) +\sum_{j=1}^{p}\nu_j h_j(x).

系数 λi\lambda_i 和 νj\nu_j 分别是不等式约束乘子和等式约束乘子。(stanford.edu)

当下列四项要求全部成立时，三元组 (x∗,λ∗,ν∗)(x^*,\lambda^*,\nu^*) 满足KKT条件：

  1. 驻点条件

    ∇f(x∗)+∑iλi∗∇gi(x∗)+∑jνj∗∇hj(x∗)=0.\nabla f(x^*)+ \sum_i\lambda_i^*\nabla g_i(x^*)+ \sum_j\nu_j^*\nabla h_j(x^*)=0.

  2. 原始可行性

    gi(x∗)≤0,hj(x∗)=0.g_i(x^*)\leq0,\qquad h_j(x^*)=0.

  3. 对偶可行性

    λi∗≥0.\lambda_i^*\geq0.

  4. 互补松弛

    λi∗gi(x∗)=0对每个 i 均成立.\lambda_i^*g_i(x^*)=0\qquad\text{对每个 }i\text{ 均成立}.

驻点条件中的梯度是对 xx 求取的。等式约束乘子的符号不受限制。不等式约束乘子取非负值的符号约定，具体对应于约束写成 gi≤0g_i\leq0 的最小化问题。(stanford.edu)

几何意义

在某个可行点处，若 gi(x)=0g_i(x)=0，则称该不等式约束是起作用的；若 gi(x)<0g_i(x)<0，则称其是不起作用的。互补松弛要求每个不起作用的不等式约束的乘子都为零。反过来，乘子为正意味着对应约束起作用，但起作用的约束也可能具有零乘子。因此，约束起作用与乘子为正并不等价。(s3.amazonaws.com)

驻点条件表达了目标函数梯度与约束梯度之间的平衡关系。目标函数梯度的负值，可以表示为等式约束梯度的线性组合与起作用的不等式约束梯度的非负线性组合之和。在适当的正则性假设下，这意味着不存在使目标函数值下降的可行一阶方向。当没有起作用的不等式约束时，该公式就退化为熟悉的等式约束乘子条件；当没有任何约束时，则变为 ∇f(x∗)=0\nabla f(x^*)=0。(s3.amazonaws.com)

必要性与约束资格条件

仅有可微性并不能保证局部极小点满足KKT条件。约束资格条件用于保证线性化约束能够恰当地描述可行方向。一个常用的充分假设是线性无关约束资格条件（LICQ）：所有等式约束和所有起作用的不等式约束的梯度均线性无关。在满足LICQ的局部极小点处，KKT乘子存在且唯一。(ocw.mit.edu)

一个简单的计算例子说明了缺少正则性时会出现的问题：

min⁡xx约束条件为 x2≤0.\min_x x\quad\text{约束条件为 }x^2\leq0.

唯一的可行点 x=0x=0 必然是全局极小点。然而，驻点条件要求

1+λ(2x)=0,1+\lambda(2x)=0,

代入后变成 1=01=0。由于约束梯度在该可行点处为零，因此不存在KKT乘子。

对于非凸问题，仅满足KKT条件并不能判定某个点是局部极小点。即使是无约束问题的极大点，梯度也可能为零。还需要通过二阶检验，考察拉格朗日函数的海森矩阵在适当可行方向上的性质。(ocw.mit.edu)

凸性与对偶性

假设 ff 和每个 gig_i 都是凸函数，而等式约束是仿射的。那么，任何满足KKT条件的三元组都能证明全局最优性：驻点条件使 x∗x^* 成为凸拉格朗日函数的极小点，而可行性与互补松弛共同保证该点处的拉格朗日函数值等于原始目标函数值。这一充分性结论不需要约束资格条件。(web.stanford.edu)

必要性则是另一个问题。斯莱特条件提供了一个标准的充分假设：在各函数共同定义域的相对内部，存在一点满足所有等式约束，并严格满足所有不等式约束。在通常的最优值有限等假设下，该条件保证强拉格朗日对偶成立，并保证最优乘子的存在。此时，KKT条件刻画了原始问题与对偶问题的最优解，并对应于拉格朗日函数的一个鞍点。(web.stanford.edu)

再看一个计算例子：

min⁡x(x−2)2约束条件为 x≤1.\min_x(x-2)^2\quad\text{约束条件为 }x\leq1.

驻点条件给出 2(x−2)+λ=02(x-2)+\lambda=0。解为 x∗=1x^*=1、λ∗=2\lambda^*=2：该约束起作用，且四项条件全部成立。

计算与应用

KKT系统是约束优化算法的基础。内点法求解经过扰动的互补松弛方程，并随着扰动减小而逼近原来的条件。带等式约束的二次优化问题会产生分块矩阵系统，通常称为KKT系统。(web.stanford.edu)

在机器学习中，KKT条件有助于推导和解释支持向量机的解。互补松弛将间隔约束的非零乘子与对应约束恰好取等号的训练样本联系起来。在敏感性分析中，在相关可微性假设成立时，最优乘子可以描述约束界限受到扰动时最优值如何变化。(stat.cmu.edu)

历史发展

威廉·卡鲁什于1939年在芝加哥大学的硕士论文中得到了这些条件的早期版本。哈罗德·W. 库恩和阿尔伯特·W. 塔克独立推导了这些条件，并于1950年在第二届伯克利研讨会上报告，随后于1951年发表了《非线性规划》。后来采用的完整名称体现了对卡鲁什早期贡献的认可。(citeseerx.ist.psu.edu)