凸优化学习（3）——对偶方法、KKT条件、ADMM

🍅 写在前面
👨‍🎓 博主介绍：大家好，这里是hyk写算法了吗，一枚致力于学习算法和人工智能领域的小菜鸟。
🔎个人主页：主页链接（欢迎各位大佬光临指导）
⭐️近期专栏：机器学习与深度学习
LeetCode算法实例
张量分解

凸优化系列知识，详见下方链接：

凸优化学习(1)——什么是凸优化、凸集、凸函数
凸优化学习（2）——梯度类方法求解(gradient descent)
凸优化学习（3）——对偶方法、KKT条件、ADMM
本系列文章主要参考：卡耐基梅隆凸优化系列课程

综述

对偶方法在优化问题中非常重要，实际上就是实质相同但从不同角度提出不同提法的一对问题。有时候原问题 (Primal Problem) 不太好解，但是对偶问题 (Dual Problem) 却很好解，我们就可以通过求解对偶问题来迂回地解答原问题。其中对偶方法又分为强对偶定理和弱对偶定理。弱对偶定理只能确定出原问题的上下界。强对偶定理指的是，在满足某下条件的情况下，可以通过求出对偶问题的解推断出原问题的解。

强弱对偶需要满足的条件

弱对偶：不论原问题是否为凸问题均成立，没有需要满足的特别条件。
强对偶：满足强对偶的条件有很多，这里只介绍常用的几种。
1、Convex+Slater（强对偶的充分条件）
（1）原问题必须为一个凸问题，凸问题的定义在第一节已经讲过，大家可以回顾查询一下。
（2）Slater条件，对于一个凸优化问题，该条件描述如下：
$\begin{array}{l} {\min _x}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} f(x)\\ s.{\kern 1pt} {\kern 1pt} t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {g_i}(x) \le 0,i = 1...,m\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {h_j}(x) = 0,j = 1...,r\\ \end{array}$
对于以上式子，存在可行解x，使得 ${g_i}(x) <0$ 恒成立，并且满足第二个条件
${h_j}(x) = 0$ 。那么称该问题满足Slater条件，并且强对偶也成立。
2、KKT条件
KKT条件的形式如下：

需要指出，KKT条件在问题凹凸性不同性质也有所不同。KKT条件对于凸问题是一个充分必要条件，对于非凸问题则是一个必要条件，无法作为一个充分条件来用。

线性规划对偶

对于形如下方的线性规划问题：
$\begin{array}{l} {\min _x}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {c^T}x\\ s.{\kern 1pt} {\kern 1pt} t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} Ax = b\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} Gx \le h \end{array}$
其对偶问题形式为：

$\begin{array}{l} {\min _{u.v}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} - {b^T}u - {h^T}v\\ s.{\kern 1pt} {\kern 1pt} t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} - {A^T}u - {G^T}v = c\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} v \ge 0 \end{array}$
对于LP问题，其对偶性的特性就是只要原问题存在，那么强对偶条件1就一定成立，因此强对偶也成立。

拉格朗日对偶

对于形如下方的凸问题：
$\begin{array}{l} {\min _x}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} f(x)\\ s.{\kern 1pt} {\kern 1pt} t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {g_i}(x) \le 0,i = 1...,m\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {h_j}(x) = 0,j = 1...,r\\ \end{array}$
则其增广拉格朗日函数为：

$\sum\limits_{i = 1}^m {{u_i}{g_i}(x)} + \sum\limits_{j = 1}^r {{v_j}{h_j}(x)({u_i} \ge 0)}$
原问题拉格朗日对偶形式为：
$\inf (L(x,u,v))$
这里的inf指的是求函数的上界。这里有一个重要性质，任何函数的拉格朗日对偶函数都是凹函数，大家有兴趣可以自己证明一下，比较简单，证明过程如下。
在这里插入图片描述
为什么要求出这个拉格朗日对偶函数呢？它和原函数的关系如下：

$\forall u \ge 0{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \inf (L(x,u,v)) \le f(x)$

证明起来也很容易，因为u不小于0，g(x)小于等于0，相乘小于0。h(x)又等于0。加上f(x)肯定小于等于f(x)。
所以原问题求f(x)的最小值可转变为求解以下式子：
$\min {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \inf (L(x,u,v))$

使用拉格朗日对偶法求解问题的好处有：
1、参数约束减少了很多，只需要u大于等于0
2、拉格朗日对偶函数一定是一个凹函数，则很多凸优化问题的手段都能用上。

ADMM

ADMM (Alternating Direction Method of Multipliers) 是解决带约束的凸优化问题的一种迭代解法，当初提出这个算法最主要的目的是为了在分布式环境 (Hadoop, MPI 等) 中迭代求解这个问题。
ADMM要解决问题的形式如下：
$\begin{array}{l} {\min _x} = {f_1}({x_1}) + {f_2}({x_2})\\ s.t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {A_1}{x_1} + {A_2}{X_2} = b \end{array}$
则ADMM的迭代公式为：
$\begin{array}{l} {x_1}^{(k)} = \arg {\min _{x1}}{f_1}({x_1}) + \frac{\rho }{2}{\left\| {{A_1}{X_1} + {A_2}{X_2}^{(k - 1)} - b + {w^{(k - 1)}}} \right\|_2}^2\\ {x_2}^{(k)} = \arg {\min _{x2}}{f_2}({x_2}) + \frac{\rho }{2}{\left\| {{A_1}{X_1}^{(k - 1)} + {A_2}{X_2} - b + {w^{(k - 1)}}} \right\|_2}^2\\ {w^{(k)}} = {w^{(k - 1)}} + {A_1}{x_1}^{(k)} + {A_2}{X_2}^{(k)} - b\\ \\ \end{array}$
其中ρ是事先选定的参数，可以选择定值和定值，和前一节讲过的学习率性质差不多。