论文部分内容阅读
0-1多项式优化问题是数学规划中非常重要的一类问题。它在实际中应用广泛。对这类问题的研究无论是对多项式优化理论的发展，还是指导实际应用都有非常重要的意义。目前，已有的方法主要有吴方法、结式方法、SDP半定规划松弛方法、SOS方法、同伦方法和一些全局优化方法等。但是这些方法，只能对较小规模的问题有效。因此我们考虑寻找可以求解中等规模问题的新方法。
首先，对于0-1多项式方程组，我们提出了基于错率统计的启发式算法。由于问题的每个变量非0即1，每个方程只含有一少部分变量；同时，满足的方程中不一定每个变量都正确，但是不满足的方程中的某个变量一定是错误的，所以，考虑通过统计每个变量在不满足的方程中出现的次数，我们称该次数为错次，将其与每个变量在所有方程中出现的次数作比，得到每个变量的错率。往往错率较大的变量的确是错的。另外，我们还结合了一些启发式的策略来提高统计结果的准确度，例如利用一邻域、二邻域中点的信息等。我们给出了三个算法，各有特点。有的适合粗略搜索，有的适合精细搜索，同时还结合了局部枚举策略来提高算法的准确度。通过对多个问题的测试，该方法显示出了它自身的特点，对一些问题有效地找到了真解。
其次，我们考虑通过增加变量将0-1多项式方程组转化为0-1线性规划，然后再用解0-1线性规划的方法来求解。首先介绍了三种已有的转化方法，然后提出借助McCormic不等式组进行转化，最后分析了这几种转化方法新增变量和新增约束的数量，阐述了转化之后的新问题与原问题的关系。对四种转化方法，分别用SCIP软件进行了测试，都可以找到真解。
再者，提出了基于模拟退火和正交法均匀撤点的混合算法。一般的模拟退火方法，在当前点邻域中随机撒点，数值效果不佳。我们考虑了用正交法撒点来保持搜索的均匀性，减少盲目性，扩大搜索范围。对0-1多项式方程组进行了数值实验，从实验结果上看，新方法和一般的模拟退火方法相比优势不是很明显，但这是一种有意义的尝试。
鉴于多项式优化和高阶张量的关系，我们对高阶超对称张量的Z特征值问题进行了研究。本文中，从Z特征值几何意义的角度，将线性特征值问题的子空间投影方法推广到求高阶张量的最大和最小Z特征值以及相应Z特征向量。该方法先将问题投影到二维子空间，然后在二维子空间上求最优解。在一定条件下，我们证明了该方法的收敛性。对高维4阶对角型张量问题进行了测试，对于求最大Z特征值，子空间投影方法比幂方法需要更少的迭代步数；同时，子空间投影方法可以有效地求出最小Z特征值。