大规模线性规划的增广拉格朗日算法

In the big data era, large-scale linear programming problems arise from various real applications in high-dimensional statistical analysis, financial engineering and risk management, transportation, and artificial intelligence. Classic algorithms such as the simplex method and interior point algorithms cannot handle these large-scale problems with complex data structures. To cope with this challenge, in this project, we propose to solve the large-scale linear programming problems via the augmented Lagrangian framework. Based on the special features of linear programming and using convex analysis and nonsmooth analysis, we propose to modify the original augmented Lagrangian method to obtain easy-to-solve convex piecewise quadratic programming subproblems. Special second-order algorithms will be designed to obtain high accuracy solutions of the subproblems efficiently. For theoretical guarantees, we will also conduct comprehensive convergence analyses for the proposed algorithms. Meanwhile, the inherent structures of the large-scale problems and the optimal solutions will be carefully explored and exploited to significantly reduce the computational costs. Moreover, we will provide a serious implementation of the proposed algorithms and conduct extensive numerical experiments to demonstrate their high efficiency and robustness.

大数据时代，越来越多的大规模线性规划问题从高维统计分析、金融工程与风险管理、航空铁路城市交通运输与人工智能的各类应用中产生。经典算法如单纯形法与内点法已经无法应对由这些数据结构复杂且规模巨大的线性规划问题带来的挑战。为应对这一挑战，本项目将基于增广拉格朗日型算法框架设计并实现高效稳定的算法求解大规模线性规划问题。通过利用凸分析与非光滑分析等理论分析工具，根据线性规划问题的特点，申请人将改进原始增广拉格朗日算法得到易于求解的分片凸二次规划子问题，并为这些子问题设计二阶方法以期快速获得这些子问题的高精度近似最优解。申请人也将对所设计的算法进行全面的收敛性分析为其效率提供理论保证。同时，本项目将深度挖掘并高效利用大规模线性规划问题及其最优解的内蕴特殊结构从数值实践的角度来显著节省计算工作量。另外，本项目还会开发并实现高效稳定的求解软件包并通过大量的数值算例验证其数值效果。

本项目关注为大规模线性规划问题的增广拉格朗日算法。经典的算法如单纯形法及内点法无法有效处理结构复杂且规模巨大的线性规划问题。为应对这一挑战，本项目设计了新型增广拉格朗日型算法。根据线性规划问题的特点，本项目通过利用凸分析与非光滑分析等理论分析工具，改进原始增广拉格朗日算法得到了易于求解的子问题，并利用半光滑牛顿算法高效求解了这些子问题。本项目对所设计的算法进行了全面的收敛性分析，得到了完整的收敛理论结果。同时，本项目还深度挖掘并高效利用大规模线性规划问题及其最优解的内蕴特殊结构从数值实践的角度来显著提供算法效率。本项目所开发的高效稳定求解软件包在大量数值算例上比现有商业软件有明显优势。另外，本项目仔细研究了增广拉格朗日算法在矩阵优化问题上的收敛性质；并研究了增广拉格朗日算法与交替方向乘子算法的关系，并特别的为低秩马氏转移矩阵恢复问题设计了高效算法且得到了统计意义下的最优恢复界；同时利用半光滑牛顿算法和动态规划算法分别求解了有序加权L1范数球的投影问题及保序回归问题。