大规模可分离0-1整数规划的ADMM算法及在港口安全监测系统中的应用

Large-scale separable 0-1 integer programming plays a key role in many fields such as economy, management, and engineering. For such structured optimization problems, designing fast and efficient splitting algorithms is one of the hottest topics in the field of optimization. As one of the classic splitting algorithms, the alternating direction method of multipliers (ADMM) has been successfully used to solve large-scale separable convex optimization problems. However, drawbacks still present, especially for integer programming. The aim of this proposal is to investigate ADMM methods for large-scale separable 0-1 integer programming and their applications. Firstly, we design ADMM algorithms for separable 0-1 integer programming such that the original problem can be transformed into convex optimization sub-problems and a quadratic 0-1 integer optimization sub-problem which can be solved alternatively. Then, the convergence of the proposed algorithms and properties of solutions are analyzed. After that, the new ADMM algorithms are applied to port security surveillance system, where the associated sub-problems can be efficiently solved based on the structure and implication of the problem. Moreover, efficient and robust numerical algorithms are tailored for such practical problems. This research has great scientific significance and practical value for the reason that the investigation not only enriches the relevant theories of ADMM algorithms, but also provides new insights and methods for the solution of port security monitoring system.

大规模可分离0-1整数规划在经济、管理、工程等领域中都有着极其广泛的应用。针对此结构化问题，设计快速有效的分裂算法是当前优化领域的重要研究课题之一。作为经典的分裂算法之一，交替方向乘子法(ADMM)用于求解大规模可分离0-1整数规划，存在很多问题亟待解决。本项目旨在研究求解大规模可分离0-1整数规划问题的ADMM算法，并将其应用于求解实际问题。首先，设计求解可分离0-1整数规划的ADMM算法，将原问题转化为凸规划子问题和简单的0-1整数规划子问题进行交替迭代求解，并分析算法的收敛性及解的性质。其次，将新的ADMM算法应用到港口安全监测系统问题，根据实际问题的结构和含义，设计高效的子问题求解算法,为这样的实际问题定制实用算法。该项目的研究成果既丰富了ADMM算法的相关理论，又为港口安全监测系统求解提供新的思路和方法，具有重要的科学意义和实用价值。

交替方向乘子法(ADMM)因具有将高维问题分解成多个低维易求解子问题的优势而成为求解经济、管理、工程等领域中大规模问题的经典有效分裂算法之一。本项目专注于大规模问题的ADMM算法设计及在港口、机场安全等实际问题中的应用。本项目的主要研究成果为：(1)港口、机场安全问题的模型及其ADMM算法设计。针对港口安全监测系统和国内机场网络安全预算分配问题分别建立了双层0-1整数规划模型，并根据这些模型特性设计了ADMM求解下层或上层大规模0-1整合规划的松弛广义割平面算法。新算法具有良好的数值效果。此方面的成果为高效求解港口、机场安全问题提供了新方法。(2)大规模线性等式约束可分离问题的ADMM加速算法设计。针对大规模具有线性等式约束的两块可分离优化问题，在黄金比率邻近ADMM算法基础上扩大其凸组合因子的取值范围，提出一种扩展黄金比率邻近ADMM算法，并且分析了该算法的收敛性及收敛速度。(3)大规模张量补全和矩阵补全、恢复的ADMM加速算法设计。将非单调技术、惯性加速技巧应用到ADMM算法中，分别提出了求解大规模矩阵补全及恢复问题的快速ADMM算法。此外，在经典的ADMM算法基础上，随机选取一个子问题求解，提出一种新的求解大规模低秩张量补全的ADMM加速算法。这些算法的收敛性得以证明，并将这些算法应用数据和图像修复的实例中，都有良好的数值表现。此方面的成果为求解图像处理、信号数据分析、医学中等相关数据处理的实际问题提供了一种新的研究工具。

内容获取失败，请点击重试