改进的二阶Mehrotra预估矫正算法：无保障措施下的不可行内点优化

本文主要探讨的是线性规划的二阶不可行预估-矫正算法在锥规划问题中的应用。该研究基于Mehrotra型预估-矫正算法的传统框架，提出了一个新的自适应更新方法，旨在解决在线性规划问题中遇到的不可行内点挑战。Mehrotra算法是一种经典的内点算法，其核心在于通过预估和矫正步骤来逼近可行区域，尤其在处理标准形式的线性规划问题时表现出色。 在传统算法中，可能会遇到内点算法需要多次小步调整才能到达最优解的问题，这可能导致效率不高。为了解决这个问题，论文的作者没有引入额外的“保障措施”，而是直接针对宽邻域上线性规划问题设计了一个不可行内点算法。这种算法的主要贡献在于能够在不依赖额外策略的情况下，保证算法的迭代过程具备O(n1.5log(1/ε))的迭代复杂性，这里的n表示变量的数量，ε代表目标精度。 算法的迭代复杂性分析是本文的核心部分，它展示了算法在优化过程中达到所需精度所需的基本步骤数量与问题规模的关系。这种多项式复杂性意味着算法的运行时间随着问题规模的增长而相对较快地增加，这对于实际应用中的大规模优化问题至关重要。 文中提到的关键词，如“线性规划”、“不可行内点算法”、“Mehrotra型预估-矫正算法”以及“多项式复杂性”，都是理解这篇论文的关键点。作者通过比较和借鉴先前的研究，如文献[6]和[8]，展示了他们的算法如何改进了Mehrotra算法的不足，尤其是在处理不可行问题时的性能。 总结来说，这篇论文不仅提供了一个新颖的算法设计，而且还通过理论分析确保了算法的有效性和高效性。这对于优化领域特别是线性规划问题的解决具有重要的理论价值和实践意义，有助于提升优化软件包的性能和实用性。