A fast algorithm for globally solving Tikhonov regularized total least squares problem

Yong Xia (), Longfei Wang () and Meijia Yang ()
Additional contact information
Yong Xia: Beihang University
Longfei Wang: Beihang University
Meijia Yang: Beihang University

Journal of Global Optimization, 2019, vol. 73, issue 2, No 3, 330 pages

Abstract: Abstract 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 })$$ O ( n 3 / ϵ ) 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.

Keywords: Total least squares; Tikhonov regularization; Trust region subproblem; Fractional program; Lower bound; Branch and bound; 65F20; 90C26; 90C32; 90C20 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-018-0719-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:73:y:2019:i:2:d:10.1007_s10898-018-0719-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-018-0719-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().