完全正优化的若干问题研究

Completely positive optimization is a relatively young field in mathematical optimization. It has wide applicaitons in combinatorial optimization, probability and statistics, digital signal processing, and so on. Since checking the membership in the completely positive cone is NP-hard and checking the membership in the copositive cone is co-NP-hard, it is generally difficult to treat the completely positve cone and the copositive cone directly. A standard approach is to approximate them by simpler and more tractable cones. To the best of our knowledge, there is little work on the completely positive optimization. In this project, we will study the following important problems in the completely positive optimziation. Firstly, we will consider the problem of checking interiors of the completely positive cone. If a matrix is an interior of the completely positive cone, a nonnegative decomposition in Dur's form or Dickinson's form will be given for it. Secondly, we will compute the distance between the linear matrix pencil and the completely positive cone, which provides a way to check the feasibility of the dual problem of the copositive programming. Thirdly, we will study the completely positive matrix approximation problem and give a nonnegative decomposition of the approximation matrix. Fourthly, we will study the completely positve tensor and decomposition, the completely positive tensor completion problem as well as the completely positive tensor approximation problem. We will transform the problems to the linear optimization problems with moments. Some semidefinite relaxation algorithms will be presented and the asymptotic convergence and finite convergence of the algorithms will be discussed. Studying the problems above will provide new insights and also computational improvements for completely positive optimizaition.

完全正优化是最优化领域的新兴研究方向，它在组合优化、数理统计、信号处理等领域有着很广泛的应用。完全正优化的研究在国际上还处于起步阶段，关于它的研究成果还比较少。由于完全正矩阵判定的NP-难性，对于完全正矩阵和完全正张量的处理较为复杂，没有直接的方法，所以完全正优化的研究具有相当大的难度和挑战性。本项目将研究以下几个完全正优化问题：完全正矩阵锥内点的判定和表示；线性矩阵束与完全正矩阵锥之间的距离问题；矩阵的完全正逼近；以及完全正张量的判定和非负分解、完全正张量的填充问题和张量的最佳完全正逼近问题。我们将从多项式优化的角度出发，将完全正优化问题转化为矩优化问题，利用序列线性矩阵不等式逼近完全正矩阵锥和完全正张量锥，设计半正定松弛算法，讨论算法的渐进收敛性和有限收敛性。我们的研究将为解决完全正优化问题提供新的视角和方法，为完全正优化在实际领域中的应用提供理论保证。

完全正优化在组合优化、数理统计、信号处理等领域有广泛的应用。完全正矩阵锥的处理没有直接的方法，通常是用一些简单易处理的凸锥来逼近，但这样往往得不到问题的最优解。我们从多项式优化的角度，利用序列线性矩阵不等式逼近完全正矩阵锥，提出的半正定松弛等级算法框架总能够得到问题的全局最优值和最优解。1.我们将矩阵的最佳完全正逼近问题转化为矩变量锥和范数锥约束的线性优化问题，构造了一个半正定松弛等级算法求解。算法在一般性条件下，有限步终止。文章被SIAM J.Matrix Anal.Appl.选为“特推论文”（Featured Article）。2.对于线性矩阵束与完全正矩阵锥之间的距离问题，我们给出了半定松弛算法，分析了算法的收敛性质。同时，给出了完全正矩阵判定的一个新模型。3.我们解决了完全正张量的判定和分解问题，提出的半正定算法能判定一个张量是否为完全正张量，如果不是，给出判定准则，如果是，则给出它的一个完全正分解。在CP-秩和CP-秩分解方面也取得了一些进展：给出了二维完全正张量的充分必要条件；提出了计算其CP-秩和CP-秩分解的半正定松弛算法；并进一步刻画了CP-秩分解唯一的条件。我们还解决了极小核值完全正张量填充问题。4.我们证明了张量特征互补问题的互补特征值的个数有限，且每个互补特征值对应的互补特征向量存在且唯一（除了相差一个常数倍），并提出了计算其全部互补特征对的半正定算法。5.我们还研究了非线性方程组的自适应LM方法，能大幅度降低Jacobi矩阵的计算量和总计算量，给出了非精确LM方法的一般性框架和复杂度。6.此外，我们考虑了Celis-Dennis-Tapia问题和二次约束二次规划问题的子空间性质，并给出了子空间的选取方法，当子空间的维数远远小于原空间的维数时，问题的计算量将大幅度降低。在本项目支持下，出版了专著《非线性方程组数值方法》，在国际学术期刊上发表论文20篇，其中Math.Program.1篇、SIAM J.Matrix Anal.Appl.1篇、J.Sci.Comput.2篇、Math.Oper.Res.1篇、Comput.Optim.Appl.3篇、J.Global Optim.2篇。这些结果丰富了完全正优化理论和非线性方程组理论，为实际领域的完全正优化问题和非线性方程组问题提供了新的方法及其理论保证。