×

Computational and sensitivity aspects of eigenvalue-based methods for the large-scale trust-region subproblem. (English) Zbl 1273.90142

Summary: The trust-region subproblem (TRS) of minimizing a quadratic function subject to a norm constraint arises in the context of trust-region methods in optimization and in the regularization of discrete forms of ill-posed problems, including nonnegative regularization by means of interior-point methods. A class of efficient methods and software for solving large-scale trust-region subproblems (TRSs) is based on a parametric-eigenvalue formulation of the subproblem. The solution of a sequence of large symmetric eigenvalue problems is the main computation in these methods. In this work, we study the robustness and performance of eigenvalue-based methods for the large-scale TRS. We describe the eigenvalue problems and their features, and discuss the computational challenges they pose as well as some approaches to handle them. We present results from a numerical study of the sensitivity of solutions to the TRS to eigenproblem solutions.

MSC:

90C20 Quadratic programming
90C06 Large-scale problems in mathematical programming
90C51 Interior-point methods

Software:

UFO
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] DOI: 10.1137/060654797 · Zbl 1151.49027
[2] Barbero A., Fast algorithms for total-variation based optimization (2010)
[3] DOI: 10.1137/0142040 · Zbl 0498.35084
[4] DOI: 10.1137/1.9780898719673 · Zbl 0846.65020
[5] DOI: 10.1137/1.9780898719857 · Zbl 0958.65071
[6] DOI: 10.1137/0720002 · Zbl 0523.65021
[7] DOI: 10.1007/BF01932285 · Zbl 0362.65105
[8] DOI: 10.1080/10556780410001647186 · Zbl 1070.65041
[9] Fotland B. H., A matrix-free method for the regularisation with unrestricted variables (1956)
[10] Golub G., Stochastic error estimates for iterative linear solvers: Part 2 (2000)
[11] DOI: 10.1023/A:1021985111111
[12] DOI: 10.1007/s11075-007-9136-9 · Zbl 1128.65029
[13] DOI: 10.1137/1.9780898718027 · Zbl 1011.65010
[14] DOI: 10.1016/j.laa.2011.07.028 · Zbl 1237.65039
[15] DOI: 10.1109/TCOMM.2005.861691
[16] Hurley, N. and Zhang, M.Analysis of methods for novel case selection. 20th IEEE International Conference on Tools with Artificial Intelligence, ICTAI ’08. pp.217–224. Dayton, OH: IEEE.
[17] DOI: 10.1007/s10044-007-0082-x · Zbl 1422.68213
[18] Lampe J., Solving regularized total least squares problems based on eigenproblems (2010) · Zbl 1198.65081
[19] DOI: 10.1137/090764426 · Zbl 1368.65096
[20] DOI: 10.1137/1.9780898719628 · Zbl 0901.65021
[21] Lukšan L., UFO 2006 interactive system for universal functional optimization (2006)
[22] DOI: 10.1016/j.laa.2009.04.017 · Zbl 1185.65068
[23] DOI: 10.1137/100786125 · Zbl 1243.65016
[24] DOI: 10.1007/s10092-010-0030-9 · Zbl 1216.65047
[25] Nava G., Inverse sound rendering: In-situ estimation of surface acoustic impedance for acoustic simulation and design of real indoor environments (2006)
[26] DOI: 10.1016/j.cviu.2008.05.010 · Zbl 05363056
[27] DOI: 10.1080/03052150701218475
[28] Parlett B., The Symmetric Eigenvalue Problem (1980) · Zbl 0431.65017
[29] Rendl F., Math. Program. 77 pp 273– (1997)
[30] DOI: 10.1137/S1064827500378167 · Zbl 1006.86004
[31] DOI: 10.1088/0266-5611/18/5/305 · Zbl 1015.90062
[32] Rojas M., Computational and sensitivity aspects of eigenvalue-based methods for the large-scale trust-region subproblem – extended version (2013) · Zbl 1273.90142
[33] DOI: 10.1137/S105262349928887X · Zbl 0994.65067
[34] DOI: 10.1145/1326548.1326553 · Zbl 1291.65177
[35] DOI: 10.1016/0022-247X(72)90259-4 · Zbl 0237.65086
[36] DOI: 10.1137/S0895479894270427 · Zbl 0860.65023
[37] DOI: 10.1137/0719026 · Zbl 0483.65039
[38] DOI: 10.1137/0613025 · Zbl 0763.65025
[39] DOI: 10.1137/S1052623494274374 · Zbl 0878.65044
[40] DOI: 10.1137/1032121 · Zbl 0722.15002
[41] Tikhonov A., Soviet Math. 4 pp 1624– (1963)
[42] Tikhonov, A. and Arsenin, V. 1977. ”Solutions of Ill-Posed Problems”. New York: Halsted Press. · Zbl 0354.65028
[43] DOI: 10.1023/B:BITN.0000039424.56697.8b · Zbl 1066.65059
[44] DOI: 10.1016/j.amc.2009.08.033 · Zbl 1175.94030
[45] DOI: 10.1016/j.neucom.2007.01.013 · Zbl 05718652
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.