本文主要讲解有关原问题和拉格朗日对偶问题，以及它们之间的关系，从而引出弱对偶性和强对偶性以及 KKT 条件和 Slater 条件。
一、原问题与拉格朗日函数
1. 原问题
优化问题一般都可以写为下面的形式：
$$
\min f_0(x),\quad x\in R^n
$$
$$
s.t.\quad f_i(x)\leq0,\quad i=1,2,…,m
$$
$$
\quad \quad h_j(x)=0,\quad j=1,2,…,p
$$
以上形式被成为原问题，即求解一个满足 m 个不等式约束和 p 个等式约束的函数 $f_0(x)$ 的最小值。实际上我们并不关心最小值是什么，而是关心最小值在 x 是什么的时候取得。下面的讨论如果不加以说明都是针对一般的优化问题来说的。
2. 拉格朗日函数
解决带约束的条件的优化问题的一般解决办法是拉格朗日乘子法，也就是先写出拉格朗日函数，再让拉氏函数对 x 求导得到导数为 0 的点，将这些点带入原函数，则其中的最大值即为原函数的最大值，最小值即为原函数的最小值。上述优化问题的拉氏函数为：
$$
L(x,u,v)=f_0(x)+\sum_{i=1}^mu_if_i(x)+\sum_{j=1}^pv_jh_j(x)
$$
其中 $u_i\geq0$，$v_j\in R$，这是因为在可行域内 $f_i(x)\leq0$，所以当 $u_i\geq0$ 时， $\sum_{i=1}^mu_if_i(x)$ 的最大值为 0；因为 $h_j(x)=0$，所以 $\sum_{j=1}^pv_jh_j(x)$ 恒为0，$v_j$ 可以取任意值。这样就保证了 $L(x,u,v)$ 的最大值为原函数 $f_0(x)$ ，即 $\max_{u,v} L(x,u,v)=f_0(x)$。
对于固定的 x 来说，拉氏函数 $L(x,u,v)$ 为 $u$ 和 v 的仿射函数。
二、对偶问题和对偶函数
1. 拉格朗日对偶函数
由此一来，就把原来的求解带约束条件的原函数转换为了不带约束条件的拉格朗日函数。求解 $\min_x f_0(x)$ 就等价于求解 $\min_x\max_{u,v}L(x,u,v)$。但是该式子并不容易求解，所以引入了对偶问题。 $\min_x\max_{u,v}L(x,u,v)$ 和原问题等价，也被称作原问题；$\max_{u,v}\min_xL(x,u,v)$ 被称作原问题的对偶问题，从形式上看原问题和对偶问题只是互换了一下最大最小的位置。而对偶问题中的 $\min_x L(x,u,v)$ 就是拉格朗日对偶函数（注意不是对偶问题），拉格朗日对偶函数就是拉格朗日函数关于 x 取最小值，即：
$$
g(u,v)=\inf_{x\in D}L(x,u,v)=\inf_{x\in D}[f_0(x)+\sum_{i=1}^mu_if_i(x)+\sum_{j=1}^pv_jh_j(x)]
$$
其中 $\inf_{x\in D}$ 表示函数逐点对 x 求下确界，也就是对任意的 $u$ 和 v 求出一个使得 $L(x,u,v)$ 最小的 x 。当拉氏函数没有下确界时，定义下确界为 $-\infty$，即 $g(u,v)=-\infty$； D 是可行域。拉格朗日对偶函数是一个凹函数，也就是说它存在一个唯一的极大值点。
2. 拉氏对偶函数为凹函数证明
先来感性的看一下这个问题，因为是拉氏函数是关于 u 和 v 的仿射函数，所以可以用下面两张示意图表示对 x 逐点取最小值的结果：
上图是随便画的多个仿射函数（直线是最简单的仿射函数），对其逐点取最小值得到下图：
可以发现结果是一个凹函数。
下面再来理性的推导一下，为了叙述方便，记 $\gamma=(u,v)$，则拉格朗日对偶函数为：
$$
g(\gamma)=\min{L(x_1,\gamma),L(x_2,\gamma),…,L(x_n,\gamma)}
$$
即针对变量 x 所有可能的取值求最小值。
要证明拉格朗日对偶函数 $g(\gamma)$ 是凹函数，即证明：
$$
g(\theta\gamma_1+(1-\theta)\gamma_2)\geq\theta g(\gamma_1)+(1-\theta)g(\gamma_2)
$$
证：
$$
g(\theta\gamma_1+(1-\theta)\gamma_2)
$$
根据拉氏对偶函数的定义，有
$$
=\min{L(x_1,\theta\gamma_1+(1-\theta)\gamma_2),L(x_2,\theta\gamma_1+(1-\theta)\gamma_2),…,L(x_n,\theta\gamma_1+(1-\theta)\gamma_2)}
$$
由于 $L(x,\gamma)$ 是关于 $\gamma$ 的仿射函数，而仿射函数是凹函数（当然同样也是凸函数），有
$$
\geq\min{\theta L(x_1,\gamma_1)+(1-\theta)L(x_1,\gamma_2),\theta L(x_1,\gamma_1)+(1-\theta)L(x_2,\gamma_2),…,\theta L(x_n,\gamma_1)+(1-\theta)L(x_n,\gamma_2)}
$$
上式中带参数 $\theta$ 的项都不小于下式中的第一项，上式中带参数 $1-\theta$ 的项都不小于下式中的第二项，故
$$
\geq\theta\min{L(x_1,\gamma_1),L(x_2,\gamma_1),…,L(x_n,\gamma_1)}+(1-\theta)\min{L(x_1,\gamma_2),L(x_2,\gamma_2),…,L(x_n,\gamma_2)}
$$
根据凹函数的定义，有
$$
=\theta g(\gamma_1)+(1-\theta)g(\gamma_2)
$$
故拉氏对偶函数为凹函数。
3. 仿射函数和凸函数的关系
凸集 ：若集合 C 内任意两个不同点的 线段 仍在集合 C 内，则称集合 C 为凸集。
如果一个函数是凸函数，则该函数的图像上方区域一定是凸集，反之亦然。
仿射集 ：若通过集合 C 中任意两个不同点的 直线 仍在集合 C 内，则称集合 C 为仿射集。
n 维空间的仿射集为 n-1 维超平面，比如二维空间的直线，三维空间的平面都是仿射集。
由以上定义可知，如果一个集合是仿射集，那么它也一定是凸集。
仿射函数 ：最高次数为1的多项式函数。常数项为零的仿射函数称为线性函数。
三、原问题与对偶问题的关系
1. 原问题与对偶问题的关系
因为 $\min_x f_0(x)=\min_x\max_{u,v}L(x,u,v)\geq\max_{u,v}\min_xL(x,u,v)=max_{u,v}g(u,v)$，所以可以用拉格朗日对偶的最大值去逼近原函数的最小值。下面来证明一下上面式子的正确性：
因为任何函数都不大于其对某个变量求最大值，故：
$$
f(x,y)\leq\max_x f(x,y)
$$
上式两边对 y 求最小值得：
$$
\min_yf(x,y)\leq\min_y\max_x f(x,y)
$$
上式中不等式的前面是一个关于 x 的函数，不妨记为 G(x)，不等式后面是一个定值，不妨记为 A，所以说 $G(x)\leq A$，所以 G(x) 的最大值也不大于 A：
$$
\max_x\min_yf(x,y)\leq\min_y\max_x f(x,y)
$$
得证。
2. 弱对偶和强对偶
我们用 $p^{*}$ 表示原问题的最优解，即 $p^*=\min_xf_0(x)$；用 $d^$ 表示拉氏对偶函数的最优解，即 $d^\=\max_{u,v}g(u,v)$。并定义原问题的最优解与拉氏对偶问题的最优解之间的差值为 对偶间隙（dual gap），即 $p^*-d^*$。
前面我们已经证明了原问题的最优解大于等于对偶问题的最优解，即$p^*\geq d^*$，这个性质被称作 弱对偶性 ，也可以表示为对偶间隙大于等于 0，即 $p^*-d^*\geq 0$。即使当 $p^*$ 和 $d^*$ 无限时，弱对偶性仍然成立。如果原问题无下界，则对偶问题也无下界；如果对偶问题无上界，则原问题也无上界，即原问题不可行。
如果原问题的最优解和拉氏对偶问题的最优解相等，也就是对偶间隙为 0，则 强对偶性 成立。
四、约束准则
强对偶性成立的条件一般被称为 约束准则。下面主要讲解两个约束准则—— KKT 条件 和 Slater 条件。
1. KKT 条件
之前证明了我们可以用拉格朗日对偶的最大值去逼近原函数的最小值的思路是正确的，但是什么时候两者的最大值和最小值相等呢？
首先假设函数 $f_0(x),…,f_m(x),h_1(x),…,h_p(x)$ 都可微，但并不假设这些函数为凸函数，则拉氏对偶函数：
$$
g(u^*,v^*)=\inf_x[f_0(x)+\sum_{i=1}^mu_i^*f_i(x)+\sum_{j=1}^pv_j^*h_j(x)]
$$
因为一个函数的下确界（最小值）不大于函数本身，带入最优解 $x^*$ 后仍如此，故：
$$
\leq f_0(x^*)+\sum_{i=1}^mu_i^*f_i(x^*)+\sum_{j=1}^pv_j^*h_j(x^*)
$$
又因为后两项的最大值为 0，故：
$$
\leq f_0(x^*)
$$
上面三式中，$u^*$、$v^*$ 和 $x^*$ 分别是拉格朗日对偶函数和原函数的最优解。所以说要想让拉格朗日对偶函数的最大值和原函数最小值相等，需要让上面三式中的小于等于号全部取等号。
因为拉格朗日函数在 $x^*$ 处取得极小值，因此拉氏函数在 $x^*$ 处的导数为 0 。所以第一个 $\leq$ 取等号的条件是拉氏函数对 $x^*$ 的偏导为 0，即：
$$
\nabla f_0(x^*)+\sum_{i=1}^mu_i^*\nabla f_i(x)+\sum_{j=1}^pv_j^*\nabla h_j(x)=0\quad\quad\quad\quad 条件 (1)
$$
第二个 $\leq$ 取等号的条件是 $\sum_{i=1}^mu_i^*f_i(x^*)$ 和 $\sum_{j=1}^pv_j^*h_j(x^*)$ 全部为 0，前面说了，后者恒等于 0，而前者为 0 的条件是：
$$
\sum_{i=1}^mu_i^*f_i(x^*)=0
$$
但是因为在可行域内，以上求和项的每一项都是非正的，因此以上条件等价于：
$$
u_i^*f_i(x^*)=0\quad\quad\quad\quad\quad\quad\quad条件(2)
$$
以上 2 个约束条件，再加上优化问题自身的三个约束条件就得到了著名的 KKT 条件，和 KMP 算法的名称类似，所谓的 KKT 条件的命名其实是三位科学家名字的英文首字母的组合，KKT 条件即：
$$
f_i(x^*)\leq0,\quad i=1,…,m
$$
$$
h_i(x^*)=0,\quad i=1,…,p
$$
$$
u_i^*\geq0,\quad i=1,…,m
$$
$$
\nabla f_0(x^*)+\sum_{i=1}^mu_i^*\nabla f_i(x)+\sum_{j=1}^pv_j^*\nabla h_j(x)=0
$$
$$
u_i^*f_i(x^*)=0
$$
KKT 条件中的条件 (2) $u_i^*f_i(x^*)=0$ 也被称为 互补松弛性，我们可以将互补松弛条件等价地改写为：
$$
u_i^*>0\Rightarrow f_i(x^*)=0
$$
或者：
$$
f_i(x^*)<0\Rightarrow u_i^*=0
$$
这是因为在可行域内有 $u_i^*\geq 0$ 并且 $f_i(x^*)\leq 0$。
2. Slater 条件
文章开始讲述的是一般的优化问题，而凸优化问题在以上形式的基础上多了几个限制条件：1. $f_i(x)$ 为凸函数（$i=0,1,…,m$） 2. $h_j(x)$ 为仿射函数（$j=1,2,…,p$）。一般情况下强对偶性不成立，但如果原问题是凸优化问题，则强对偶性通常（但不总是）成立。将一般的优化问题转化为凸优化问题的好处是凸优化只有一个极小值点，也就是说凸优化问题的局部最优解即全局最优解。
如果原始问题为凸优化问题，并且存在一点 x 使得所有的不等式约束都小于 0，即：
$$
f_i(x)<0,\quad i=1,…,m
$$
则强对偶性成立。
上述条件就是所谓的 Slater 条件，而满足上述条件的点被称为 严格可行，这是因为不等式约束严格成立。上述表达即 Slater 定理，即当 Slater 条件成立且原问题是凸优化问题时，强对偶性成立。
当不等式约束函数 $f_i(x)$ 中有一些函数是仿射函数时，Slater 条件可以进一步改进。我们假设前 k 个不等式约束函数为仿射函数，则强对偶性成立的条件（即改进后的 Slater 条件）为：存在一点 x 使得前 k 个不等式约束函数小于等于 0，而其他不等式约束函数小于 0，即
$$
f_i(x)\leq 0,\quad i=1,…,k
$$
$$
f_i(x)<0,\quad i=k+1,…,m
$$
换句话说，仿射函数不等式不需要严格成立。
五、一阶原对偶方法
一阶原对偶方法应该就是利用一阶导数来求解最优解的方法，常见的有增广拉格朗日算法和交替方向乘子法两种。这段话的表述我不是特别确定是否完全正确。
1. ALM
增广拉格朗日乘子法（Augmented Lagrange Method），是用于解决等式约束条件下的优化问题。相对于朴素拉格朗日，它增加对偶上升法的鲁棒性和放松函数f的强凸约束，使得转换后的问题能够更容易求解，不至于因条件数变大不好求。
形式：在朴素的拉格朗日函数的基础上加一个惩罚项 $\frac{\rho}{2}\cdot||\varphi(x)||_2^2$，即对于只带等式约束的凸优化问题
$$
\min_x f(x)
$$
$$
s.t.\quad\varphi(x)=0
$$
其中 f(x) 为凸函数，其增广拉格朗日函数为：
$$
L(x,\lambda)=f(x)+\lambda\cdot\varphi(x)+\frac{\rho}{2}\cdot||\varphi(x)||_2^2
$$
其中 $\rho>0$ 为惩罚因子。
更新迭代
- 假设 $\lambda^k$ 为当前 k 轮迭代的对偶问题最优解
- 求解 $x^{k+1}$：$x^{k+1}=\arg\min_xL(x,\lambda^k)$，其中 $L(x,\lambda)$ 定义如上式
- 梯度上升法更新 $\lambda$：$\lambda^{k+1}=\lambda^k+\alpha\cdot\frac{\partial L(x,\lambda)}{\partial\lambda}|_{x=x^{k+1},\lambda=\lambda^k}$
对于带有不等式约束的凸优化问题，可以先将其转换为带等式约束的优化问题，再进行求解，即带有不等式约束的凸优化问题为：
$$
\min_x f(x)
$$
$$
s.t.\quad\varphi(x)\geq0
$$
其等价形式为：
$$
\min_x f(x)
$$
$$
s.t.\quad\varphi(x)-v=0
$$
$$
v\geq0
$$
带有约束的增广拉格朗日函数为：
$$
L(x,\lambda)=f(x)+\lambda\cdot(\varphi(x)-v)+\frac{\rho}{2}\cdot||\varphi(x)-v||_2^2
$$
$$
s.t.\quad v\geq0
$$
算法迭代更新步骤为：
固定 $\lambda$，更新 x, v：
$$
(x,v)=\arg\min_{x,v}L_t(x,\lambda)
$$$$
=\arg\min_{x,v}f(x)+\lambda\cdot(\varphi(x)-v)+\frac{\rho}{2}\cdot||\varphi(x)-v||_2^2
$$$$
s.t.\quad v\geq02.
$$- 更新 $\lambda$：
$$
{\lambda*}_i=\lambda_i-\rho\cdot(\varphi(x)-v)
$$
- 更新 $\lambda$：
2. ADMM
交替方向乘子算法（Alternating Direction Method of Multipliers）：将对偶上升法的可分解性和乘子法的上界收敛属性融合在一起的算法。
所谓可分解性就是指待求解的凸优化问题中的函数和限制条件都可以分为多块，下面我们以最简单的形式为例——可分为两块的凸优化问题：
$$
p*=\min_{x,z} f(x)+g(z)
$$
$$
s.t.\quad Ax+Bz=c
$$
其中 $x\in R^n$，$z\in R^m$，$A\in R^{p\times n}$，$B\in R^{p\times m}$，$c\in R^p$，函数 $f:R^n\rightarrow R$，$g:R^m\rightarrow R$ 都是凸函数。
该凸优化问题的增广拉格朗日函数为：
$$
L_\rho(x,z,y)=f(x)+g(z)+y^T\cdot(Ax+Bz-c)+(\frac{\rho}{2})\cdot||Ax+Bz-c||2^2
$$
然后对增广拉格朗日函数 $L(x,z,y)$ 使用对偶上升法求解：
$$
(x^{k+1},z^{k+1}):=\arg\min{x,z}L_\rho(x,z,y^k)
$$
$$
y^{k+1}:=y^k+\rho\cdot(Ax^{k+1}+Bz^{k+1}-c)
$$
对偶上升法的本质就是原始变量的迭代方向取拉格朗日函数对原始变量的次微分，对偶变量的迭代方向取拉格朗日函数对对偶变量的次微分（$\frac{\partial L_\rho}{\partial y}$）。
可以注意到，增广拉格朗日问题更新是求对两个原始变量联合最小化，即变量 x, z 一起更新，而 ADMM（交替方向的乘子法） 是在原来的基础改成变量 x, z 单独交替更新，即
$$
x^{k+1}:=\arg\min_xL_\rho(x,z^k,y^k)
$$
$$
z^{k+1}:=\arg\min_zL_\rho(x^{k+1},z,y^k)
$$
$$
y^{k+1}:=y^k+\rho\cdot(Ax^{k+1}+Bz^{k+1}-c)
$$
ADMM 算法更新还有一种等价的方式，首先我们定义残差（residual）为 $r^k:=Ax^k+Bz^k-c$，并定义缩放的对偶变量（scaled dual variable）为 $u^k:=(\frac{1}{\rho})y^k$，则有
$$
(y^k)^Tr^k+(\frac{\rho}{2})\cdot||r^k||_2^2=(\frac{\rho}{2})\cdot||r^k+(\frac{1}{\rho})y^k||_2^2-(\frac{1}{2\rho})\cdot||y^k||_2^2
$$
$$
=(\frac{\rho}{2})\cdot||r^k+u^k||_2^2-(\frac{\rho}{2})\cdot||u^k||_2^2
$$
所以，我们可以将 ADMM 算法的更新方式改写为：
$$
x^{k+1}:=\arg\min_x{f(x)+(\frac{\rho}{2})\cdot||Ax+Bz^k-c+u^k||_2^2}
$$
$$
z^{k+1}:=\arg\min_z{g(z)+(\frac{\rho}{2})\cdot||Ax^{k+1}+Bz-c+u^k||_2^2}
$$
$$
u^{k+1}:=u^k+Ax^{k+1}+Bz^{k+1}-c
$$
这种形式的 ADMM 算法比前一种更为简洁，我们一般把前一种形式称为 ADMM 的非缩放（unscaled）形式，而这种是缩放（scaled）形式。
3. ADMM 的收敛性
假设1：函数 f, g 为凸函数，并且是 closed 和 proper 的。
假设2：（非增广）拉格朗日函数 $L_0$ 至少有一个鞍点（saddle point）。
上述假设1保证了 $\arg\min_x L_\rho(x,z^k,y^k)$ 和 $\arg\min_z L_\rho(x^{k+1},z,y^k)$ 的解是一定存在的；假设2保证了强对偶性成立，即原问题的最优值等于对偶问题的最优值。基于这两个假设，可以得到
- 残差收敛：当 $k\rightarrow\infty$ 时，有 $r^k\rightarrow0$，也就是说最终的解是可行的。
- 目标函数值收敛：当 $k\rightarrow\infty$ 时，有 $f(x^k)+g(z^k)\rightarrow p*$，也就是说最终的目标函数值是最优的。
- 对偶变量收敛：当 $k\rightarrow\infty$ 时，有 $y^k\rightarrow y*$，也就是说最终对偶变量的值收敛于某个对偶变量的最优解。
值得注意的是，原变量 $x^k,z^k$ 不一定会收敛到一个最优解 $x,z$。
- 本文作者： 俎志昂
- 本文链接： zuzhiang.cn/2019/11/27/primal-dual/
- 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！