一种无需中心化步的全NT步不可行内点算法求解半定线性互补问题：收敛性与数值性能

《AppliedMath》：A Novel Full NT-Step Infeasible Interior-Point Algorithm for Semi-Definite Linear Complementarity Problems: Convergence and Numerical Performance

　　

本文提出一种面向半定线性互补问题（SDLCP）的改进型不可行内点算法。所提方法采用全Nesterov–Todd（NT）搜索方向，同时消除中心化步，从而显著简化算法结构并降低计算开销。严格的理论分析证实该方法定义良好、全局收敛，且其迭代复杂度达到该领域不可行内点方法已知最优界。在理论结果之外，大量数值实验凸显了该算法优越的实际性能，与现有方法相比，其始终以更少的迭代次数实现更快的收敛。这些发现表明该算法有潜力成为求解SDLCP的高效且稳健的求解技术，并对大规模和复杂问题实例具有良好适用前景。

研究背景方面，半定线性互补问题（SDLCP）涵盖标准线性互补问题（LCP）、半定规划（SDP）及矩阵不等式系统等广泛优化问题，在控制理论及线性或双线性不等式系统分析等领域具有重要应用。长期以来，内点方法（IPMs）被视为求解此类问题最有效的方法之一，其中Alizadeh–Haeberly–Overton（AHO）、Helmberg–Kojima–Monteiro（HKM）与Nesterov–Todd（NT）方向最为突出，HKM与NT方向已被SeDuMi和SDPT3等先进半定规划求解器广泛采用。然而，内点方法的效率对初始点的选择高度敏感，为克服需可行初始点的局限，不可行内点方法（IIPMs）得以发展，可从任意正点出发同时逼近可行性与最优性。Lustig最早为线性优化引入不可行内点方法，Zhang随后为半定优化（SDO）建立了具有多项式迭代复杂度的原始–对偶内点方法。尽管无中心化全NT步方法已在半定规划中有所研究，但将其推广至SDLCP需要单独考虑问题结构及互补条件的收敛性分析，这正是本研究开展的原因。

研究人员开展了针对SDLCP的不可行内点算法研究，采用无中心化全NT步方法，证明了算法的定义良好性与全局收敛性，推导出迭代复杂度界，并通过数值实验评估算法性能。研究得出该算法迭代复杂度达到该领域不可行内点方法已知最优界，数值实验表明其相比现有方法迭代次数更少、CPU时间更短，具有高效性与稳健性，对大规模复杂问题具有应用潜力。

关键技术方法方面，研究采用全Nesterov–Todd（NT）搜索方向构造对称化牛顿系统，通过引入可逆矩阵P进行对称化处理，利用矩阵D将X与Y缩放为同一对称矩阵V；采用核函数替代经典对数核函数构造搜索方向；采用路径跟踪策略的不可行原始–对偶框架，从正定矩阵出发无需满足可行性方程；通过邻近度量（proximity measure）控制迭代点位于中心路径邻域内。数值实验在MATLAB R2025a平台上实现，测试了五个数值算例，包括半定最小二乘问题（SDLS）、Sylvester算子问题、对称Kronecker和算子问题、由凸二次半定优化问题（CQSDO）转化而来的SDLCP以及由半定优化（SDO）转化而来的SDLCP，并与文献中的参考算法进行了比较。

研究结果方面，在可行性与算法良定义性分析中，通过Lemma 7与Corollary 1建立了新迭代点保持正定性的充分条件，证明了在适当参数选择下更新后的矩阵X与Y保持正定且邻近度量保持有界。在迭代界分析中，Theorem 1证明了在原始–对偶问题存在满足假设的最优解条件下，算法经有限次迭代可计算得到ε-最优解，每次主迭代原始残量至少缩减一定因子，总主迭代次数具有上界。数值实验部分，Problem 1考察半定最小二乘问题（SDLS），将其最优性条件转化为单调SDLCP，研究了不同障碍参数μ下的迭代次数与CPU时间，Figure 1展示了不同μ值的收敛性能；Problem 2考察Sylvester算子描述的单调SDLCP，Table 2给出了不同n值的计算结果；Problem 3考察对称Kronecker和算子描述的SDLCP，Table 3给出不同n值的计算结果，Table 4报告了终端可行性误差、互补误差、X与Y的最小特征值及最终μ值以评估解的精度；Problem 4考察由CQSDO转化而来的SDLCP，Table 5给出不同μ值的计算结果；Problem 5考察由SDO转化而来的SDLCP，Table 6给出计算结果。Remark 1指出数值结果表明算法在μ从某一值降至另一值时迭代次数保持相对稳定，CPU时间总体略有下降。比较研究中，Table 7汇总了所提算法与文献中Algorithm 2在五个SDLCP测试问题上的迭代次数与CPU时间比较，所提算法一致地以更少迭代次数和更少CPU时间收敛。

讨论部分总结指出，本研究对Mansouri等人提出的经典不可行内点算法进行了改进，核心改进在于从每次主迭代中去除中心化步，从而获得更简单且计算更高效的方法；严格证明了算法定义良好且全局收敛，其迭代复杂度达到SDLCP背景下不可行内点方法已知最优理论界；大量数值实验证明了算法的优越性能，特别是采用新引入参数时优于文献中的参数选择；比较分析进一步表明该方法一致地需要更少迭代次数与CPU时间。未来研究方向为将算法评估扩展至更大规模及更多样化的问题实例，以进一步评估其可扩展性与实际性能。研究结论部分译为：本文提出了经典不可行内点算法的增强版本用于求解半定线性互补问题，关键改进在于去除每次主迭代中的中心化步，形成更简单且计算更高效的方法；严格证明了所提算法定义良好且全局收敛，并证明其迭代复杂度达到SDLCP背景下不可行内点方法已知最优理论界；大量数值实验证明了所提算法的优越性能，尤其在使用新引入参数时优于文献中的参数选择；比较分析进一步表明该方法相比参考算法一致地需要更少迭代次数和更少CPU时间，凸显了其求解SDLCP的效率与实际适用性。