ADMM算法matlab实现

Basis pursuit解滑困决基信胡念本方法的，例做隐子：

Generate problem data

rand('seed', 0)

randn('seed', 0)

n = 30

m = 10

A = randn(m,n)

x = sprandn(n, 1, 0.1*n)

b = A*x

xtrue = x

Solve problem

[x history] = basis_pursuit(A, b, 1.0, 1.0)

首先从拉格朗日缓卜说起，拉扮哪橡格朗日函数是将条件合并入目标函数的一种方法，增广拉格朗日函数是在拉格朗日的基础上添加了一个二次惩罚项，ALM主要是针对一个变量的增广拉格朗日算法，ADMM则是针对两个变量，迭代更新，将对偶上升法厅旁和乘子法的上界收敛性合二为一的算法。

基追踪（basis pursuit）算法是一种用来求解未知参量L1范数最小化的等式约束问题的算法。

基追踪是通常在信号处理中使用的一种对已知系数稀疏化的手段。将优化问题中的L0范数转化为L1范数的求解就是基追踪的基本思想。

比如我原先有一个优化问题：

min ||x||_0（就是L0范数的最小值）subject to y=Ax。

这个||x||_0，就是表示x中有多少个非零元素；那么我们要求min ||x||_0，就是想知道含有最多0元素的那个解x是什么。

但是呢，L0范数有非凸性，不怎么好求解，这时我们就转而求解L1范数的优化问题。

那么，基追踪算法就是磨备转而求解

min||x||_1（就是L1范数的最小值）subject to||y-Ax||_2=0（2范数）

这个||x||_1，就是x的绝对值；那么我们要求min||x||_1，就是求绝对值最小的那个解x是什么。

更通俗一点来讲，比如我要求一个线性方程组

Ax=b

x就是我们要求的未知量。这个A矩阵不是个方阵，是个欠定矩阵，那么就导致这个线性方程组会有若干组解瞎升毁。那么我们到底要哪组解好呢？

如果在一般情况下，可以直接用最小二乘法来获得一组最小二乘解，就是x=(A'A)^(-1)A'b。但是我们现在利用基追踪，就是想要来获得一组含0元素最多的解。

那么我们为什么希望我们获得的解里面0元素越多越好呢？这就要谈到“稀疏化”了。所谓稀疏化，就是希望我获得的这个解放眼望去全是0，非0元素稀稀疏疏的。这样在大样本或者高维数的情况下，计算速度不会太慢，也不会太笑桐占计算机的内存。当然，所谓稀疏解是有一定精度误差的，想要提高计算速度，必然会损失一点精度，这是不可避免的。

可以参考：Stephen Byod 的<Distributed Optimization and Statistical Learning via the ADMM>41页

---