【凸优化笔记6】-拉格朗日对偶（Lagrange duality）、KKT条件

Author: [Lauer]

Link: [https://zhuanlan.zhihu.com/p/103961917]

1. 问题背景

在一个优化问题中，原始问题通常会带有很多约束条件，这样直接求解原始问题往往是很困难的，于是考虑将原始问题转化为它的对偶问题，通过求解它的对偶问题来得到原始问题的解。**对偶性（Duality）是凸优化问题的核心内容。

2. 原始问题极其转化

2.1 原始问题（Primal problem）

将一个原始最优化问题写成如下形式：

\begin{aligned} \min_x &\quad f_0(x) \\ s.t. &\quad f_i(x) \leq 0, i=1,2,...,m \\ &\quad h_j(x) = 0,j=1,2,...,p \end{aligned}

这里可以参考【凸优化笔记3】-第1节-凸优化问题中对凸优化问题的定义。
需要注意的是 $f_i(x)\leq0$ 的形式，若是大于等于 $0$ ，则需要修改符号转成这种形式，以避免不必要的麻烦。

事实上，在求解原问题的对偶问题时，并不要求原始问题一定是凸问题， $f$ 和 $h$ 可以是一般函数而不一定非得是凸函数。

2.2 拉格朗日函数（Lagrangian function）

将原始问题的拉格朗日函数定义为：

L(x, \lambda, v) = f_0(x)+\sum_{i=1}^{m}{\lambda_if_i(x)}+\sum_{j=1}^{p}{v_jh_j(x)}

其中 $x\in R^n,\lambda\in R^m,v\in R^p$ 。可以看到，拉格朗日函数 $L$ 相对于原始问题引入了两个新变量（向量） $\lambda,v$ ，称为拉格朗日乘子。

拉格朗日函数 $L$ 如果看成是关于 $x$ 的函数，那它其实就是对原始问题中目标函数与约束条件进行线性加权，目标函数的权系数是 $1$ ，约束条件的权系数是 $\lambda_i$ 或 $v_i$ ；
如果 $L$ 看成是关于 $\lambda$ 或 $v$ 的函数，则其余部分可看成常数， $L$ 就可看作是一个关于 $\lambda$ 或 $v$ 的仿射函数（即最高次幂为1的多项式函数）。

2.3 拉格朗日对偶函数（ Lagrange dual function）

拉格朗日对偶函数（简称对偶函数）通过对拉格朗日函数关于 $x$ 取下确界得到，即：

g(\lambda, v) = \inf_xL(x,\lambda,v)

$inf$ 符号表示取下确界。求解析式可先将 $L$ 看成是关于 $x$ 的函数，而将拉格朗日乘子看作常数，求出 $L$ 的极小值点，再将该点代入 $L$ ，得到的关于 $\lambda$ 和 $v$ 的表达式就是对偶函数。

对偶函数具有如下两条重要性质： i. 对偶函数一定是凹函数，其凹性与原目标函数和约束函数凹凸与否无关。

证明：
$L(x,\lambda,v)$ 可以看作是一个无限的函数集，这个函数集中每个元素是 $L(x_i,\lambda,v)$ ， $x$ 取遍其在定义域上的所有值得到不同的 $x_i$ 。针对不同的 $x_i$ ， $L(x_i,\lambda,v)$ 的表达式不一样，由于这个表达式是只关于 $\lambda$ 和 $v$ 的，故用 $g_i(\lambda,v)$ 来表示。所以有：
$g(\lambda,v)=inf\{g_1(\lambda,v),g_2(\lambda,v),...,g_\infty(\lambda,v)\}$
由本章 2.2 节已提到过，当 $L$ 看成是关于 $\lambda$ 或 $v$ 的函数时， $L$ 是一个仿射函数，亦即， $g_i(\lambda,v)$ 是仿射函数，对仿射函数集取下确界，得到的函数是凹/凸函数，如图 2-1 所示：

图 2-1

黑线加粗部分就是 $g(\lambda,v)$ ，是凹/凸函数。

ii. 对 $\forall\lambda\geq0,\forall v$ （泛指向量中的每个分量），如果原问题最优解对应的目标函数值为 $p^*$ ,则 $g(\lambda, v)\leq p^*$ 。

证明：
设原问题的最优解为 $x^*$ ，结合 $f_i(x)\leq0,h_j(x)=0$ ，很容易有： $L(x^*, \lambda, v) = f_0(x^*)+\sum_{i=1}^{m}{\lambda_if_i(x^*)}+\sum_{j=1}^{p}{v_jh_j(x^*)}\leq f_0(x^*)=p^*$ 假设这个最优解 $x^*$ 在 $x_1$ 处取得，结合性质 i 中的证明部分，有： $L(x^*,\lambda,v)=g_1(\lambda,v)$ 很显然，由图 2-3 可以看到 $g(\lambda,v)$ 的图像总在 $g_1(\lambda,v)$ 下方，即以下不等式总成立：
$g(\lambda,v)\leq L(x^*,\lambda,v)\leq p^*$

3. 拉格朗日对偶问题（Lagrange dual problem）

根据对偶函数的重要性质 ii ，对 $\forall\lambda\geq0,\forall v$ ，对偶函数 $g(\lambda,v)$ 是原问题最优值 $p^*$ 的一个下界，最好的下界就是最大化对偶函数，因此构造原问题的对偶问题：

$\\ \begin{aligned} \max_{\lambda,v} &\quad g(\lambda,u) \\ s.t. &\quad \lambda\geq 0\end{aligned}$

由于对偶函数是凹函数，故拉格朗日对偶问题一定是凸优化问题，其对应的最优解为 $\lambda^*,v^*$ （最优拉格朗日乘子），若对应的最优值为 $d^*$ ，则总有 $d^*\leq p*$ 。

当 $d^*\leq p^*$ 时，称为弱对偶（weak duality）。

当 $d^*=p^*$ 时，称为强对偶（strong duality）。

将 $p^*-d^*$ 称为对偶间隙（duality gap）。

在解存在的情况下，弱对偶总是成立的。
满足强对偶时，可以通过求解对偶问题来得到原始问题的解。

4. Slater 条件（Slater's condition）

Slater 条件用于判断什么情况下强对偶是成立的。

在原问题是凸问题的情况下，若 $\exists \ x\in relint(D)$ ，使得约束条件满足：

$f_i(x)<0,h_j(x)=0\ \ \ i=1,2...,m;j=1,2,...,p$

则强对偶成立。

$relint(D)$ 表示原始凸问题定义域的相对内部，即在定义域上除了边界点以外的所有点。只要能找到一个这样的点使原凸问题等式约束依然成立且不等式约束都严格小于 $0$ 即可。
幸运的是，对大多数一般的原凸问题，强对偶都是成立的。

若满足 Slater 条件，则强对偶一定成立，不满足 Slater 条件，强对偶也可能成立，它是一个充分不必要条件。

5. KKT 条件（KKT conditions）

KKT条件见当前文档目录下的拉格朗日乘子&KKT一节

对一般的原问题，KKT 条件是 $x^*;\lambda^*,v^*$ 为最优解的必要条件，即只要 $x^*;\lambda^*,v^*$ 为最优解，则一定满足 KKT 条件。对原问题为凸问题， KKT 条件是 $x^*;\lambda^*,v^*$ 为最优解的充要条件。