报告题目：Globally solving Tikhonov regularized total least squares problem

报 告 人：夏勇 教授 北京航空航天大学

报告时间：2020年12月7日 上午 9:50-10:30

报告地点：腾讯会议 ID：191 170 890

会议密码：9999

校内联系人：李欣欣        xinxinli@jlu.edu.cn

报告摘要：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 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. For a special case, the Tikhonov identical regularized total least squares, we propose a more efficient algorithm based on the hidden convexity.

报告人简介：夏勇，北京航空航天大学数学科学学院教授、副经理。2002年本科毕业于北京大学数学科学学院，2007年博士毕业于中国科学院数学与系统科学研究院，同年入职北航。研究方向为非凸优化，在MP、SIOPT、MOR等期刊发表SCI论文54篇，2018获批国家自然科学基金优秀青年科学基金项目。代表性工作：与合作者建立了完整的等式型S-引理；与导师袁业湘院士合作在经典二次指派问题上提出的模型被国内外同行称为Xia-Yuan线性化。