基于非多余矩阵分离的二次指派问题SDP近似算法与应用

Quadratic Assignment Problems (QAPs) are known to be among the most challenging discrete optimization problems. In general, solving a QAP with n≥30 becomes very difficult. QAPs have a wide range of applications in many important areas such as facility location, chip design, image analysis and processing, and communications. It has become a research topic in the field of international optimization in recent years. The development of conic optimization especially semidefinite programming (SDP) and second-order cone programming (SOCP) provides new methods and tools for the study of quadratic assignment problems. This project aims to use cone optimization relaxation techniques and matrix decomposition methods to investigate the quadratic assignment problem and its important generalization problem--nonconvex quadratically constrained quadratic programming, especially based on the SDP relaxation technique of recent development, the approximate algorithm and its implementation for large quadratic assignment problems are investigated. We will study the SDP relaxation algorithms based on non-redundant matrix splitting for the quadratic assignment problems, and study its application in the image analysis and processing of molecular biology. We will investigate SDP relaxation algorithms for the generalized quadratic assignment problem based on non-redundant matrix decomposition. We will also study the tighter SOCP relaxation based on the non-redundant matrix splitting and the tighter nonlinear SDP relaxation based on the exact penalty method for nonconvex quadratically constrained quadratic programming, respectively, and we will propose a bi-section search algorithm to solve the constructed nonlinear SDP relaxation. Finally, we will investigate the tighter SDP and SOCP relaxations and their approximate algorithms based on the matrix splitting for 0-1 quadratic programming with the linear constraints.

二次指派问题是最具挑战性的离散优化问题之一，一般而言，求解n≥30的问题就变得很困难了。这类问题在设施选址、芯片设计、图像分析与处理和通讯等领域有广泛的应用，是近年来国际最优化的一个研究热点，锥优化特别是半定规划和二阶锥规划的发展为二次指派问题研究提供了新的方法和工具。本项目旨在利用锥优化松弛技术和矩阵分解方法研究二次指派问题及其一类重要的推广问题--非凸二次约束二次规划，特别是基于近年来发展的SDP松弛技术，研究大型二次指派问题的近似算法和实现。我们将研究二次指派问题的基于非多余矩阵分解紧SDP松弛算法，并研究其在分子生物学图像分析与处理中的应用；研究广义二次指派问题的基于矩阵分解SDP松弛；研究非凸二次约束二次规划的基于非多余矩阵分解紧SOCP松弛，并研究它基于精确罚方法的非线性SDP松弛及求其解的二分搜索算法；研究线性约束0-1二次规划的基于矩阵分解紧SDP和SOCP松弛和近似算法。

二次指派问题是最具挑战性的离散优化问题之一，一般而言，对n≥30的问题求解就变得很困难。这类问题在设施选址、芯片设计、图像分析与处理和通讯等领域有广泛的应用，是近年来国际最优化的一个研究热点，锥优化特别是半定规划和二阶锥规划的发展为二次指派问题研究提供了新的方法和工具。本项目利用锥优化松弛技术和矩阵分解方法系统和深入地研究了二次指派问题及其一类重要的推广问题——非凸二次约束二次规划的SDP松弛理论与近似算法，并进行算法实现。本项目经过四年的研究，基本实现了项目立项时的研究目标，对项目立项时的研究内容进行了重点研究。本项目主要集中在以下几个研究方向：(1) 二次指派问题的基于非多余矩阵分解的SDP松弛方法研究；(2) 非凸二次约束二次规划的基于非多余矩阵分解的SOCP松弛和基于罚方法的非线性SDP松弛理论与算法研究；(3) 线性约束0-1二次规划的基于矩阵分解的紧SDP和SOCP松弛方法；(4) 带凸二次约束的非凸二次规划的全局算法研究。随着研究的深入，我们在项目的四年研究中还在下列与项目相关的扩展方向进行了研究：(1) 不确定性下的最坏情形线性优化问题的全局算法研究；(2) 金融中带有市场影响的最优去杠杆化问题和带边际风险控制的投资组合选择问题的全局算法研究；(3) 非线性半定规划的增广Lagrangians对偶理论与非线性分离方法研究。.项目取得了一系列重要的研究成果，已发表（录用）了6篇学术论文，其中SCI论文3篇，有2篇论文正在SCI源刊二审之中，另有4篇论文已投稿SCI源刊，包括国际运筹与优化权威期刊Mathematical Programming Computation, INFORMs Journal on Computing, Computational Optimization and Applications, Journal of Global Optimization, Journal of Optimization Theory and Applications。