协正规划理论与算法研究

Copositive programming (CP) is one of the frontier and the hot issue of conic programming. It not only includes many high computational complexity NP-hard problems, but also is widely used in the real world, such as combinatorial optimization, financial management, optimal control, etc. However, the strong duality theorem for CP does not hold, moreover, there also does not exist polynomial time algorithms for solving CP. This project aims to establish the duality theory and the system of optimal conditions as well as design some fast and efficient algorithms for CP. The main research contents and innovations are as follows: (1) some new algebraic properties and equivalent forms of expression for copositive cone are given, in order to design new approximation methods and efficient algorithms for copositive cone and CP, respectively; (2) based on the ideas of the discretization methods, the new algorithms for CP by using of the equivalence between CP and other programming problems are designed; (3) we establish the systems of duality theory and optimal conditions for CP; (4) we study the new approximation methods for the dual cone of copositive cone, and design new algorithms for solving CP by solving the dual problem of CP, moreover, some new efficient algorithms for solving CP in terms of the ideas of the penalty function methods and alternating direction methods and so on are constructed; (5) the theoretical properties and the convergence speed of the new algorithms are analyzed and proved, and a large number of numerical experiments are performed to verify the effectiveness of the proposed algorithms.

协正规划(CP)是锥规划研究领域的前沿和热点问题之一，在组合优化、金融管理、最优控制等领域有着广泛的应用，且CP还涵盖了很多计算复杂性高的NP-难问题。但CP的强对偶定理不成立，也不存在多项式时间可解算法。本项目以CP为研究对象，旨在建立CP对偶理论和最优性条件体系，设计快速有效求解算法。主要研究内容和创新有：(1)给出协正锥新的代数性质及等价表述形式，设计新的协正锥近似逼近方法，构建求解CP有效算法；(2)利用CP与其他一些规划问题的等价性，以离散化方法等方法思想为基础，设计新的CP求解算法；(3)建立CP及其相关问题对偶理论和最优性条件体系；(4)研究协正锥的对偶锥新的近似方法，设计算法通过求解CP的对偶问题来进一步求解CP，同时以罚函数法、交替方向法等方法设计思想为基础，构建求解CP的新型有效算法；(5)系统分析和证明新算法的理论性质和收敛速度，进行大量的数值实验，验证算法的有效性。

协正规划(CP)是锥规划研究领域的前沿和热点问题之一，在图论与组合优化、供应链管理、最优控制、社会网络等领域有着广泛的应用，且CP还涵盖了很多计算复杂性高的NP-难问题。本项目以CP及其相关问题为主要研究对象，旨在设计有效求解方法和构建问题优化模型。主要研究内容和创新包括：(1) 基于协正矩阵的一种等价表述形式，建立了一类CP问题的等价半无限规划模型，进而设计了一个新的离散化方法来求解该CP问题。理论上该方法或有限步得到原问题的一个可行近似解，或返回该问题不存在可行解。相关结果对构建新的协正矩阵判定方法及CP求解算法具有一定的指导意义。(2) 系统研究了线性约束0-1二次规划问题的全正规划模型特征，并给出了双非负松弛求解方法。理论上证明了其在一定条件下等价于一个紧的半定松弛模型，但数值和对比结果表明双非负松弛的计算性能要优于半定松弛。研究成果对进一步探讨双非负松弛的近似界、全正规划的求解算法具有一定的指导作用。(3) 基于(2)中的基础成果，研究了稠密K-子图问题的全正规划模型特征及其双非负松弛求解方法，结果表明双非负松弛的理论近似界与当前半定松弛的最好界相同，而且计算效果要优于半定松弛。相关成果对解决超图中的K-子图问题，社会/社区网络中的K-子图问题等具有重要的借鉴意义。(4) 针对带有等式与不等式约束的优化问题，设计了以二次规划为主子问题，利用罚函数和线性方程组技术，在较弱的条件下，构建了一个局部超线性收敛的快速有效算法。相关成果对设计求解CP有效算法亦具有重要意义。(5) 研究了乳制品供应链网络设计、收益与成本等相关优化问题。设计了与其匹配的敏捷型供应链网络，构建了产品库存量度量的新函数。在满足产品需求量的前提下，分别建立了供应链总成本最小的混合整数规划模型、总成本与收益能够同时达到最优的双目标混合整数规划模型，进而设计了新的求解方法。相关成果对研究供应链成本与收益、提升顾客满意度、构建最优物流网络等具有潜在的重要指导意义。