zbMATH — the first resource for mathematics

A fast algorithm for globally solving Tikhonov regularized total least squares problem. (English) Zbl 1411.65065
Summary: The total least squares problem with the general Tikhonov regularization can be reformulated as a one-dimensional parametric minimization problem (PM), where each parameterized function evaluation corresponds to solving an \(n\)-dimensional trust region subproblem. Under a mild assumption, the parametric function is differentiable and then an efficient bisection method has been proposed for solving (PM) in literature. In the first part of this paper, we show that the bisection algorithm can be greatly improved by reducing the initially estimated interval covering the optimal parameter. It is observed that the bisection method cannot guarantee to find the globally optimal solution since the nonconvex (PM) could have a local non-global minimizer. The main contribution of this paper is to propose an efficient branch-and-bound algorithm for globally solving (PM), based on a new underestimation of the parametric function over any given interval using only the information of the parametric function evaluations at the two endpoints. We can show that the new algorithm (BTD Algorithm) returns a global \(\epsilon \)-approximation solution in a computational effort of at most \(O(n^3/\sqrt{\epsilon })\) under the same assumption as in the bisection method. The numerical results demonstrate that our new global optimization algorithm performs even much faster than the improved version of the bisection heuristic algorithm.

65F20 Numerical solutions to overdetermined systems, pseudoinverses
90C26 Nonconvex programming, global optimization
90C32 Fractional programming
90C20 Quadratic programming
PDF BibTeX Cite
Full Text: DOI arXiv
[1] Beck, A.; Ben-Tal, A., On the solution of the Tikhonov regularization of the total least squares problem, SIAM J. Optim., 17, 98-118, (2006) · Zbl 1112.65034
[2] Beck, A.; Ben-Tal, A.; Teboulle, M., Finding a global optimal solution for a quadratically constrained fractional quadratic problem with applications to the regularized total least squares, SIAM J. Matrix Anal. Appl., 28, 425-445, (2006) · Zbl 1115.65065
[3] Beck, A.; Teboulle, M., A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid, Math. Program., 118, 13-35, (2009) · Zbl 1176.90451
[4] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS/SIAM Series on Optimization. SIAM, Philadelphia (2000) · Zbl 0958.65071
[5] Falk, JE; Soland, RM, An algorithm for separable nonconvex programming problems, Manag. Sci., 15, 550-569, (1969) · Zbl 0172.43802
[6] Fortin, C.; Wolkowicz, H., The trust region subproblem and semidefinite programming, Optim. Methods Softw., 19, 41-67, (2004) · Zbl 1070.65041
[7] Gander, W.; Golub, GH; Matt, U., A constrained eigenvalue problem, Linear Algebra Appl., 114, 815-839, (1989) · Zbl 0666.15006
[8] Gay, DM, Computing optimal locally constrained steps, SIAM J. Sci. Stat. Comput., 2, 186-197, (1981) · Zbl 0467.65027
[9] Golub, GH; Loan, CF, An analysis of the total least-squares problem, SIAM J. Numer. Anal., 17, 883-893, (1980) · Zbl 0468.65011
[10] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[11] Hansen, PC, Regularization tools: a Matlab package for analysis and solution of discrete ill-posed problems, Numer. Algorithm, 6, 1-35, (1994) · Zbl 0789.65029
[12] Hansen, PC; O’Leary, DP, The use of the L-curve in the regularization of discrete ill-posed problems, SIAM J. Sci. Comput., 14, 1487-1503, (1993) · Zbl 0789.65030
[13] Jain, A.K.: Fundamentals of Digital Image Processing. Prentice-Hall, Englewood Cliffs (1989) · Zbl 0744.68134
[14] Joerg, L.; Heinrich, V., Large-scale Tikhonov regularization of total least squares, J. Comput. Appl. Math., 238, 95-108, (2013) · Zbl 1254.65052
[15] Lbaraki, T.; Schaible, S., Fractional programming, Eur. J. Oper. Res., 12, 325-338, (2004)
[16] Moré, JJ; Sorensen, DC, Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 553-572, (1983) · Zbl 0551.65042
[17] Moré, JJ, Generalizations of the trust region problem, Optim. Methods Softw., 2, 189-209, (1993)
[18] Pong, TK; Wolkowicz, H., Generalizations of the trust region subproblem, Comput. Optim. Appl., 58, 273-322, (2014) · Zbl 1329.90100
[19] Rendel, F.; Wolkowicz, H., A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Program., 77, 273-299, (1997) · Zbl 0888.90137
[20] Schaible, S.; Shi, JM, Fractional programming: the sum-of-ratios case, Optim. Methods Softw., 18, 219-229, (2003) · Zbl 1070.90115
[21] Sorensen, DC, Minimization of a large-scale quadratic function subject to a spherical constraint, SIAM J. Optim., 7, 141-161, (1997) · Zbl 0878.65044
[22] Tikhonov, A.N., Arsenin, V.Y.: Solution of Ill-Posed Problems. V.H. Winston, Washington (1977) · Zbl 0354.65028
[23] Van Huffel, S., Lemmerling, P.: Total Least Squares and Errors-in-Variables Modeling. Kluwer, Dordrecht (2002) · Zbl 1002.65500
[24] Van Huffel, S., Vandewalle, J.: The Total Least Squares Problem: Computational Aspects and Analysis. Frontiers in Applied Mathematics, vol. 9. SIAM, Philadelphia (1991) · Zbl 0789.62054
[25] Xia, Y.; Wang, S.; Sheu, RL, S-lemma with equality and its applications, Math. Program. Ser. A, 156, 513-547, (2016) · Zbl 1333.90086
[26] Yang, M.; Xia, Y.; Wang, J.; Peng, J., Efficiently solving total least squares with Tikhonov identical regularization, Comput. Optim. Appl., 70, 571-592, (2018) · Zbl 1391.90498
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.