A semidefinite framework for trust region subproblems with applications to large scale minimization
Rendl, Franz
Wolkowicz, Henry

Data: 1997
Resum: 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 + (alpha)(n) times the cost of finding a minimum eigenvalue using the Lanczos algorithm, where 0 < (alpha)(n) < 1 is a fraction which decreases as the dimension increases. .
Drets: Tots els drets reservats
Llengua: Anglès
Document: article ; recerca ; Versió publicada
Matèria: Trust region subproblems ; Parametric programming ; Semidefinite programming ; Min-max eigenvalue problems ; Large scale minimization
Publicat a: Mathematical Programming, vol. 77 n. 2 (1997) p. 273-299, ISSN 0025-5610

27 p, 1.3 MB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2021-06-27

   Favorit i Compartir