上海交大团队提出改进版ABIP算法，大幅提升线性与锥优化问题求解效率

上海交通大学安泰经济与管理学院数据与商务智能系的邓琪副教授、葛冬冬教授和叶荫宇访问讲席教授，以及他们的合作者 Feng Qing、Gao Wenzhi、Jiang Bo、Jiang Yuntian、Liu Jingsong、Liu Tianhao、Xue Chenyu 和 Zhang Chuwen，于2025年3月在国际顶级期刊《INFORMS Journal on Computing》上发表了一篇重要论文：“An Enhanced Alternating Direction Method of Multipliers-Based Interior Point Method for Linear and Conic Optimization”。这篇论文已经被引用33次。 论文的核心内容是提出了一种改进的基于交替方向乘子法的内点算法（ABIP）。传统内点法（IPM）依靠计算量极大的牛顿步求解，而ABIP则通过ADMM近似求解带有障碍惩罚项的子问题，从而有效提升了在大规模线性优化中的性能。然而，传统的ABIP对条件数和反精度依然敏感。为此，研究团队在这篇论文中对ABIP进行了多项增强： 扩展与复杂度分析：将ABIP扩展到一般线性和锥优化问题，并提供了详细的迭代复杂度分析。这使得ABIP不仅适用于简单的线性优化，还能够处理更为复杂的锥优化问题。 实现策略设计：借鉴先前的研究成果，为ABIP设计了多种实现策略，从而显著提升了求解线性优化问题时的算法效率。这些策略包括改进的参数选择方法、更有效的子问题求解技术和增强的收敛性控制机制。 实证优势验证：研究团队在合成数据和真实数据集上进行了大量数值实验，验证了改进策略的有效性。具体而言，在Netlib数据库选取的105个线性优化实例上，改进版ABIP的运行时间几何平均值减少了5.8倍。此外，该算法在支持向量机和PageRank等结构化问题上表现出色。 虽然改进版ABIP在许多基准测试中与商业求解器相比仍有差距，尤其是在需要高精度解的情况下，但研究团队认为，这并不影响它的应用价值。改进版ABIP可以作为经典求解器的一个有益补充，适用于需要快速求解的大规模优化场景。 邓琪副教授长期专注于数学规划和机器学习领域的研究。她的教育背景包括美国佛罗里达大学和上海交通大学的计算机博士学位，此前在上海财经大学信息管理与工程学院担任教师。葛冬冬教授是上海交通大学智能计算研究院院长和安泰经济与管理学院数据与商务智能系特聘教授，博士毕业于斯坦福大学，目前主持国家自然科学基金的多个重要项目，研究领域涵盖超大规模数学优化的理论、算法和应用。叶荫宇教授不仅是安泰经济与管理学院的访问讲席教授，还是香港中文大学（深圳）数据科学学院的特聘教授，他曾任斯坦福大学的李国鼎讲席教授，研究领域涉及优化、数据科学、算法设计、市场均衡和运筹管理科学等。 业内专家对这一研究成果给予了高度评价，认为它在提高现有优化算法效率的同时，也为大规模优化问题提供了一个新的视角和工具。上海交通大学安泰经济与管理学院在数据科学和优化算法领域的持续研究和突破，进一步巩固了其在国际学术界的领先地位。