ADMM算法求解二次项目标函数+l1正则项问题

问题描述

$$\underset{x}{\min }f(x)+\lambda ||x|{|}_1\cdot \cdot \cdot \cdot \cdot \cdot （1）$$
其中，f(x)为二次项函数，λ＞0，x是$R^n$上的列向量。

分析

由于(1)带l1范数不可导，考虑将(1)转化为以下问题(2)：

$$\begin{gathered} \min f(x)+g(z) \\ x-z=0 \end{gathered}$$
其中，
$$g(z)=\lambda ||z|{|}_1$$
则增广拉格朗日函数为
$$L(x,z,y)=f(x)+g(z)+y^T(x-z)+\frac{n}{2}||x-z|{|}_2^2$$
迭代算法为
$$\begin{gathered} x^{k+1}:=\underset{x}{\mathrm{argmin}}L(x,z^k,y^k) \\ {z}^{k+1}:=\underset{z}{\mathrm{argmin}}L(x^{k+1},z,y^k) \\ {y}^{k+1}:=y^k+n(x^{k+1}-z^{k+1}) \end{gathered}$$

简化

令$r=x-z$，则
$$\begin{gathered} y^T(x-z)+\frac{n}{2}||x-z|{|}_2^2=y^{T}r+\frac{n}{2}||r|{|}_2^2 \\ =\frac{n}{2}||r+\frac{1}{n}y|{|}_2^2-\frac{n}{2}||\frac{1}{n}y|{|}_2^2 \\ =\frac{n}{2}||x-z+u|{|}_2^2-\frac{n}{2}||u|{|}_2^2 \\ (u=\frac{1}{n}y） \end{gathered}$$
迭代算法可转化为
$$\begin{gathered} x^{k+1}:=\underset{x}{\mathrm{argmin}}f(x)+\frac{n}{2}||x-z^k+u^k|{|}_2^2 \\ {z}^{k+1}:=\underset{z}{\mathrm{argmin}}g(z)+\frac{n}{2}||x^{k+1}-z+u^k|{|}_2^2 \\ {u}^{k+1}:=u^k+x^{k+1}-z^{k+1} \end{gathered}$$

问题的求解

1.x-update的求取

对于x-update，由于f(x)是二次项目标函数，不妨假设
$$f(x)=\frac{n}{2}||Ax-b|{|}_2^2$$A为n阶方阵，b是与x同规模的矩阵。
那么x-update的求解即寻求超定线性方程组
$$\begin{gathered} Ax-b=0 \\ x-z^k+u^k=0 \end{gathered}$$的最小二乘解。此外，还可以通过以下方法求取x-update
$$f(x)+\frac{n}{2}||x-z^k+u^k|{|}_2^2=\frac{n}{2}(||Ax-b|{|}_2^2+||x-z^k+u^k|{|}_2^2)$$
对x求导，并令导数为0，有
$$A^{T}Ax-A^{T}b+x-z^k+u^k=(A^{T}A+I)x-(A^{T}b+z^k-u^k)=0$$
即$$（A^{T}A+I)x=A^{T}b+z^k-u^k$$

2.z-update的求取

对于z-update的求取，
$$g(z)+\frac{n}{2}||x^{k+1}-z+u^k|{|}_2^2={\Sigma }_{i=1}^n（\lambda |z_i|+\frac{n}{2}(x^{k+1}-z+u^k{)}^2)$$
对于第i个分量
当$x_i^{k+1}+u_i^k>\frac{\lambda }{n}$时，$z_i^{k+1}=x_i^{k+1}+u_i^k-\frac{\lambda }{n}$；
当$x_i^{k+1}+u_i^k<-\frac{\lambda }{n}$时，$z_i^{k+1}=x_i^{k+1}+u_i^k+\frac{\lambda }{n}$；
其他，$z_i^{k+1}=0.$

3.u-update的求取

$$u^{k+1}=u^k+x^{k+1}-z^{k+1}$$

总结

以上是生活随笔为你收集整理的ADMM算法求解二次项目标函数+l1正则项问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。