线性互补问题新内点算法：代数等价变换与幂变换

"基于代数等价变换的线性互补问题内点算法 (2004年) 文章编号:1000-8608(2004)03-0337-05 作者: 李兴斯, 何素艳, 潘少华, 张洪武 关键词: 线性互补问题; 内点算法; 代数等价变换; 幂变换; 邻近性度量" 线性互补问题（Linear Complementarity Problem, LCP）是数学中的一个重要问题，它在多个领域如经济学、工程学、运筹学等有着广泛应用。LCP通常由三组方程和不等式组成：线性方程组、互补约束和非负约束。本文主要讨论了一种基于代数等价变换的内点算法来解决这类问题。 文章首先分析了对线性互补问题的中心化方程（即，$xs = \mu e$）进行代数等价变换的影响。这里，$x$和$s$是变量向量，$\mu$是一个标量，$e$是单位向量。通过这种变换，作者揭示了彭积明等人提出的自正则邻近度量方法实际上可以被视为一种幂变换的特殊情况。这种方法对于理解LCP的内在性质和寻找有效解法具有重要意义。 随后，作者在更一般的基础上建立了一个基于幂变换的内点算法。内点算法是一种解决线性互补问题和线性规划问题的高效方法，它避免了传统外点算法在迭代过程中可能遇到的边界问题。Karmarkar在1984年提出的投影算法是内点法的起源，之后原-对偶内点算法因其优良的性能而受到广泛关注。 新提出的内点算法利用幂变换对LCP的中心化方程进行操作，增强了算法的效率和稳定性。为了验证新算法的效果，文章通过一系列测试问题与现有的内点算法进行了数值比较。比较结果表明，新算法不仅有效，而且在某些特定问题上展现出优于传统算法的性能。 这篇论文深入探讨了线性互补问题的代数等价变换和内点算法的结合，为解决这类问题提供了新的思路。通过对算法的数值实验，证明了该方法在求解效率和数值稳定性方面的优势，这对于实际应用和进一步的算法优化具有重要的理论价值。