结构张量优化问题的理论与算法研究

Tensor optimization and computation is a new field of applied mathematics and computational mathematics. In recent two years, structured tensor optimization is one of the main topic in the new field. The project has two main purposes. First, we study theory and algorithm for tensor complementarity problems and tensor absolute equations. For some special structured tensors such as P-tensor and B-tensor, we establish nonsmooth and smooth Newton-type method for solving the corresponding tensor complementarity problems, discuss the nonsingularity of Jacobian matrix and feasibility and convergence analysis; We establish sufficient conditions for existence of solutions to tensor absolute value equations. Second, we compute the minimal eigenvalue of structured tensor with positive semi-definite property. For identifying the existence of solution to tensor complementarity or tensor absolute value equations, it needs to know the structure of the tensor. Using nonlinear optimization methods, we establish efficient algorithms for computing the minimal eigenvalue of symmetric tensor. Using sum-of-squares polynomial and sum-of-squares tensor decomposition, we propose polynomial-time algorithms for computing the minimal eigenvalue of structured tensor with positive semi-definite property.

张量优化和计算是应用数学和计算数学的一个新兴领域，结构张量优化是近两年该领域的主要研究课题之一。本项目着眼于两方面的研究：一是张量互补问题和张量绝对值方程的理论与算法，针对如P-张量、B-张量等这样的特殊结构张量，设计求解相应张量互补问题的可行的非光滑或光滑牛顿法，讨论相应的Jacobian阵的非奇异性条件和算法的可行性和收敛性；研究张量绝对值方程解存在的条件和算法。二是具有半正定性质的结构张量的最小特征值计算，判断一个张量互补问题或张量绝对值方程解的存在性，有时需要知道相应张量的结构。利用非线性优化方法，建立有效的计算对称张量最小特征值的算法；利用多项式平方和优化技巧和平方和张量分解，设计半正定性结构张量最小特征值计算的多项式时间算法。

张量优化和计算是应用数学和计算数学的一个新兴领域，结构张量优化是该领域的研究热点。本项目研究结构张量优化问题的理论与算法：一是研究了张量互补问题的算法及特殊结构下的收敛性分析，主要是证明了对角张量互补问题解的存在性，并给出了一般张量互补问题解存在的充要条件，设计了求解张量互补问题的整数规划算法、单调张量互补问题的线性收敛的ADMM算法、张量互补问题的光滑半光滑牛顿算法，给出了保证牛顿步可行的条件，这些结果非富了张量互补问题的算法研究；二是首次研究了张量绝对值问题的解存在理论和算法，证明了强M-张量绝对值方程当右端项大于零有唯一正解，给出了超线性收敛的LM，开启了张量绝对值方程的研究；三是研究了张量特征值互补问题，通过分析其结构，设计了在同一框架下求解非负张量的H-或Z-特征值和相应的特征向量，并且研究了具有半正定性质的结构张量的最小特征值计算，给出了H张量的判定算法；四是理论上得到了超路的拉普拉斯张量和无符号拉普拉斯张量的所有特征值并给出了计算，这些结果丰富了张量谱理论和超图谱理论；五是研究了张量互补问题在多人非合作博弈中的应用，建立了有解的等价张量互补模型并给出了半光滑牛顿法，研究了带有不确定因素的随机张量互补问题，引入了严格半正定张量，找到好的稳健的确定性模型，引入了严格半正定张量，分析了模型解集的有界性。这些结构张量优化理论与算法的研究结果，为用张量表示大数据进而进行大数据的研究提供了理论与应用研究基础，具有重要的理论科学意义和实用价值。