随机化Hessian近似拟牛顿法在无约束优化问题中的应用 题目描述：考虑无约束优化问题 \(\min_ {x \in \mathbb{R}^n} f(x)\)，其中 \(f\) 是二阶连续可微函数。拟牛顿法（如BFGS、DFP等）通过构造矩阵 \(B_ k\) 近似 Hessian 矩阵 \(\nabla^2 f(x_ k)\)，利用拟牛顿方程 \(B_ {k+1} s_ k = y_ k\)（其中 \(s_ k = x_ {k+1} - x_ k\)， \(y_ k = \nabla f(x_ {k+1}) - \nabla f(x_ k)\)）更新近似。然而，当问题维度 \(n\) 很大时，存储和操作 \(n \times n\) 矩阵 \(B_ k\) 成本高。随机化Hessian近似拟牛顿法通过随机采样梯度信息，构建低秩或结构化的Hessian近似，在保证收敛性的同时降低计算和存储开销。本题目讲解其基本思想、随机化构造方法、算法流程及理论性质。 解题过程： 问题背景与核心思想 在无约束优化中，牛顿法使用精确Hessian矩阵进行迭代：\(x_ {k+1} = x_ k - [ \nabla^2 f(x_ k)]^{-1} \nabla f(x_ k)\)，具有二阶收敛速度，但计算Hessian及其逆的成本为 \(O(n^3)\)，且需存储 \(O(n^2)\) 元素。 拟牛顿法用近似矩阵 \(B_ k\) 代替 \(\nabla^2 f(x_ k)\)，满足拟牛顿方程 \(B_ {k+1} s_ k = y_ k\)，更新通常为秩1或秩2修正（如BFGS），迭代为 \(x_ {k+1} = x_ k - \alpha_ k B_ k^{-1} \nabla f(x_ k)\)，其中 \(\alpha_ k\) 是步长。 当 \(n\) 很大时，即使拟牛顿法也需存储稠密矩阵 \(B_ k\)（\(O(n^2)\) 内存），且求解线性系统 \(B_ k p_ k = -\nabla f(x_ k)\) 需 \(O(n^3)\) 计算（尽管可通过递归更新逆矩阵降至 \(O(n^2)\)）。 随机化Hessian近似拟牛顿法核心：利用随机采样技术，仅通过少量随机向量与Hessian的乘积信息，构造结构化近似（如低秩矩阵、对角加低秩矩阵等），使存储降为 \(O(n)\) 或 \(O(n \log n)\)，并利用Sherman-Morrison-Woodbury公式快速求解线性系统。 随机化Hessian近似构造方法 设当前迭代点为 \(x_ k\)，定义随机向量集合 \(\{\omega_ i\}_ {i=1}^m\)，其中 \(\omega_ i \in \mathbb{R}^n\) 独立同分布（如标准正态分布），\(m \ll n\) 为采样数。 通过有限差分或自动微分计算Hessian-向量积：\(h_ i = \nabla^2 f(x_ k) \omega_ i\)。实际操作中，\(\nabla^2 f(x_ k) \omega_ i\) 可通过梯度的一阶差分近似：\(\nabla^2 f(x_ k) \omega_ i \approx \frac{\nabla f(x_ k + \epsilon \omega_ i) - \nabla f(x_ k)}{\epsilon}\)，其中 \(\epsilon\) 为小步长。 构建随机化近似矩阵 \(B_ k\)。常用形式包括： a. 低秩近似：\(B_ k = \delta_ k I + \sum_ {i=1}^m c_ i h_ i \omega_ i^T\)，其中 \(c_ i\) 为缩放系数，\(\delta_ k > 0\) 为修正项保证正定性。 b. 对角加低秩：\(B_ k = \text{diag}(d_ k) + \sum_ {i=1}^m a_ i (h_ i - \text{diag}(d_ k) \omega_ i) \omega_ i^T\)，其中 \(d_ k \in \mathbb{R}^n\) 通过对角元素估计得到。 数学上，这等价于用随机投影近似Hessian矩阵的外积形式，基于Johnson-Lindenstrauss引理，能以高概率保持矩阵的谱性质。 算法具体步骤 初始化：选择初始点 \(x_ 0\)，近似矩阵 \(B_ 0 = \delta_ 0 I\)（标量矩阵），采样数 \(m\)，容差 \(\tau > 0\)，最大迭代次数 \(K\)。 对于 \(k=0,1,\dots,K\)： 计算梯度 \(g_ k = \nabla f(x_ k)\)，若 \(\|g_ k\| < \tau\)，则停止。 求解搜索方向 \(p_ k\)：求解线性系统 \(B_ k p_ k = -g_ k\)。由于 \(B_ k\) 具有特殊结构（如对角加低秩），可利用Sherman-Morrison-Woodbury公式在 \(O(m^2 n + m^3)\) 时间内求解，避免显式构造 \(B_ k\) 的逆。 线搜索：沿 \(p_ k\) 执行Armijo或Wolfe条件线搜索得到步长 \(\alpha_ k\)，更新 \(x_ {k+1} = x_ k + \alpha_ k p_ k\)。 计算梯度差：\(y_ k = \nabla f(x_ {k+1}) - \nabla f(x_ k)\)，位移 \(s_ k = x_ {k+1} - x_ k\)。 随机采样更新：生成新的随机向量 \(\{\omega_ i^{(k)}\} {i=1}^m\)，计算Hessian-向量积 \(h_ i^{(k)} = \nabla^2 f(x {k+1}) \omega_ i^{(k)}\)（或差分近似）。 更新近似矩阵：构造新的 \(B_ {k+1}\) 满足拟牛顿方程 \(B_ {k+1} s_ k = y_ k\)，并融入随机采样信息。常见更新策略为： 将 \(B_ {k+1}\) 设为对角加低秩矩阵，其参数通过最小化 \(\|B_ {k+1} - B_ k\| F\) 等范数，并约束 \(B {k+1} s_ k = y_ k\) 和 \(B_ {k+1} \omega_ i^{(k)} = h_ i^{(k)}\) 得到。 或采用随机化BFGS变体：\(B_ {k+1} = B_ k + \frac{y_ k y_ k^T}{y_ k^T s_ k} - \frac{B_ k s_ k s_ k^T B_ k}{s_ k^T B_ k s_ k} + E_ k\)，其中 \(E_ k\) 为基于随机采样的低秩修正项，以保持近似精度。 收敛性理论要点 在目标函数 \(f\) 为强凸且 Lipschitz Hessian 连续条件下，随机化拟牛顿法产生的序列 \(\{x_ k\}\) 以概率1收敛到全局极小点。 收敛速度：通常为超线性收敛的随机变体，即 \(\mathbb{E}[ \|x_ {k+1} - x^ \|] \leq \rho_ k \|x_ k - x^ \|\)，其中 \(\rho_ k \to 0\) 随 \(k\) 增加，但比经典拟牛顿法慢，因近似引入随机误差。 关键引理：随机采样数 \(m\) 需满足 \(m = O(\log n)\) 才能以高概率保证近似误差可控，使得算法行为接近确定性拟牛顿法。 数值实现细节 为了避免每轮重新采样，可采用滑动窗口策略，保留部分历史随机向量，减少梯度计算次数。 对于非凸问题，需保证 \(B_ k\) 正定，可通过在构造时添加正则化项 \(\delta I\) 实现。 实际代码中，求解 \(B_ k p_ k = -g_ k\) 可利用矩阵求逆引理：若 \(B_ k = D + U V^T\)，其中 \(D\) 为对角阵，\(U, V \in \mathbb{R}^{n \times m}\)，则 \(B_ k^{-1} = D^{-1} - D^{-1} U (I + V^T D^{-1} U)^{-1} V^T D^{-1}\)，计算仅需 \(O(m^2 n)\)。 应用场景与扩展 适用于大规模机器学习中的经验风险最小化（如逻辑回归、神经网络训练），其中 \(n\) 可达数百万。 可与随机梯度下降结合，在每次迭代中用随机子集估计梯度，进一步减少计算。 扩展至分布式优化，各计算节点本地采样，协同更新全局Hessian近似。