目的
分析与测试带动量的LGD方法的搜索效率与算法特性。
算法分析
LGD算法的核心是步长随机的梯度下降法，其中步长取值符合莱维分布。这样做带来的好处主要有两个：
- 因为步长的最大取值为无限大，因此理论上算法具有全局收敛性。给定足够的搜索次数，算法一定会发现全局最优解；
- 搜索过程顺带对解空间的形态（起伏）进行了探索，因此可利用搜索路径的统计信息给出解的不确定度。 但也有一个缺点：由于在地球物理反演中一般会采用正则化的方法改善反演问题的奇异性，因此一些解空间的凹性质并不突出，这使得LGD在大多数迭代步骤中下降量不足。为了增加LGD的下降效率，同时保留其优点。考虑到Adam这类的最优化方法具有良好的下降效率和一定的全局最优性。因此计划在LGD算法中引入类似的动量概念，提升迭代效率。
下面是带有动量的LGD算法的简单分析：
// 这里我们考虑一个二维最优化问题
// 首先计算归一化的迭代方向（这使得对动量和梯度模的直接统计没有了意义）
// 迭代方向乘步长得到迭代矢量（这是我们真正想记录的量，它直接决定了迭代路径）
direct_mod = sqrt(g2[0]*g2[0] + g2[1]*g2[1]);
g2[0] = levy_length*g2[0]/direct_mod;
g2[1] = levy_length*g2[1]/direct_mod;
// 计算修正系数
mt *= beta_m;
vt *= beta_v;
// 利用指数平均对动量与梯度模进行估计（有偏的）
m[0] = (beta_m*m[0] + (1.0 - beta_m)*g2[0]);
m[1] = (beta_m*m[1] + (1.0 - beta_m)*g2[1]);
v[0] = (beta_v*v[0] + (1.0 - beta_v)*g2[0]*g2[0]);
v[1] = (beta_v*v[1] + (1.0 - beta_v)*g2[1]*g2[1]);
// 对动量与梯度模进行校正
mhat[0] = m[0]/(1.0 - mt);
mhat[1] = m[1]/(1.0 - mt);
vhat[0] = v[0]/(1.0 - vt);
vhat[1] = v[1]/(1.0 - vt);
// 利用动量与梯度模进行迭代（此处不再需要乘以步长了）
x2[0] = x2[0] - mhat[0]/(sqrt(vhat[0]) + 1e-8);
x2[1] = x2[1] - mhat[1]/(sqrt(vhat[1]) + 1e-8);
模型试验
对比二维非凸问题的搜索过程（见下图，其中白色为LGD_Momentum的搜索路径，黑色为LGD搜索路径，红色为Adam算法的搜索路径），在实验过程中，两种LGD算法每次迭代的步长取值都是一样的，Adam算法的步长为LGD搜索步长的平均值，LGD算法的搜索次数为1000次。对比下图可见：
- Adam算法的搜索范围很小，直接陷入了局部极小值；
- LGD算法的搜索范围最大，路径总体呈放射状，搜索效率受到了一定的影响；
- LGD_Momentum算法的搜索范围较小一些，全局收敛性较LGD更弱，但更集中于极值附近，搜索的效率整体更高。
问题
- 怎样更直观地对比LGD与LGD_Momentum的求解效率？
- LGD_Momentum在地球物理反演中是否更优？