线性规划对偶投影最钝角松弛算法的研究

作为前一个已结题国家自然科学基金项目的标志性成果，我们提出的 "修正对偶投影主元算法" 在数值试验中取得了极好的效果，甚至超过最新版著名优化软件MINOS 5.51）。.而另一方面，基于"最钝角原理"的主元规则在实践中引人注目，表现不凡。我们拟在松弛迭代的新架构中将这两项成功技术加以整合。以获得更高效的新算法。其基本思路是，按最钝角原理略去部分约束和变量得到一个规模较小的子问题, 用修正对偶投影主元算法解之；然后添加所略去的约束及变量恢复原问题，若所得到的是原问题的最优解则终止，否则完成一次主迭代。.新算法对于求解大规模稀疏问题具有重要价值。目前使用的分解算法虽然也可缩小大规模稀疏问题的规模，但只适用于特定结构，而新算法则可处理一般问题。