Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization
Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization
复制标题
DOI：
10.1007/s10589-006-9003-y
复制
发表时间：
2007-04
影响因子：
2.2
通讯作者：
O. Schenk;A. Wächter;Michael Hagemann
中科院分区：
文献类型：
--
作者：
O. Schenk;A. Wächter;Michael Hagemann
内点方法是解决大规模非线性规划问题的最有效方法之一。这些方法的核心是必须解决高度病态的对称鞍点问题。我们提出组合方法来预处理这些矩阵，以便为后续分解建立更有利的数值属性。我们的方法基于对称加权匹配，并用于稀疏直接LDLT分解方法，其中旋转仅限于静态超节点数据结构。此外，在额外填充有助于选择更好的数值主元元素的情况下，我们将动态扩展超级节点数据结构。该技术可以被视为更传统的阈值旋转技术的替代方法。我们在来自 CUTE 和 COPS 集的大量测试问题以及基于偏微分方程的大型最优控制问题上在内点方法中证明了这种方法的竞争力。解决的最大的非线性优化问题有超过 1200 万个变量和 600 万个约束。
Interior-point methods are among the most efficient approaches for solving large-scale nonlinear programming problems. At the core of these methods, highly ill-conditioned symmetric saddle-point problems have to be solved. We present combinatorial methods to preprocess these matrices in order to establish more favorable numerical properties for the subsequent factorization. Our approach is based on symmetric weighted matchings and is used in a sparse directLDLTfactorization method where the pivoting is restricted to static supernode data structures. In addition, we will dynamically expand the supernode data structure in cases where additional fill-in helps to select better numerical pivot elements. This technique can be seen as an alternative to the more traditional threshold pivoting techniques. We demonstrate the competitiveness of this approach within an interior-point method on a large set of test problems from the CUTE and COPS sets, as well as large optimal control problems based on partial differential equations. The largest nonlinear optimization problem solved has more than 12 million variables and 6 million constraints.