优化问题中的 KKT 条件解读

[TOC]
KKT(Karush-Kuhn-Tucker Conditions)条件在最优化尤其是凸优化问题中大名鼎鼎, 那么这个条件是怎么来的, 怎么理解它的本质, 以及如何应用它, 相信很多刚入门凸优化的同学跟我抱有相同的疑问. 我整理了以上问题的自己的理解.

前言

首先介绍 KKT 条件的定义:
对于具有等式和不等式约束的一般优化问题:
$$
\begin{aligned}
\min \quad &f_0(x) \\
\text{s.t}. \quad &f_i(x) \leq 0 (i=1,2,3…m) \\
&h_i(x) (i=1,2,3…n)
\end{aligned}
$$
其中 $f_0$ 为目标函数(最小值函数), $f_i$ 为不等式约束, $h_i$ 为等式约束.

如下条件是解 $x^{\star}$ 为最优解的必要条件:

$$
f_{i}\left(x^{\star}\right) \leqslant 0, \quad i=1, \cdots, m\\
h_{i}\left(x^{\star}\right)=0, \quad i=1, \cdots, p\\
\lambda_{i}^{\star} \geqslant 0, \quad i=1, \cdots, m\\
\lambda_{i}^{\star} f_{i}\left(x^{\star}\right)=0, \quad i=1, \cdots, m\\
\nabla f_{0}\left(x^{\star}\right)+\sum_{i=1}^{m} \lambda_{i}^{\star} \nabla f_{i}\left(x^{\star}\right)+\sum_{i=1}^{p} \nu_{i}^{\star} \nabla h_{i}\left(x^{\star}\right)=0
$$

当问题是凸性时(此时 $f(x)$ 为凸函数, $h(x)$ 为仿射函数), KKT 条件为充要条件, 即当问题的一个可行解 $\tilde{x}$ 等于最优解 $x^\star$ 的充要条件是满足 KKT 条件(后面再展开).

ps. 所谓仿射函数(仿射变换)是指对一个向量空间进行一次线性变换(齐次相乘 + 线性相加)并接上一个平移, 变换为另一个向量空间.

如上图中对于向量空间 $\textbf{R}^2$ 中的一个子空间 $U$ 为线性空间.
也就是 $U = {(x, 2x) \in \textbf{R}^2 : x \in \textbf{R}}$, 即 $f(x)=2x,x \in \textbf{R}$.
平移至经过(17,20)点得到的 (17,20)+$U$ 即为 $\textbf{R}^2$ 的一种仿射变换.

推导(拉格朗日对偶)

问题简化

对于原问题我们可以看到问题的复杂度主要源自于后面的约束, 没有约束的话, 我们通过求导, 使得导数函数值为 0 得到零点(求根)就可以求得解(或者是近似解). 因此思路就来了:
将原问题中的约束放入最小化函数中得到增广(问题的维度变大了)的拉格朗日函数(这样我们要考虑的问题就从 $1+m+n$ 个式子变成 1 个式子了)$L: \mathbf{R}^{n} \times \mathbf{R}^{m} \times \mathbf{R}^{p} \rightarrow \mathbf{R}$:
$$
L(x, \lambda, \nu)=f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{p} \nu_{i} h_{i}(x)
$$
其中 $\lambda_i$ 为第 $i$ 个不等式约束的拉格朗日算子, $\nu_i$ 为第 $i$ 个等式约束的拉格朗日算子.

拉格朗日对偶函数

怎么通过求解拉格朗日函数与原问题对应上呢?

定义拉格朗日对偶函数:

$$ g(\lambda, \nu)=\inf _{x \in \mathcal{D}} L(x, \lambda, \nu)=\inf _{x \in \mathcal{D}}\left(f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{p} \nu_{i} h_{i}(x)\right) $$

我们希望求对 $x$ 的最小值(下确界 $p^{\star}$ )来简化原问题的求解. 也就是说希望求得的 $p^{\star}$ 最好就是原问题的解 $d^{\star}$, 即便不是解至少也能极大地缩小范围帮助给出一个精度还可以的解.

可以数学推导出 $d^{\star} \leq p^{\star}$,
如果 $p^{\star} = d^{\star}$, 则称之为强对偶性.
如果 $p^{\star} > d^{\star}$, 则称之为弱对偶性.

如何判断强弱对偶性呢?

有很多判断是否为强对偶性的约束准则, 一种简单的是 Slater 定理.
存在 $x \in \textbf{reint} D$ (定义域内一点)使得下式满足, 说明强对偶性成立.
$$
f_i(x) < 0, \quad i=1,…m, \quad Ax=b
$$

至于更多的准则以及对偶问题的解释, 这里不做深入分析.

互补松弛性

假设强对偶成立可得如下式子:

$$ \begin{aligned} f_{0}\left(x^{\star}\right)&=g\left(\lambda^{\star}, \nu^{\star}\right)\\ &=\inf _{x}\left(f_{0}(x)+\sum_{i=1}^{m} \lambda_{i}^{\star} f_{i}(x)+\sum_{i=1}^{p} \nu_{i}^{\star} h_{i}(x)\right)\\ &\leqslant f_{0}\left(x^{\star}\right)+\sum_{i=1}^{m} \lambda_{i}^{\star} f_{i}\left(x^{\star}\right)+\sum_{i=1}^{p} \nu_{i}^{\star} h_{i}\left(x^{\star}\right)\\ &\leqslant f_{0}\left(x^{\star}\right) \end{aligned} $$ 最后一步跳跃较大, 解释一下, 能直接这么做的原因是 $\lambda^{\star} \geq 0$ 且 $f_i(x) \leq 0$,$h_i(x)=0$.

如果要把不等号变为等号需要使得

$$ \sum_{i=1}^{m} \lambda_{i}^{\star} f_{i}\left(x^{\star}\right)=0 $$

实际上每项都为 0. (推导很简单,假设有一项不为 0, $\lambda_jf_j(x)<0$​, 那么必然存在另一项 $\lambda_kf_k(x)>0$​, 不然的话无法满足总和为 0 的条件. 但是 $\lambda^{\star} \geq 0$ ​且 $f_i(x) \leq 0$​, 也就是说不可能存在两个和相乘大于 0 的项.)
$$
\lambda_{i}^{\star} f_{i}\left(x^{\star}\right)=0, \quad i=1, \cdots, m
$$

可以发现 $\lambda_i$ 与 $f_i(x)$ 互补为 0, 也就被称作互补松弛性, 更有用的推导如下:

$$ \lambda_{i}^{\star}>0 \Longrightarrow f_{i}\left(x^{\star}\right)=0 $$

拉格朗日对偶问题求解

所谓的对偶问题, 一般是指与原问题相伴, 通过解一方可以很方便地求解另一方的求解思路.
通过上面对拉格朗日对偶函数以及对偶性的解释中, 我们得到一种思路: 先求拉格朗日对偶函数的下界, 然后结合约束准则判断对偶函数的最优解是否为原问题的最优解.

假设所有的 $f(x)$ 与 $h(x)$ 可微(定义域为开集), 那我们就可以通过求导函数的根值求解(零点为 $x^{\star}$ )得到 $p^{\star}$.
$$
\nabla f_{0}\left(x^{\star}\right)+\sum_{i=1}^{m} \lambda_{i}^{\star} \nabla f_{i}\left(x^{\star}\right)+\sum_{i=1}^{p} \nu_{i}^{\star} \nabla h_{i}\left(x^{\star}\right)=0
$$

求解此式即可得到 KKT 条件如下:

$$ f_{i}\left(x^{\star}\right) \leqslant 0, \quad i=1, \cdots, m\\\\ h_{i}\left(x^{\star}\right)=0, \quad i=1, \cdots, p\\\\ \lambda_{i}^{\star} \geqslant 0, \quad i=1, \cdots, m\\\\ \lambda_{i}^{\star} f_{i}\left(x^{\star}\right)=0, \quad i=1, \cdots, m\\\\ \nabla f_{0}\left(x^{\star}\right)+\sum_{i=1}^{m} \lambda_{i}^{\star} \nabla f_{i}\left(x^{\star}\right)+\sum_{i=1}^{p} \nu_{i}^{\star} \nabla h_{i}\left(x^{\star}\right)=0 $$

恰如多项式函数 $y=a+bx+cx^2+dx^3+ex^4+fx^5$ 的零点不一定对应着极值(有可能是鞍点), 也就是不满足充分条件. 但极值点一定是零点, 也就是满足必要条件. 因此完成推导.

ps. 如果 $f(x)$ 与 $h(x)$ 不可微怎么办? 还有广义可微的工具帮助我们, 这里不展开.

凸问题中的充要性

假设 $\tilde{x}$ 和 $\tilde{\lambda},\tilde{\nu}$ 分别为原问题与对偶问题的最优解, 满足 KKT 条件可以得到如下推导:

$$ \begin{aligned} g(\tilde{\lambda}, \tilde{\nu})&=L(\tilde{x}, \tilde{\lambda}, \tilde{\nu})\\\\ &=f_{0}(\tilde{x})+\sum_{i=1}^{m} \tilde{\lambda}_{i} f_{i}(\tilde{x})+\sum_{i=1}^{p} \tilde{\nu}_{i} h_{i}(\tilde{x})\\\\ &=f_{0}(\tilde{x}) \end{aligned} $$

即满足强对偶性 $p^{\star} = d^{\star}$.

总结如下: 若某个凸优化问题具有可微的目标函数和约束函数, 且其满足 Slater 条件, 那么 KKT 条件是最优性的充要条件: $x$ 为最优解当且仅当存在 $(\lambda, \nu)$ 满足 KKT 条件. Slater 条件意味着强对偶性以及最优解可以达到.

应用

如何应用 KKT 条件求解问题呢?
当原问题比较复杂, 不好直接求解也许换成对偶形式可以较方便求出解(或者近似解).
下面给出 1 个简单的例子.

等式约束二次凸问题求极小

$$
\begin{aligned}
\min \quad & (1/2)x^TPx + q^Tx + r \\
\text{s.t.} \quad & Ax=b
\end{aligned}
$$

其中 $P \in \textbf{S}_{++}^n$.

此问题的 KKT 条件为
$$
Ax^{\star} = b \\
Px^{\star} + q + A^Tv^{\star} =0
$$

写成方程组形式如下:

$$
\begin{bmatrix}
P & A^T \\
A & 0
\end{bmatrix}
\begin{bmatrix}
x^{\star} \\
v^{\star}
\end{bmatrix} =
\begin{bmatrix}
-q \\
b
\end{bmatrix}
$$
求解关于 $x^{\star},v^{\star}$ 变量的 $m+n$ 个方程即可得到原问题与对偶问题的最优解.

KKT 条件的力学解释

上面的分析都太过于数学化, 有没有实际模型的解释? 下面是从一个弹簧系统的力学角度进行解释, 然后我们就会发现, 上面的数学模型真的有用.

考虑下图, 两个长度为 $w>0$ 的滑块被三个弹簧固定在两个墙面之间, 它们之间不能互相穿透, 也不能穿透墙面.

三个弹簧的弹性势能用滑块的位置 $(x_1,x_2)$ 函数表达为:
$$
f_0(x_1,x_2)=(1/2)(k_1x_1^2 + k_2(x_2 - x_1)^2) + k_3(l - x_2)^2
$$
其中 $k_i>0$ 为各段弹簧的弹性系数.
约束为(不能穿透)运动约束:
$$
w/2-x_1 \leq 0, \quad w-x_2+x_1 \leq 0, \quad w/2 - l + x_2 \leq 0
$$
得到优化问题:

$$
\begin{aligned}
\min \quad & (1/2)(k_1x_1^2 + k_2(x_2 - x_1)^2) + k_3(l - x_2)^2 \\
\text{s.t.} \quad & w/2-x_1 \leq 0 \\
& w-x_2+x_1 \leq 0 \\
& w/2 - l + x_2 \leq 0
\end{aligned}
$$
很明显是个二次优化问题.
引入拉格朗日乘子 $\lambda_1 \geq 0,\lambda_2 \geq 0,\lambda_3 \geq 0$, 根据互补松弛条件可得:
$$
\lambda_1(w/2-x_1)=0 , \quad \lambda_2(w-x_2+x_1)=0 , \quad \lambda_3(w/2 - l + x_2)=0
$$

再对目标函数求偏导零点可得:

$$ \left[\begin{array}{c} k_{1} x_{1}-k_{2}\left(x_{2}-x_{1}\right) \\ k_{2}\left(x_{2}-x_{1}\right)-k_{3}\left(l-x_{2}\right) \end{array}\right]+\lambda_{1}\left[\begin{array}{c} -1 \\ 0 \end{array}\right]+\lambda_{2}\left[\begin{array}{c} 1 \\ -1 \end{array}\right]+\lambda_{3}\left[\begin{array}{l} 0 \\ 1 \end{array}\right]=0 $$

可以看成两个滑块的受力方程式如下图所示:

拉格朗日乘子可以看成墙面对滑块的力(均为接触面反方向).
左边滑块受力: 左侧墙面的力 $\lambda_1$, 右侧墙面的力 $-\lambda_2$. 左侧弹簧力 $k_1x_1$, 右侧弹簧力 $k_2(x_2-x_1)$.
右边滑块受力: 左侧墙面的力 $-\lambda_2$, 右侧墙面的力 $\lambda_3$. 左侧弹簧力 $k_2(x_2-x_1)$, 右侧弹簧力 $k_3(l-x_2)$.

到此为纯物理模型的推导.

拉格朗日对偶问题如下：

$$
L(\lambda,\nu) = (1/2)(k_1x_1^2 + k_2(x_2 - x_1)^2) + k_3(l - x_2)^2 + \\
\lambda_1(w/2-x_1) + \lambda_2(w-x_2+x_1) + \lambda_3(w/2 - l + x_2)
$$
考虑到目标函数约束函数均可微, 也满足 Slater 准测, 即 $2w \leq l$, 可以得到的 KKT 条件与上述例子一样.

由此可以看到 KKT 在实际物理模型中表现完美.

次优解

如果我们无法判断是否为强对偶(例如找不到满足 Slater 准则的点)还可以应用对偶性吗? 答案是肯定的. 通过迭代 + 设置目标准则的方式找到对偶问题已经原问题的最优近似解.
如下公式通过某种方式迭代 $k$ 次使得原问题与对偶问题的差值小于停止准则, 即可得到 $x^{(k)}$ 是 $\epsilon_{abs}-$ 次优.
$$
f_0(x^{(k)}) - g(\lambda^{(k)},\nu^{(k)}) \leq \epsilon_{abs}
$$

也可以采用如下两种形式:
$$
g\left(\lambda^{(k)}, \nu^{(k)}\right)>0, \quad \frac{f_{0}\left(x^{(k)}\right)-g\left(\lambda^{(k)}, \nu^{(k)}\right)}{g\left(\lambda^{(k)}, \nu^{(k)}\right)} \leqslant \epsilon_{\mathrm{rel}}\\
f_{0}\left(x^{(k)}\right)<0, \quad \frac{f_{0}\left(x^{(k)}\right)-g\left(\lambda^{(k)}, \nu^{(k)}\right)}{-f_{0}\left(x^{(k)}\right)} \leqslant \epsilon_{\mathrm{rel}}
$$

小结

本文简单地整理了 KKT 条件是什么, 如何由拉格朗日对偶性推导而来, 以及一个具体的物理模型意义, 最后简单举例应用案例以及思路. 主要参考资料为《convex optimiazation》教材. 很多细节没有深入, 具体可以详细参考此教材.