Report title: Globally solving Tikhonov regularized total least squares problem

Reporter: Professor Xia Yong, Beijing University of Aeronautics and Astronautics

Reporting time: 9:50-10:30 am on December 7, 2020

Report location: Tencent Conference ID: 191 170 890

Conference password: 9999

School contact: Li Xinxin xinxinli@jlu.edu.cn

Report summary: 

The well-known 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, 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 talk 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 func tion 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. For a special case, the Tikhonov identical regularized total least squares, we propose a more efficient algorithm based on the hidden convexity.

Speaker's profile: 

Xia Yong, Professor and Associate Dean of the School of Mathematical Sciences, Beihang University. He graduated from the School of Mathematical Sciences, Peking University in 2002, and graduated from the Academy of Mathematics and Systems Science, Chinese Academy of Sciences with a Ph.D. in 2007. He joined Beihang University in the same year. The research direction is non-convex optimization, and 54 SCI papers have been published in MP, SIOPT, MOR and other journals. In 2018, he was approved by the National Natural Science Foundation of China for Outstanding Youth Science Fund projects. Representative work: Established a complete equation-type S-lemma with collaborators; the model proposed in cooperation with academician Yuan Yexiang on the classic quadratic assignment problem is called Xia-Yuan linearization by domestic and foreign colleagues.