凸优化中的KKT条件及与拉格朗日对偶的关系

本文将手把手教你理解并应用凸优化中的关键工具：KKT条件，以及它如何与拉格朗日对偶性相互关联。这是一个实操指南，目标是让你能清晰识别问题、列出条件、并理解其背后的逻辑关系。

1. 识别可应用KKT条件的优化问题

首先，你需要判断你面对的优化问题是否满足使用KKT条件的基本前提。

确认问题为凸优化问题。
目标函数必须是凸函数，且所有约束条件定义的可行域是凸集。一个简单判断：如果目标函数形如 $f(x) = x^2$ 这类向上开口的抛物线，且约束是线性的（如 $a^Tx \leq b$），那么它大概率是凸问题。
确认存在等式与不等式约束。
KKT条件处理的是一般形式的优化问题：
$$ \begin{aligned} \min_{x} \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \leq 0, \quad i=1,...,m \\ & h_j(x) = 0, \quad j=1,...,p \end{aligned} $$
其中 $f(x)$ 是待最小化的目标函数，$g_i(x) \leq 0$ 是不等式约束，$h_j(x) = 0$ 是等式约束。
检查约束规范性条件。
对于凸问题，通常需要满足一些温和的“约束规范”条件（如Slater条件）才能保证KKT条件是最优性的充要条件。一个常用的充分条件是：问题严格可行，即存在一个点严格满足所有不等式约束（$g_i(x) < 0$）。

这是连接原问题与KKT条件、对偶问题的核心桥梁。

为每个约束引入拉格朗日乘子。
对于每个不等式约束 $g_i(x) \leq 0$，引入一个乘子 $\lambda_i$。对于每个等式约束 $h_j(x) = 0$，引入一个乘子 $\nu_j$。
写出拉格朗日函数。
将目标函数与所有“约束函数乘以对应乘子”相加，形成拉格朗日函数 $L(x, \lambda, \nu)$：
$$ L(x, \lambda, \nu) = f(x) + \sum_{i=1}^{m} \lambda_i g_i(x) + \sum_{j=1}^{p} \nu_j h_j(x) $$
这个函数打包了原问题的所有信息：目标和约束。乘子 $\lambda$ 和 $\nu$ 衡量了相应约束的“违反程度”对最优值的影响。

对于一个满足前述条件的凸优化问题，其最优解 $x^*$ 及其对应的乘子 $(\lambda^*, \nu^*)$ 必须同时满足以下四个条件，这四个条件合称为KKT条件。

梯度为零。
拉格朗日函数关于原变量 $x$ 的梯度在最优点处为零。这反映了最优解处，目标函数的变化趋势与约束力达成平衡。
$$ \nabla_x L(x^*, \lambda^*, \nu^*) = 0 $$
原始可行性。
最优点必须满足原问题的所有约束。
$$ g_i(x^*) \leq 0, \quad i=1,...,m \\ h_j(x^*) = 0, \quad j=1,...,p $$
对偶可行性。
对应于不等式约束的乘子必须非负。这有其经济学解释：放松一个约束（让 $g_i(x)$ 更负）带来的收益（目标函数降低）不应是负的。
$$ \lambda_i^* \geq 0, \quad i=1,...,m $$
互补松弛性。
这是KKT条件中最具洞察力的一条。它表明：对于每一个不等式约束，要么该约束在最优解处是紧的（$g_i(x^*) = 0$），要么其对应的乘子为零（$\lambda_i^* = 0$）。两者必须至少有一个成立。
$$ \lambda_i^* g_i(x^*) = 0, \quad i=1,...,m $$
用白话说，如果一个约束在最优解处没有用上（$g_i(x^*) < 0$），那么它对应的乘子 $\lambda_i^*$ 一定为零，表示该约束是“松弛”的，不影响最优值。

KKT条件不仅是寻找原问题最优解的充要条件，它也深刻地揭示了原问题与对偶问题之间的纽带。

构造对偶问题。
保持乘子 $\lambda \geq 0$ 不变，将拉格朗日函数 $L(x, \lambda, \nu)$ 视为关于 $x$ 的函数，并求其最小值，得到一个只关于 $\lambda, \nu$ 的函数，称为对偶函数 $g(\lambda, \nu)$：
$$ g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu) $$
对偶问题就是在 $\lambda \geq 0$ 的约束下，最大化这个对偶函数：
$$ \max_{\lambda \geq 0, \nu} \quad g(\lambda, \nu) $$
通过KKT条件连接原问题与对偶问题。
- 弱对偶性总是成立：对偶问题的最优值 $\leq$ 原问题的最优值。
- 强对偶性在凸问题下通常成立：在满足约束规范条件的凸问题中，原问题与对偶问题的最优值相等。此时，KKT条件成立的点 $(x^*, \lambda^*, \nu^*)$ 同时给出了原问题和对偶问题的最优解。
具体联系：
- KKT条件中的 “梯度为零” ($\nabla_x L=0$) 正是求解对偶函数 $g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu)$ 的必要条件。换句话说，对偶函数在最优乘子处的值，是通过解这个方程得到的。
- KKT条件中的 “互补松弛性” 保证了原问题最优值与对偶最优值的“间隙”为零，是强对偶性成立时解的特征。
- 当你通过求解KKT方程组（或对偶问题）得到一组解 $(x^*, \lambda^*, \nu^*)$ 时，这组解自动满足了对偶性，并提供了原问题最优解与最优乘子（对偶变量）的完整信息。

简言之：KKT条件是原问题最优解必须满足的方程组。对偶问题是将原问题的约束转化为了优化目标。在凸优化中，求解KKT方程组等价于同时找到了原问题和对偶问题的最优解，两者通过拉格朗日乘子紧密相连。互补松弛性是理解哪些约束在最优解处起作用（active）的关键。