若干张量特征值互补与相关多项式优化问题理论与算法

Eigenvalue complementarity of tensors is a class of structural problems which involves many theories and relevant problems from a brand-new perspective. It not only has applications in the study of a class of differential inclusions, but also is closely related to some polynomial optimization and covers many mathematical issues such as matrix eigenvalue complementarity and tensor eigenvalue problems. In this project, methods which integrate tensor analysis (e.g. decomposition, spectral theory) and optimization (e.g. duality, relaxation) are adopted. To begin with, a class of standard eigenvalue complementarity of tensors and related homogeneous polynomial optimization will be studied first, then followed by studying on higher-order eigenvalue complementarity of tensors and related multi-homogenous polynomial optimization with higher degree or order: (1) Establish some properties for solutions of eigenvalue complementarity of tensors, which includes existence of solution, structure and estimation of error, etc., and develop the local and global optimality theory for related polynomial optimization, including optimality conditions and approximation analysis, etc. (2) By using appropriate transformation and relaxation,cone eigenvalues and their numbers will be estimated based on transferring original problems to some related polynomial optimization. Some global approximation algorithms such as PTAS for solving related polynomial optimization will be designed, and approximation analysis for algorithms will be proposed. (3) By using idea which integrate alternating direction methods and projection techniques, some efficient algorithms for eigenvalue complementarity of tensors will be presented, related convergence will be established. Moreover, these algorithms will be applied to related models which come from complex networks optimization design.

张量特征值互补是一类内容新、涵盖面宽、理论丰富的结构型问题，它不仅在一类微分包含问题研究中有应用，且与多项式优化密切相关，矩阵特征值互补和张量特征值问题是其特例。将采用张量分析(如分解、谱理论等)与优化方法(如对偶、松弛等)相结合的技术，以张量一次特征值互补和相关齐次多项式优化为切入口，逐步展开对张量高次特征值互补和相关多重齐次多项式优化的研究。内容包括：(1) 建立张量特征值互补问题解的性质(包括存在性和结构理论、误差估计等)和相关多项式优化的局部和全局最优化理论(包括最优性条件、近似分析等)；(2) 利用适当转化和各种松弛方法，在将原问题转化成相应的多项式优化基础上，估计锥特征值及其个数、设计各相关优化模型的全局近似算法(如PTAS算法)并进行近似分析；(3)采用交替方向法和投影技术相结合思路，设计求解张量特征值互补的有效算法、分析收敛性质，并应用于源自复杂网络优化设计问题的相关模型。

张量特征值互补是一类特殊的张量计算问题，它与多项式优化密切相关，矩阵特征值互补和张量特征值问题是其特例。第一，提出了张量高次特征值互补问题的一般模型，该模型是广义张量特征互补问题、矩阵二次特征值互补问题的推广。研究解的存在性定理、对称张量特征值互补的多项式优化等价模型、二阶锥上的高阶张量特征值互补问题和严格半正张量特征值互补问题的Pareto-谱估计等，设计了非对称情形的投影算法、线性化ADMM法，并进行了相关的数值实验。第二，在研究4重齐次多项式优化问题全局最优值估计的基础上，给出了一个求解其全局最优解的PTAS算法，较大改进了现有近似界的结果。第三， 在闭凸锥上，定义了若干结构张量，并讨论了这些结构张量相互间的关系。证明了张量互补问题解的存在性及解集的紧性和解的稳定性等相关拓扑性质。研究了多项式互补问题，证明了当最高次项系数张量为ER-张量时，其解集为非空紧。分析了当系数张量为严格半协正张量时解的下界，从而得到解集的误差界结论。第四，考虑了求解张量方程问题，证明了求解这样的方程等同于求解具有P-函数的非线性方程组，提出了一种牛顿型算法，并证明当系数张量为非奇异M-张量、常数向量为正向量时，算法产生的点列二次收敛于原方程的唯一正解。随机产生的数值算例说明了算法的有效性和稳定性。第五，研究若干可求解特殊优化问题的数值算法、收敛性理论，并用于张量（特征值）互补问题：(1)部分并行分裂算法、(2)缩放梯度投影算法、(3)解分裂可行性问题的CQ算法、（4）原始-对偶预测-校正算法、（5）基于LQP正则化子问题的两步投影法。