优化问题中的拉格朗日乘子法

之前看的一些传统优化问题,用的基本都是拉格朗日乘子法 (Lagrange Multiplier),但最近遇到一些非平常的优化问题,特此系统整理一下这一块的理论,包括:拉格朗日法的基础理论,不同限制条件下的拉格朗日法,对偶问题,交替方向乘子法 (ADMM) ,具体优化例子。

拉格朗日法的基础理论

1)怎么判断凸函数?
定义:满足 Jensen 不等式, $f(\theta x+(1-\theta)y)\leq \theta f(x)+(1-\theta)f(y)$,或者记为 $E[f(x)]\ge f(E(X))$
判断:对于一元函数 $f(x)$,我们可以通过其二阶导数 $\nabla f(x)$ 的符号来判断。如果函数的二阶导数总是非负,即 $\nabla^2 f(x)\ge0$ ,则 f(x) 是凸函数;对于多元函数 $f(x)$,其 Hessian 矩阵(Hessian 矩阵是由多元函数的二阶导数组成的方阵)为半正定矩阵时,f(X) 是凸函数。
2)怎么判断优化问题为凸优化?
凸优化问题的一般形式

$f$,$g_j$ 为凸函数,$h_i$ 是仿射函数 (带有平移的线性变换 $Ax+b$),一般是最小化损失函数。

不同限制条件下的拉格朗日法

1)无约束
直接梯度为 0,计算结果,一般有解析解;如果没有的话,需要梯度下降法。
2)等式约束
等式约束一般使用拉格朗日乘子法(Lagrange Multiplier)

优化方法,

3)不等式约束
函数有不等约束一般使用 KKT(Karush Kuhn Tucker)条件

最优解满足需要满足以下条件

当不等式约束为大于等于 0 时,变换成标准形式即可。SVM 中的优化过程用到了这里的 KKT 条件,对 $x$ 求偏导,然后带入,将原始问题转换成单变量的优化问题。
4)等式与不等式混合
将一个有 $n$ 个变量与 $k$ 个约束条件的最优化问题转换为一个解有 $n + k$ 个变量的方程组的解的问题

最优解成立的规范性条件,注意这里

对偶问题

对于含有不等式的约束问题,将其转换为对偶问题很有必要

定义增广拉格朗日函数

为了解决这一优化问题,定义

$p^{\ast}$ 表示这个这个目标函数的最优值

看一下我们的新目标函数,先求最大值,再求最小值。以 SVM 为例,这样做之后,我们首先就要面对带有需要求解的参数 $\mathrm{w}$ 和 $b$ 的方程,而 $\alpha_i$ 又是不等式约束,这个求解过程不好做。所以,我们需要使用拉格朗日函数对偶性,将最小和最大的位置交换一下,这样就变成了:

可知 $d^{\ast}\le p^{\ast}$,即对偶问题最优值 $d^{\ast}$ 是原始问题最优值 $p^{\ast}$ 的一个下界,在满足 KKT 条件下,二者是等价的。Slater 定理和 KKT 条件,如果 $f$ 和 $g_i$ 是凸的, $h_i$ 是仿射,假设 $g_i$ 是严格可解的,即 $\exists \ \mathrm{w}$ 使得 $g_i(\mathrm{w})<0\quad \forall i$,则存在 $\mathrm{w}^{\ast}, \alpha^{\ast}, \beta^{\ast}$ 使得 $\mathrm{w}^{\ast}$ 是原问题的解,$\alpha^{\ast}, \beta^{\ast}$ 是对偶问题的解。此外 $p^{\ast} = d^{\ast}=\mathcal{L}(\mathrm{w}^{\ast}, \alpha^{\ast}, \beta^{\ast})$,且 $\mathrm{w}^{\ast}, \alpha^{\ast}, \beta^{\ast}$ 满足 KKT 条件:

满足上述几条约束,就可以用对偶问题替代原始问题,并且对偶问题的解是原问题最优值得最好下界。

拉格朗日法和交替方向乘子法

交替方向乘子法 ADMM

传统解决带约束凸问题时,往往会利用拉格朗日乘子法作转换,将其转化为无约束问题然后进行求解,但传统方法对数据及函数假设较为严格,所以一般情况很难达到收敛,假设要求宽松的又难以做大规模分布式计算,所以为了解决这个问题,Boyd 提出了 ADMM。ADMM 在理论上是综合了对偶上升、对偶分解、增广拉格朗日法。增广拉格朗日 (ALM) 是在拉格朗日函数中增加了关于约束条件的二次项 (或者说在拉格朗日函数上加约束条件的 “L2 正则项” ),目的是增加对偶上升法的鲁棒性和放松函数 $f$ 的强凸约束。先看 ALM 方法的一般形式,对于原始优化问题

其增广拉格朗日函数为

ADMM 针对上述优化问题,通过增加变量,把约束条件转化到原问题中,达到可以函数可分 (separable) 的目的,然后迭代求解时就可以进行分布式并行了。

其中 $g(z)=Ax-b$,这样变换的优势会体现在优化过程中。其迭代过程为

其中 $y^k$ 是拉格朗日乘子,可以对比之前的增广拉格朗日乘子法,ADMM 的核心就是加和拆,通过加变量来让原问题的函数可分,然后拆成并行迭代计算的形式。

拉格朗日法 v.s. 期望最大化 EM 算法

拉格朗日法解决一个多变量优化问题时,需要将原问题拆解成多个子凸优化问题,然后用拉格朗日法去解决,这里多个变量交替优化的方法并不是 EM 算法。EM 算法是为了解决模型中存在隐变量的情况,求期望和期望最大化两步交替迭代。而优化问题中的交替是优化不同的变量。

具体优化例子

1)偏导带有常数项

有约束的情况下偏导中含有常数项的优化问题,比如

其中 $A$ 为协方差矩阵,$\mu$ 为固定向量,其拉格朗日函数偏导为

该类型问题用拉格朗日乘子法暂时无解,这也展示了其有一定局限性。但是将该问题转换成

其增广拉格朗日函数为

然后用 ADMM 法分别优化 $\mathrm{w},\mathrm{z},Y_1,\theta$ 即可。

2)多变量优化 [3]

一种降维方法的损失函数,$Y$ 为 onehot 标签,$E$ 为随机矩阵

令其拉格朗日函数对 $W$ 和 $E$ 的偏导为 0,易得

在对 $W$ 的偏导为 0 计算简化过程中,需要将上述两个结果以及 $G^{\top}G=I$ 带入到原始问题中,可以得到仅含有 $G$ 的凸优化问题。

3)非负矩阵分解 [4]

非负矩阵分解问题中,对于损失函数

优化问题 $\min J\quad \text{s.t.}\ G\ge0$,拉格朗日函数为

其中拉格朗日乘子 $\beta_{ij}$ 约束 $G_{ij}$ 非负。易得其偏导

根据 KKT 条件知最优解满足互补松弛条件

可以得到收敛时 G 的更新公式

4)逐行求偏导 [5]

动态图学习,对于优化问题

优于约束条件中包括了对行和的约束,直接优化 $S$ 较为困难,因此这里逐行求偏导,原问题转换为

上述优化问题等效为以下问题的求解:

其中 $d_i=\alpha \left|f_{i}-f_{j}\right|_{2}^{2}$,可以用 KKT 条件逐行优化。

5)多变量 ADMM 法 [6]

SPDA 是一个迁移学习领域的模型,其优化问题很有趣。其原始优化问题为

其中 $L$ 包括了拉普拉斯正则化以及 MMD 距离约束。转换后的优化问题

表面上增加了优化变量,使得问题变复杂了,但是优化过程更好解了。其增广拉格朗日函数为

交替对 $P,Z,E,Z_1,Z_2,M$ 进行优化,可以得到各个子问题中变量的更新公式,最后是拉格朗日乘子的更新

其过程是按照标准的 ADMM 流程来的。当原始问题较复杂时,利用 ADMM 可分布优化的性质,通过增加变量,把原问题中的项转为约束条件,或者把约束条件转化到原问题中。然后写出其 ALM 函数,然后分别优化其待优化变量以及拉格朗日系数。

参考:
[1] ADMM note
[2] 广义拉格朗日与乘数法,以及ADMM之间有着怎样的关联?
[3] Guo, Chenfeng, and Dongrui Wu. "Discriminative sparse generalized canonical correlation analysis (DSGCCA)." 2019 Chinese Automation Congress (CAC). IEEE, 2019.
[4] Ding, Chris HQ, Tao Li, and Michael I. Jordan. "Convex and semi-nonnegative matrix factorizations." TPAMI 32.1 (2008): 45-55.
[5] Wang, Lichen, Zhengming Ding, and Yun Fu. "Adaptive graph guided embedding for multi-label annotation." IJCAI. 2018.
[6] Xiao, Ting, et al. "Structure preservation and distribution alignment in discriminative transfer subspace learning." Neurocomputing 337 (2019): 218-234.