  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 novel 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/\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.
