求解双线性鞍点问题的自由步长原始对偶算法

来源：计算数学杂志2025年第4期北京时间：

作者：许龙, 常小凯

单位：兰州理工大学理学院, 兰州 730050

摘要：原始对偶算法 (PDA) 通过全分裂的方式同时求解原始问题和对偶问题, 是解决双线性鞍点问题经典且有效的方法. 然而已有PDA的步长依赖于线性算子的谱范数或通过线搜索进行估计, 依赖谱范数的步长通常过于保守, 而线搜索往往需要额外计算邻近算子或者线性变换. 为此, 文章通过拉格朗日函数添加邻近项和求解矩阵逆问题，提出了一种具有可分离预设的原始对偶算法. 该算法具有自由的步长且只需进行一次矩阵分解, 预设矩阵逆问题的计算量较小. 最后, 建立了函数值残差和约束违反度的 \mathcal{O}(1/N) 遍历收敛率, 求解LASSO和矩阵博弈问题的数值实验验证了所设计算法的有效性.

关键词：双线性鞍点问题,原始对偶算法,可分离预设策略,自由步长

基金资助：国家自然科学基金(12571320, 12161053), 甘肃省杰出青年基金(22JR5RA223)和甘肃省研究生“创新之星”项目(2025CXZX-583)资助.