非精确非可行内点法解决非单调线性互补问题的多项式收敛

本文主要探讨了非精确不可行内点算法在解决一类非单调线性互补问题(P-Matrix Linear Complementarity Problems, 简称P-LCP)中的多项式收敛特性。自1984年Karmarkar提出目标尺度化算法以来，内点算法因其高效性和理论价值得到了广泛应用，尤其是在线性规划、凸二次规划和单调线性互补问题领域。然而，对于非单调线性互补问题，这类方法的应用相对较少。 作者王言金和费浦生针对这一挑战，提出了一个创新的非精确不可行内点算法。他们关注的是那些初始状态可能不满足可行性的线性互补问题，这种情况下，传统的可实现内点方法可能无法直接应用。他们的算法设计考虑了实际计算中的不精确性，这在实际问题求解中是非常重要的，因为它允许算法在一定程度上容忍误差，提高了算法的实用性。 文章的核心贡献在于证明了这个非精确不可行内点算法具有多项式复杂性。这意味着随着问题规模的增加，算法所需的计算步骤数量不会指数级增长，而是呈现出一个固定的多项式增长率。这对于复杂度分析而言是关键的结果，因为它确保了算法在处理大规模问题时仍然保持高效。 在算法执行过程中，经过有限的迭代后，要么会找到问题的近似解，要么能够确定在某个大区域内不存在可行最优解。这种方法的出现为非单调线性互补问题的求解提供了一个新的工具箱，特别是在处理实际问题时，它可能比传统方法更具优势，尤其是在面对精度要求不那么严格的情况下。 这篇文章不仅扩展了内点算法的应用范围，还为非单调线性互补问题的算法设计和理论研究做出了贡献，特别是在处理不可行初始点和非精确计算方面的进展，具有较高的学术价值和实用意义。