A semidefinite framework for trust region subproblems with applications to large scale minimization
A semidefinite framework for trust region subproblems with applications to large scale minimization
复制标题
DOI：
10.1007/bf02614438
复制
发表时间：
1997-05
影响因子：
2.7
通讯作者：
F. Rendl;Henry Wolkowicz
中科院分区：
文献类型：
--
作者：
F. Rendl;Henry Wolkowicz
半定规划的原对偶对为信任域子问题（TRS）的理论和算法提供了通用框架。后一个问题在于最小化受凸二次约束的一般二次函数，因此，它是最小特征值问题的推广。 (TRS) 的重要性在于它提供了信任域最小化算法的步骤。半定框架作为半定规划的一个有趣实例以及查看已知算法和推导新算法（TRS）的工具进行了研究。特别是，研究了将（TRS）作为参数特征值问题求解的对偶单纯形型方法。该方法使用Lanczos算法将最小特征值作为黑盒。因此，该算法的基本成本是矩阵向量乘法，因此可以利用稀疏性。原始单纯形类型方法提供了所谓的硬情况的步骤。讨论了大型稀疏问题的广泛数值测试。这些测试表明，该算法的成本是使用 Lanczos 算法查找最小特征值的成本的 1 +α(n) 倍，其中 0<α(n)<1 是随着维度增加而减少的分数。
Primal-dual pairs of semidefinite programs provide a general framework for the theory and algorithms for the trust region subproblem (TRS). This latter problem consists in minimizing a general quadratic function subject to a convex quadratic constraint and, therefore, it is a generalization of the minimum eigenvalue problem. The importance of (TRS) is due to the fact that it provides the step in trust region minimization algorithms. The semidefinite framework is studied as an interesting instance of semidefinite programming as well as a tool for viewing known algorithms and deriving new algorithms for (TRS). In particular, a dual simplex type method is studied that solves (TRS) as a parametric eigenvalue problem. This method uses the Lanczos algorithm for the smallest eigenvalue as a black box. Therefore, the essential cost of the algorithm is the matrix-vector multiplication and, thus, sparsity can be exploited. A primal simplex type method provides steps for the so-called hard case. Extensive numerical tests for large sparse problems are discussed. These tests show that the cost of the algorithm is 1 +α(n) times the cost of finding a minimum eigenvalue using the Lanczos algorithm, where 0<α(n)<1 is a fraction which decreases as the dimension increases.