On Lagrange multipliers of trust-region subproblems. (English) Zbl 1203.65092

Lukšan, Ladislav; Matonoha, Ctirad; Vlček, Jan

Chleboun, J. (ed.) et al., Programs and algorithms of numerical mathematics 14. Proceedings of the seminar, DolníMaxov, Czech Republic, June 1–6, 2008. Prague: Academy of Sciences of the Czech Republic, Institute of Mathematics (ISBN 978-80-85823-55-4). 130-137 (2008).

Summary: We are concerned with large-scale problems where the sparsity pattern plays a considerable role. The Moré-Sorensen method is very efficient for ill-conditioned but reasonably sparse problems [cf. J. J. Moré and D. C. Sorensen, SIAM J. Sci. Stat. Comput. 4, 553–572 (1983; Zbl 0551.65042)]. If the problems do not have sufficiently sparse Hessian matrices, then this method can be much worse than the Steihaug-Toint method whose efficiency also strongly depends on suitable preconditioning [cf. T. Steihaug, SIAM J. Numer. Anal. 20, 626–637 (1983; Zbl 0518.65042); Ph. L Toint, Proc. IMANA Conf., Reading 1980, 57–88 (1981; Zbl 0463.65045)]. There are two possibilities of preconditioning mentioned in Section 2. The first one changes the trust-region problem whereas the second one deforms the trust-region path in the original trust-region problem. Note that the Gould-Lucidi-Roma-Toint method cannot be preconditioned in the second way since the preconditioned Lanczos process does not generate the orthonormal basis related to the original trust-region subproblem [cf. N. I. M. Gould, S. Lucidi, M. Roma, and Ph. L. Toint, SIAM J. Optim. 9, No. 2, 504–525 (1999; Zbl 1047.90510)]. Our preliminary tests have shown that the first preconditioning technique is less efficient because it failed in many cases.
To sum up, the shifted Steihaug-Toint method combines good properties of the More-Sorensen and the Steihaug-Toint methods. Our computational experiments indicate that this method works well in connection with the second way of preconditioning. The point on the trust-region boundary obtained by this method is usually closer to the optimal solution in comparison with the point obtained by the original Steihaug-Toint method.
For the entire collection see [Zbl 1194.65013].

MSC:

65K05	Numerical mathematical programming methods
90C30	Nonlinear programming
90C51	Interior-point methods
90C06	Large-scale problems in mathematical programming

Keywords:

numerical examples; large-scale problems; preconditioning; trust-region problem; Lanczos process

Citations:

Zbl 0551.65042; Zbl 0518.65042; Zbl 0463.65045; Zbl 1047.90510