A semidefinite framework for trust region subproblems with applications to large scale minimization |
| |
Authors: | Franz Rendl Henry Wolkowicz |
| |
Institution: | 1. Institut für Mathematik, Technische Universit?t Graz, Kopernikusgasse 24, A-8010, Graz, Austria 2. Department of Combinatorics and Optimization, University of Waterloo, N2L 3GI, Waterloo, Ontario, Canada
|
| |
Abstract: | 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.
Research supported by the National Science and Engineering Research Council Canada. |
| |
Keywords: | Trust region subproblems Parametric programming Semidefinite programming Min-max eigenvalue problems Large scale minimization |
本文献已被 SpringerLink 等数据库收录! |
|