线性权互补问题的全牛顿步可行内点算法.docx

线性权互补问题（Linear Weighted Complementarity Problem, LWCP）是由Potra在2012年提出的，它是互补问题的一个扩展，旨在找到一对分别属于流形和锥体交集的向量，使得这两向量在特定代数中的乘积等于给定的权向量。当权向量为零时，LWCP退化为传统的互补问题。LWCP在理论上的复杂性高于互补问题，但在经济领域，如Fisher市场均衡问题，它可以被转化为LWCP模型来求解，相较于构建非线性互补模型更为有效。 Anstreicher提出了Fisher问题的广义Eisenberg-Gale模型，将其与线性规划和权中心问题关联起来。Potra进一步将二次规划和权中心问题转换为单调线性权互补问题。文献中提到，尽管LWCP的研究相对较少，但光滑方法和内点算法已被证明是解决优化问题的有效工具。 Zhang等人采用光滑牛顿法解决LWCP，并证明了在一定条件下该方法具有局部二次收敛性。Roos提出了线性规划问题的全牛顿步不可行内点算法，证明了其收敛性和迭代复杂度。其他研究则提出了针对LWCP的全牛顿步可行内点算法，包括求解R^n上的LWCP。 本文的主要贡献是将Roos的内点算法改进并应用于LWCP，提出了一个全牛顿步内点算法来解决线性权互补问题。算法的核心是定义中心路径，以此设计出一个可行的内点策略。作者分析了算法的可行性，并证明了算法具有多项式时间迭代复杂度。通过数值实验，算法的有效性得到了验证。 LWCP的具体形式如(1)所示，其中包含线性方程组、非负约束以及权乘积条件。当权向量ω等于零时，问题变为线性互补问题(2)。Roos的内点算法在互补问题(2)上的迭代复杂度界为O(n^2 log(max{n/4, ||b-2LAe||, ||c-2Le||}/ε))，其中e是全1向量。 在LWCP中，引入了中心路径扰动问题(3)，通过参数t控制路径，随着t趋近于0，中心路径上的解会收敛到LWCP的解。搜索方向(Δx, Δy, Δs)的确定依赖于求解线性方程组(6)，由于矩阵A的秩完整，向量x和s均为正向量，该方程组有唯一解。经过变换，方程组(6)可以简化为(8)，并定义了邻近测度δ(x, s; t)来衡量解与中心路径解的距离。 这些理论和算法的进展为解决实际应用中的LWCP提供了重要的工具，特别是在经济、工程和运筹学等领域。通过不断的研究和完善，未来可能会有更多高效、稳定的方法涌现，以处理更复杂的权互补问题。