双步长内点算法中一个子问题的研究

本文研究了双步长内点算法中的一个子问题，具体地，讨论了原始对偶路径跟踪内点算法的修正算法所涉及的双步长问题。文中提出了两种不同的步长寻找方法，并利用Matlab编写了相关算法程序，通过对大量数值结果的分析，讨论了步长的性质。 线性互补问题（LCP）在运筹学、经济学、工程技术等领域中有着广泛的应用。内点算法作为一种有效的求解线性互补问题的方法，已得到了深入的研究。该算法的基本思想是，通过在可行域内部选择一点作为迭代起点，然后迭代地向最优解靠近。内点算法因其在理论上具备多项式时间复杂度，并在实际应用中显示出良好的性能，而受到了广泛的关注。 Kojima、Mizuno和Yoshise提出了一种内点算法用于求解线性互补问题，并指出在求解具体问题时，该算法最多需要O(nL)次迭代。其中n是问题的大小，L是表示问题规模的一个指标。艾文宝教授和张树中教授在2004年对于单调线性互补问题的求解，提出了一种原始对偶路径跟踪内点算法的修正算法，并首次在算法中采用双步长方法。双步长方法是指在迭代过程中同时确定两个步长，这两个步长分别用于指导算法沿着两个不同的方向进行迭代。这种修改旨在提高算法的效率和稳定性。 文章中提到的子问题，形式上是一个关于步长α的优化问题，具体为寻找满足一定约束条件的步长向量，以使得目标函数值最小。这个问题是一个具有特定约束条件的优化问题，需要在一定的邻域内找到合适的步长向量来逼近最优解。 为了求解这个子问题的步长，作者提出了两种方法：网格法和二分法。网格法是通过在参数空间内构建网格，每个网格点代表一个可能的步长向量。通过迭代过程检查每个步长向量对应的子问题解，从而确定本轮迭代的最佳步长。网格法的一个显著特点是计算量大，但其优点是迭代次数较少。 相比之下，二分法通过逐步缩小步长α的搜索区间来寻找最优步长，使得搜索过程从二维搜索变为一维搜索，从而减少了计算量。这种方法的优点是计算复杂度相对较低，但在某些情况下，其迭代次数可能高于网格法。 具体到算法实现，文章给出了两种方法的详细步骤，包括输入输出参数的定义、迭代终止条件、以及在每一步如何确定步长并计算目标函数值。需要注意的是，文中描述的算法步骤可能会因为OCR扫描过程中出现的文字识别错误而有缺失或不连贯，但核心内容是清晰的。 为了验证这两种方法的有效性和可行性，作者通过编写Matlab程序对这两种方法进行了大量的数值实验，并对实验结果进行了分析。实验结果有助于理解两种方法在不同情况下的性能差异，为进一步优化算法提供了依据。 关键词中提到的单调线性互补问题（monotone LCP），是指满足一定单调性质的线性互补问题，这在理论上保证了解的存在性和算法的收敛性。原始对偶内点算法（Primal-Dual Interior-Point Method）是解决这类问题的一种常用方法，而宽邻域（wide neighborhood）是指算法设计中所定义的迭代过程的搜索范围，它与算法的收敛速度密切相关。 本文的研究成果对于理解原始对偶路径跟踪内点算法的特性、改进现有算法以及探索新的算法设计具有理论和实践意义。