混合整数规划的DC等价和DC算法

DC (difference of convex functions) Programming is a special but very important class of nonlinear optimization problems, attracting attention of mathematiciens in recent years with wide range of real-world applications in various fields. Due to the fact that most of nonlinear functions and nonconvex sets can be rewritten via dc functions, many difficult nonlinear optimization problems could be represented as DC programs and solved by specific DC programming algorithms, which are often observed more efficient than standard existing methods as a result. In this project, we will deep study various equivalent dc programming representations of mixed-integer programming problems, so as to solve more efficiently the mixed-integer programming problems via DC programming algorithms. We will discuss from the 0-1 binary variable cases to the general integer variable cases, involving linear or nonlinear objective function and constraints, and finally design some new high-efficient DC programming based algorithms to solve general mixed-integer optimization problems. We are also willing to develop an open source progiciel which could be tesed and used by fellow academics and scientists of applied sciences.

DC规划(凸函数之差)是非线性最优化问题中一类特殊又非常重要的问题，是近年来国际上最优化领域热门的研究方向。因DC函数和DC集(由DC函数构成的非凸集)的普遍存在性，很多困难的非线性最优化问题都可等价的转化为DC规划问题研究和求解，而且往往能得到比传统方法更好的求解效果。该项目将深入地研究混合整数规划的DC规划等价形式，以期通过求解等价DC规划问题来最终求解混合整数规划。我们将从0-1二元变量的情况开始讨论，进而深入地研究一般整数变量的情况；从线性目标函数和约束，到非线性目标函数和约束，最终设计出求解一般线性与非线性混合整数规划的基于DC规划的若干高效的新算法。我们还将开发一套开源代码软件包，以便学术界同行和应用科学界有关专家们测试和使用。

随着人工智能、量子计算和大数据时代的到来，很多核心技术问题实际上需要解决一些困难的最优化问题。而含有连续或离散变量的非线性最优化问题就是普遍存在的核心问题之一（如深度神经网络的训练、火星岩石的识别和分类、量子纠缠态的判定等）。本项目的研究对象主要包含三个方面：混合整数规划问题、多项式规划问题和相关应用问题的研究。主要切入点是：从DC规划的角度研究这些问题的DC等价表示，及相应的DC规划求解算法的设计。本项目的主要研究成果包含“理论”和“应用“两方面。理论方面主要包括：（1）对混合整数规划问题的研究和求解。我们开发了基于DC规划的若干求解算法，深入研究了DC割平面技术并提出了并行DC割平面算法，开发了并行分支定界框架，并研究了基于离散动力系统的若干混合整数规划求解算法。（2）对于非线性规划问题（特别是多项式规划问题）的研究和求解。提出了多项式的平方差（DSOS）和凸平方差（DCSOS）分解理论，并基于DCSOS分解开发了多项式规划的DC求解算法。应用方面主要包括：（1）跨学科相关应用问题的研究，例如，机器学习中自然语言处理问题、高阶资产组合优化、矩阵特征值互补问题、空间-时间深度神经网络模型、激光诱导等离子体光谱分析和量子纠缠态判定等若干实际应用问题的研究。（2）相关最优化软件和科学计算程序包的开发，例如，基于DC规划和并行分支定界算法的混合整数规划求解器、基于DC割平面的混合0-1线性规划求解器、DC规划图形界面集成开发环境DCIDE、自然语言处理工具包NLPTOOL、基于DSOS和DCSOS的多项式分解软件包、求解0-1多项式规划的离散动力系统算法包（Lie和Houbolt等差分格式）、DC规划基础类库（DC函数类、DC模型类和DCA算法类）、POLYLAB多项式矩阵类库以及空间-时间深度学习的模型和代码等。在本项目的资助下，目前见刊论文4篇，在审论文3篇，在研论文9篇，应邀国际大会报告9次和国内外学术报告6次，邀请海内外专家来校学术交流7次，同9位专家开展学术合作，赴美国和加拿大访学三个月，作为组委成员参与组织国际学术大会1次，获得国际大会最佳海报奖1次，开发最优化和科学计算软件16款，其中部分代码以MIT开源软件的形式共享在Github平台上，另有两款软件（“混合整数规划的并行分支定界DC规划求解器”和“DCIDE”）正在申请知识产权。