|||
交替方向乘子法(ADMM)是一种求解具有可分离的凸优化问题的重要方法,由于处理速度快,收敛性能好,ADMM算法在统计学习、机器学习等领域有着广泛应用。ADMM算法一般用于解决如下的凸优化问题:
$$\begin{aligned}\min f(x)+g(x)\\ s.t. Ax+By=c \end{aligned} $$
其中,$x\in R^n$为目标函数$f(x)$的优化变量,$y\in R^m$为目标函数$g(x)$的优化变量,$A\in R^{p\times n}$,$B\in R^{p\times m}$,$c\in R^p$。 函数$f$和$g$是凸函数。
它的增广拉格朗日函数如下:
$$L_p(x,y,\lambda)=f(x)+g(y)+\lambda^T(Ax+By-c)+(\rho/2)\|Ax+By-c\|_2^2, \rho>0$$
其中,$\lambda$称为拉格朗日乘子,$\rho$是惩罚参数且$\rho>0$。此时,用ADMM算法进行求解,则过程如下:
$$\begin{split} x^{k+1}&:=\arg\min L_p(x,y,\lambda)\\ x^{k+1}&:=argmin L_p(x,y,\lambda) \\ \lambda&:=\lambda^k+\rho(Ax^{k+1}+By^{k+1}-c)\end{split} $$
第一步简化:
通过公式$2a^Tb+\|b\|^2_2=\|a+b\|^2_2-\|a\|^2_2$替换增广拉格朗日函数中的线性项$\lambda^T(Ax+By-c)$和二次项$\rho\|Ax+By-c\|_2^2$
$\lambda^T(Ax+By-c)+\rho\|Ax+By-c\|_2^2=\rho/2\|AX+By-c+\rho/\lambda\|_2^2-\rho/2\|\lambda/\rho\|_2^2$
于是ADMM求解过程可以简化为如下形式:
$$\begin{split} x^{k+1}&:=argmin (f(x)+\rho/2\|Ax+By^k-c+\lambda^k/\rho\|^2_2\\ y^{k+1}&:=argmin (g(y)+\rho/2\|Ax^{k+1}+By-c+\lambda^k/\rho\|^2_2\\ \lambda&:=\lambda^k+\rho(Ax^{k+1}+By^{k+1}-c)\end{split}$$
第二步简化:
令缩放对偶变量为$u=(1/\rho)\lambda$,于是ADMM求解过程再次简化为如下形式:
$$\begin{split} x^{k+1}&:=argmin (f(x)+\rho/2\|Ax+By^k-c+\lambda^k/\rho\|^2_2\\ y^{k+1}&:=argmin (g(y)+\rho/2\|Ax^{k+1}+By-c+\lambda^k/\rho\|^2_2 \\ \lambda&:=\lambda^k+\rho(Ax^{k+1}+By^{k+1}-c)\end{split}$$
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-21 00:19
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社