一类大规模实对称锥规划算法

As an important question used in engineering applications and optimization theories, the large-scale symmetric cone program has attached more and more attention. Since the interior point method which is used to solve the small or medium scale positive semidefinite program does not suit for the large-scale program, some new approaches have been raised recently, which improve the number of constraints of program to million, but the improvement of dimension of solvable program is not obvious, which is because the cost of the eigenvalue decomposition in these approaches is expensive when the dimension of program is large. For improving the dimension of the solvable program which is raised in real life, we will present a new method which bases on the algorithm of the box constraint semidefinite program, which avoid using the expensive eigenvalue decomposition. Combining this method and the existed algorithms of the large-scale program, we study the large-scale box constraint symmetric cone program firstly, and study the large-scale linear and nonlinear symmetric cone programs later, and get a class of algorithms of the large-scale symmetric cone program finally. Afterwards, we study the convergence and convergence speed of these algorithms, and apply them to solve the large-scale engineering problems.

大规模实对称锥规划问题作为一种在工程应用及优化理论中都十分重要的问题已被广泛研究。由于求解中小规模实对称锥规划问题的内点法不适用于大规模情况，近年来已有一些新方法被提出，大大提升了可求解问题的约束个数，现已能达到十万级别，但是可求解问题维数的增长却并不明显，这是由于算法中的全特征值分解在大维数时耗费巨大。为了提升可求解规划问题的维数，使其适用于实际应用所提出的大维数规划问题，在本项目中，我们提出一种基于盒式约束半定规划算法的新思路。盒式约束半定规划算法可以避免进行昂贵的全特征值分解，适用于大维数规划。结合这种算法和已有的大规模规划算法，我们从以盒式约束半定规划为特例的大规模盒式约束实对称锥规划问题入手，依次研究大规模线性和非线性实对称锥规划问题，得到一类新的算法，研究这些算法的收敛性，收敛速度等理论结果，并应用其求解工程中所产生的大规模大维数问题，为工程应用和优化理论提供一种新的研究工具。

本项目致力于提出能解决大规模对称锥规划问题的新算法和理论，丰富了对称锥规划的研究内容，并且将对称锥规划应用于数学的其他领域，解决了正定张量中的一些问题。本项目从研究最简单的线性盒式约束对称锥规划入手，建立起一套极为有效的方法和理论，给出了线性盒式约束对称锥规划和带有一个线性约束线性二次锥规划的显式结果，并提出了非线性对称锥规划的序列线性化方法，以及线性对称锥规划的一种全新的算法，算法经数值实验验证后显示对大规模问题计算效果良好。本项目还将对称锥规划用来研究空间对称张量的正定性判定问题。通过非负多项式理论，本项目建立起利用半定规划判定空间对称张量正定性的算法，从而扩大了对称锥规划的应用。此外，本项目了还继续研究了一种具有特殊结构的正定张量Sup-MO tensor，它是molor矩阵的推广，最终到了此类张量的正定性和一些其他性质。