这是我第一次在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)。(注意：norm(Y,2)表示向量Y的2-范数值)我的X矩阵是150乘5的，并且不是稀疏矩阵。
如果我将正则化参数lambda设为零，我应该会收敛到最小二乘解，我可以验证我的两个算法都能很好地并且相当快地做到这一点。
如果我开始增加lambda，我的模型系数都趋向于零，这是我所期望的，但我的算法从未终止，因为梯度的2-范数始终为正数。例如，lambda为1000时，我的系数会在10^(-19)范围内，但我的梯度的2-范数约为1.5，这是经过几千次迭代后的结果。虽然我的梯度值都收敛到0到1的范围内，但我的步长变得极小（10^(-37)范围）。如果我让算法运行更长时间，情况不会改善，似乎它在某种程度上卡住了。
我的梯度和坐标下降算法都收敛到同一点，并给出相同的2-范数(梯度)数值作为终止条件。它们在lambda为0时也运行得很好。如果我使用一个非常小的lambda（比如0.001），我可以得到收敛，lambda为0.1看起来如果运行一两个小时会收敛，任何更大的lambda收敛速度都小到无用。
我有一些问题，我认为可能与这个问题有关？
在计算梯度时，我使用了有限差分方法（(f(x+h) – f(x-h))/(2h)），其中h为10^(-5)。对这个h值有什么看法吗？
另一个想法是在这些非常小的步骤中，它几乎是沿着与最小值正交的方向来回移动，使得收敛速度慢到无用。
我的最后一个想法是，或许我应该使用不同的终止方法，或许是查看收敛速度，如果收敛速度极慢则终止。这是常见的终止方法吗？
回答：
1-范数不可微分。这将导致许多基本问题，特别是你选择的终止测试；梯度会在你的最小值附近发生剧烈变化，并且在一组测度为零的点上不存在。
你真正想要的终止测试应该是“在次梯度中有一个非常短的向量。”
在||Ax-b||_2^2 + lambda ||x||_1的次梯度中找到最短向量是相当容易的。明智地选择一个容差eps，并执行以下步骤：
-
计算
v = grad(||Ax-b||_2^2). -
如果
x[i] < -eps，则从v[i]中减去lambda。如果x[i] > eps，则向v[i]中添加lambda。如果-eps <= x[i] <= eps，则向v[i]中添加[-lambda, lambda]范围内的数，使v[i]最小化。
你可以在这里进行你的终止测试，将v视为梯度。我还建议在选择下一次迭代的位置时使用v作为梯度。
