完全正张量规划的数值方法

As we all know, many NP-hard problems can be equivalently reformulated to completely positive (CP) tensor optimization problems. Thus, completely positive tensor optimization has become an important and frontier research topic in optimization with significant theoretical value and practical application background. This project mainly focuses on the following problems:..1. The completely positive binary tensors will be characterized. Some new necessary and sufficient conditions for completely positive binary tensor will be studied. These results will be used to design an algorithm to determine whether a binary tensor is completely positive or not. When it is, the algorithm will also compute its CP-rank and a CP-rank decomposition. ..2.The completely positive tensor programming will be considered, which is a linear optimization problem with the cone of CP tensors and some linear constraints. It will be reformulated as a linear programming over the cone of moments, and then a hierarchy of semidefinite relaxations will be constructed for solving its global optimal solution and a CP decomposition. The convergence of the algorithm will also be studied...3.The best CP tensor approximation problem is to approximate a given symmetric tensor by a CP tensor under linear constraints. This problem will be transformed to a linear programming over the cone of moments and the second order cone. An effective semidefinite algorithm will also be presented for solving it. If the problem is feasible, a CP decomposition of the best CP approximation tenor will also be obtained.

众所周知，很多NP-难问题都可等价转化为完全正张量优化问题。关于完全正张量理论与应用的研究已经成为近十年来最优化领域的前沿研究方向。对完全正张量理论结果的研究，构造有效求解完全正张量优化及相关问题的数值算法，无论是在理论上，还是实际应用中都有着重要意义。本项目主要研究如下几方面的课题：1.充分利用二元张量自身的特点，将二元完全正张量的判定及CP秩分解问题转化为单变量矩问题，并通过求解相关的半定规划问题得到二元完全正张量的CP秩分解。2.对于一般的完全正张量锥规划问题，克服该类问题中完全正张量锥约束的固有困难，构造半正定松弛等级算法求其全局最优解。同时分析算法的渐近收敛性，以及有限收敛性。3.考虑最佳完全正张量逼近问题，将其转化为矩变量锥和二阶锥约束的线性规划问题。构造半定松弛等级算法求其全局最优解，并给出所得最佳完全正逼近张量的完全正分解。

关于完全正张量理论与应用的研究已经成为近十五年来最优化领域的前沿研究方向。如何构造有效求解完全正张量优化及相关问题的数值算法，无论是在理论上，还是实际应用中都有着重要意义。本项目主要在如下几方面取得了一系列重要结果：1.对于一般的完全正张量锥规划问题，克服该类问题中完全正张量锥约束的固有困难，构造半正定松弛等级算法求其全局最优解，并证明了算法的渐近收敛性和有限收敛性。同时，对于最佳完全正张量逼近问题，将其等价转化为矩变量锥和二阶锥约束的线性规划问题。构造半定松弛等级算法求其全局最优解，并给出所得最佳完全正逼近张量的完全正分解。2.引入完全正张量CP核值的概念，证明了任意完全正张量的CP核值不小于其迹。还证明了，完全正张量的CP核值不小于其任意主子张量的CP核值，并给出了其值相等的一个充要条件。同时，对于带有最小CP核值的完全正张量补全问题，将其等价转化为一个带有矩变量锥约束的线性优化问题，并提出一个半定松弛算法对其进行求解。3.充分利用二元张量自身的特点，将二元完全正张量的判定及CP秩分解问题转化为单变量矩问题，并通过求解相关的半定规划问题得到二元完全正张量的CP秩分解。4.引入了完全正可分(CPS)矩阵的概念，证明了CPS矩阵必为完全正矩阵，且CPS矩阵锥为真锥。同时，对于CPS矩阵的判定问题，将其等价转化为一个截断矩问题，并提出一个有效的半定松弛等级算法对其进行求解。5.引入了Hermitian完全正(HCP)矩阵的概念，证明了HCP矩阵锥及其对偶锥均为真锥，并对HCP矩阵判定问题，提出了一个有效的半定松弛算法。6.通过将张量最大关联问题的一阶最优性条件增加到其约束中，将原问题等价转化为另一个多项式优化问题。对转化后的优化问题提出更有效的半定松弛算法，并证明了算法有限步收敛到该问题的全局最优解。本项目所取得的上述成果极大丰富了完全正张量优化的理论内容，并扩大了其应用范围。