这是我在stackoverflow上的第一个帖子，所以如果这不是正确的区域，我道歉。我正在研究最小化l1 -正则化系统。
这个周末是我第一次深入优化，我有一个基本的线性系统Y = X*B, X是一个n × p矩阵，B是一个p × 1的模型系数向量，Y是一个n × 1的输出向量。
我试图找到模型系数，我已经实现了梯度下降和坐标下降算法来最小化L1正则化系统。为了找到我的步长，我使用回溯算法，我通过查看梯度的范数-2来终止算法，并在它"足够接近"零时终止(现在我使用0.001)。
我试图最小化的函数是以下(0.5)*(norm((Y - X*B)，2)^2) + lambda*norm(B,1)。(注:范数(Y,2)是指向量Y的范数-2值)我的X矩阵是150 × 5，不是稀疏的。
如果我将正则化参数设为0，我应该收敛于最小二乘解，我可以验证我的两个算法都能很好很快地做到这一点。
如果我开始增加lambda，我的模型系数都趋向于零，这就是我所期望的，我的算法永远不会终止，因为梯度的norm-2总是正数。例如，lambda为1000将给我10^(-19)范围内的系数，但我的梯度的norm2是~1.5，这是在几千次迭代之后，虽然我的梯度值都收敛到0到1范围内，但我的步长变得非常小(10^(-37)范围)。如果我让算法运行更长的时间，情况不会改善，它似乎被卡住了。
我的梯度和坐标下降算法都收敛于同一点，并且对于终止条件给出相同的norm2(梯度)数。它们对(0)也很适用。如果我使用非常小的lambda(比如0.001)，我会得到收敛，如果lambda为0.1，看起来会收敛，如果我运行一两个小时，lambda再大一点，收敛率就太小了，没用。
我有几个问题，我想可能与这个问题有关。
在计算梯度时，我使用有限差分法(f(x+h) - f(x-h))/(2h))， h为10^(-5)。对h的值有什么想法吗?
另一种想法是，在这些非常小的步长上，它在与最小值几乎正交的方向上来回移动，使得收敛速度如此之慢以至于无用。
我最后的想法是，也许我应该使用不同的终止方法，也许看看收敛速度，如果收敛速度非常慢，那么终止。这是一种常见的终止方式吗?
1-范数不可微。这将导致很多事情的根本问题，特别是你选择的终止测试;梯度会在你的最小值附近急剧变化，并且在一组测量零上不存在。
您真正想要的终止测试将沿着"在子梯度中有一个非常短的向量"的行进行。
在λ |Ax-b| _2^2 + λ ||x||_1的子梯度中找到最短的向量是相当容易的。明智地选择一个容差eps，并执行以下步骤:
-
计算
v = grad(||Ax-b||_2^2). -
如果是
x[i] < -eps，则从v[i]中减去lambda。如果是x[i] > eps，则将lambda添加到v[i]。如果是-eps <= x[i] <= eps，则将[-lambda, lambda]中的数字与v[i]相加，使v[i]最小。
您可以在这里进行终止测试，将v作为梯度。我还建议在选择下一个迭代应该在哪里时使用v的梯度