Max-plus代数上的super本征问题

The eigenproblem is of key importance in max-plus algebra, and the problem has extensive application background. Subeigenproblem and supereigenproblem are the extension of eigenproblem, and the supereigenproblem is still an open problem today. This project studies the supereigenproblem from the following three aspects: (1) The problem of solving the system of inequalities A⊗X≥X, which is equivalent to supereigenproblem, is discussed, and an effective algorithm with lower time complexity is proposed based on the existing algorithms to find a set of generators and a basis for the solution space of the system, and a new algorithm is proposed based on solving two-sided linear system. (2) Discuss the structure of supereigenspace and the properties of supereigenvectors, and find all proper supereigenvectors, and then fully characterize the supereigenspace. (3) The supereigenproblem for some special matrices is discussed, and an algorithm is designed, and the algorithm complexity in general and special cases is analyzed and compared. The aim of solving supereigenproblem is to promote the further study on eigenproblem and provide a base for solving two-sided linear system.

本征问题是max-plus代数中的重要研究内容，具有广泛的应用背景。Sub本征问题及super本征问题是本征问题的延伸与推广，其中super本征问题至今仍是开问题。本项目拟从三个方面展开对super本征问题的研究：（1）将super本征问题等价地转化为不等式组A⊗X≥X的求解，结合已有算法设计出时间复杂度更低的求解不等式组解空间的生成集和基的有效算法，并以双边线性方程组的求解为基础提出计算不等式组的新算法；（2）深入探讨super本征向量空间的结构及真super本征向量的性质，找到矩阵的所有真super本征向量，进而实现super本征向量空间的完备刻画；（3）讨论特殊矩阵的super本征问题，提出求解算法，分析并比较一般情形与特殊情形的算法复杂度。Super本征问题的解决不但能推动本征问题的深入研究，同时也能为max-plus代数上双边线性方程组及不等式组的求解奠定基础。

Super本征问题作为max-plus代数中本征问题的延伸与推广，具有深远的理论意义与广泛的应用背景。本项目主要研究super本征问题的求解。我们首先将super本征问题等价地转化为不等式组A⊗X≥X的求解，通过舍掉大量非极值生成元改进已有的求解不等式组A⊗X≥X解空间生成集的算法，提出更高效的求解算法；同时基于tropical double description method提出一种新的方法用以求解不等式组A⊗X≥X解空间的scaled基。在刻画不等式组解空间的基的过程中，极值解的判定是关键步骤。为此，我们给出了判断任意解向量是否为极值解的判定定理及算法。最后，基于mean-payoff game与双边不等式组的可解性的密切联系，我们将tropical最优化问题等价地转化为tropical代数(也即max-plus代数)中含参数的mean-payoff game，建立了max-plus代数中的双边不等式组的可解性问题与最优化问题的相互转化关系，并提出了判断不等式组A⊗X≥X是否存在有限解或者部分分量有限的解的判定方法。同时，在求解一类无约束条件的最优化问题完备解的过程中，稀疏矩阵所对应的不等式组A⊗X≥X(即稀疏矩阵的super本征问题)的解集得到完备刻画。

内容获取失败，请点击重试