报告人：Kim-Chuan Toh教授

报告题目：An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization

摘要：We consider solving high-order semidefinite programming (SDP) relaxations of polynomial optimization problems (POPs) that often admit degenerate rank-one optimal solutions. Instead of solving the SDP alone, we propose a new algorithmic framework that blends local search using the nonconvex POP into global descent using the convex SDP. In particular, we first design a globally convergent inexact projected gradient method (iPGM) for solving the SDP that serves as the backbone of our framework. We then accelerate iPGM by taking long, but safeguarded, rank-one steps generated by fast nonlinear programming algorithms. We prove that the new framework is still globally convergent for solving the SDP. To solve the iPGM subproblem of projecting a given point onto the feasible set of the SDP, we design a two-phase algorithm with phase one using a symmetric Gauss-Seidel based accelerated proximal gradient method to generate a good initial point,  and phase two using a modified limited-memory BFGS method to obtain an accurate solution. We conduct numerical experiments for solving second-order SDP relaxations arising from a diverse set of POPs. Our framework demonstrates state-of-the-art efficiency, scalability, and robustness in solving degenerate rank-one SDPs to high accuracy, even in the presence of millions of equality constraints.

报告人简介：Kim-Chuan Toh教授1990年本科毕业于新加坡国立大学数学系，1992年在新加坡国立大学数学系获硕士学位，1996在美国康奈尔大学应用数学中心获博士学位（导师: Nick Trefethen教授），并开始在新加坡国立大学数学系工作。Toh教授于2018年入选美国工业与应用数学学会会士（SIAM Fellow）、现任新加坡国立大学数学系系主任、Leo Tan教授。Toh教授是国际知名数值优化专家，主要致力于矩阵优化、凸规划等方面的算法设计、分析与实现。Toh教授及其合作者研制的软件如SDPT3，SDPNAL/SDPNAL+, LassoNAL等被学术界和工业界广泛使用。Toh教授现任《Mathematical Programming》，《Mathematical Programming Computation》以及《SIAM Journal on Optimization》等连续优化方向重要国际学术期刊的编委。Toh教授获得众多国际奖项，于2017 年获得INFORMS优化协会颁发的Farkas奖、2018年获得三年一度的Beale-Orchard Hays奖，2019年获得新加坡最高研究奖-总统科学奖。

报告时间：2021年12月27日下午14:00-16:00

报告形式：腾讯会议；会议号：712 220 241