多重齐次多项式优化的近似算法及其应用

多重齐次多项式优化有广泛而重要应用，受到普遍重视。我们将采用优化方法(如对偶、松弛、分解等)与张量计算理论相结合的技术，以多重二次多项式优化为切入口，逐步展开对有较高次数或重数但结构有一定特殊性的多重齐次多项式优化研究：(1)建立多重齐次多项式优化的全局最优化理论，包括解的存在性和结构理论、误差界估计与最优性条件等。(2)利用适当转化技术和多重线性、半定松弛，在将多重齐次(二次)多项式优化转成多重线性或多重半定规划基础上，设计求解原问题全局最优解的(近似)算法并分析计算复杂性；针对一些虽形式特殊但应用背景强烈的问题，借助张量计算工具，研究多项式存储问题，建立可求偏大规模问题的快速有效算法。（3）研究系数非负的多重齐次多项式优化与张量特征值（或奇异值）问题，包括更一般的Perron-Frobenius 定理及相关算法与收敛分析。(4)研究多重齐次多项式优化模型与算法在复杂网络通讯设计中应用。

多重齐次多项式优化与张量分析、计算关系密切。第一，研究单位球面约束的高次齐次多项式优化和多重线性多项式优化，在系数张量为对称时，证明了上述两问题的最优值相同。证明了对称张量的最佳对称秩-1逼近和最佳秩-1逼近相同，给出了相应算法。进一步，研究单纯形约束多重二次规划的最优值近似界和近似解，给出了形式简单、计算成本低的最优值下界，给出了近似解的相对近似率，建立了原问题与半定规划的等价关系。第二，针对张量特征值问题，研究张量determinant性质，及张量特征值(或奇异值)与多项式优化的关系，给出若干性质。研究张量的两类特征值互补问题，其中包括解的存在性与拓扑性质、解的个数与值的估计、多项式优化等价形式及相关数值算法。第三，研究若干可求解特殊优化问题的数值算法、理论分析并用于张量特征值互补问题：(1)松弛的投影方法、(2)子问题具有显式解的可执行分裂算法、(3)分布式Douglas-Rachford分裂算法。第四，针对与半定规划、张量正定和协正定判别等关系密切的半无限规划，利用积分“聚积”技术和高效积分计算，设计算法并进行收敛性分析和数值计算。第五，针对一般非光滑约束方程组，设计数值算法、分析收敛性、进行数值试验，并用于求解随机非线性互补问题。